标签: minimax

一个学校项目让我用C++编写一个日期游戏(例如http://www.cut-the-knot.org/Curriculum/Games/Date.shtml),其中计算机玩家必须实现具有alpha-beta修剪的Minimax算法.到目前为止,我理解算法背后的目标是在最大化潜在收益方面,同时假设对手将其缩小.

但是,我读过的资源都没有帮助我理解如何设计评估函数,minimax基于它的所有决策.所有示例都为叶节点分配了任意数字,但是,我需要为这些节点实际分配有意义的值.

Intuition告诉我,对于win leaf节点来说它会是+1,对于一个丢失节点会是-1,但是中间节点如何评估呢？

非常感激任何的帮助.

我已经实现了Floyd-Warshall算法来解决全对最短路径问题.现在我发现我还可以通过简单的修改来计算minimax或maximin路径.但我不明白结果意味着什么(最小极大路径是什么).我在网上找到了一些解释,但它们让我很困惑.

Minimax - 图中问题的Minimax涉及在两个节点之间找到一条路径,以最小化路径上的最大成本.

Maximin - 与Minimax相反的方式 - 在这里你遇到了一些问题,你需要找到最大化路径最小成本的路径.

有人可以尝试给出其他解释或示例吗？

我有自己的国际象棋引擎使用minimax算法搜索国际象棋移动的问题我使用5层深度搜索并且只有材料/奖励/移动性评估,但它也会使愚蠢的动作和牺牲有价值的棋子,即使我给他们无限(这肯定是一个搜索问题),我没有使用任何类型的修剪,并在几秒钟内提供5深度搜索结果.

我坚持这个问题一个星期,我确定问题是回溯而不是国际象棋逻辑(因此任何没有国际象棋背景的人都会解决这个:))我搜索了很多这是我在Stack Overflow中的第一个问题我希望你们不要让我失望:)

这是简单的搜索代码

int GameControl::Evaluate(ChessBoard _B)
{

    int material=0,bonus=0,mobility=0;
    for(int i=0;i<8;i++)
        for(int j=0;j<8;j++)
        {

            if(_B.Board[i][j]!=EMPTY)
            {
                if(_B.Board[i][j]->pieceColor==WHITE){
                    material+=-_B.Board[i][j]->Weight;
                    bonus+=-_B.Board[i][j]->bonusPosition[i][j];
                    mobility+=-_B.Board[i][j]->getPossibleMovesList(i,j,B).size();
                }
                else {
                    material+=_B.Board[i][j]->Weight;
                    bonus+=_B.Board[i][j]->bonusPosition[i][j];             
                mobility+=_B.Board[i][j]->getPossibleMovesList(i,j,B).size();
                }
            }
        }
        return material+bonus/10+mobility/20;
}


pair<pair<int,int>,pair<int,int>> GameControl::minimax( int depth , ChessBoard _B )
{
    short int i,j;

    int bestValue = -INFINITY;

    pair<pair<int,int>,pair<int,int>> bestMove;

    vector< pair<int,int> > ::iterator it;

    vector< pair<int,int> > Z;

    for( i = 0; i < 8; i++ )

        for( j = 0; j < 8; j++ )
        {
            if(_B.Board[i][j]!=EMPTY …

我目前正在尝试自学Minimax算法,并且我已尝试在tic tac toe中实现它.然而,我的算法中存在一个错误,我无法弄清楚导致它的原因.

以下是完整的源代码(抱歉,文字墙!):

public class TicTacToe {
    private static boolean gameEnded = false;
    private static boolean player = true;
    private static Scanner in = new Scanner(System.in);
    private static Board board = new Board();

    public static void main(String[] args){
        System.out.println(board);
        while(!gameEnded){
            Position position = null;
            if(player){
                position = makeMove();
                board = new Board(board, position, PlayerSign.Cross);
            }else{
                board = findBestMove(board);
            }               
            player = !player;
                System.out.println(board);
                evaluateGame();
        }
    }

    private static Board findBestMove(Board board) {
        ArrayList<Position> positions = board.getFreePositions();
        Board bestChild = …

我试图在Russel Norvig的人工智能书中给出了用于井字游戏的极小极大算法.它拥有除了将bestMove返回给用户的方式之外的所有内容.我努力回归bestMove,但无法决定何时选择bestMove.帮忙,有人吗？

moveT MiniMax(stateT state)
{
    moveT bestMove;

    max_move(state,bestMove);

    return bestMove;

}

int max_move(stateT state,int & bestMove)
{
    int v = -10000;
    if(GameIsOver(state))
    {
        return EvaluateStaticPosition(state);

    }

    vector<moveT> moveList;
    GenerateMoveList(state, moveList);
    int nMoves = moveList.size();

    for(int i = 0 ; i < nMoves ; i++)
    {
        moveT move = moveList[i];
        MakeMove(state, move);

        int curValue = min_move(state,bestMove);

            if(curValue > v)
            {
              v = curValue;
              bestMove = move;
            }
        RetractMove(state, move);

    }

    return v;

}

int min_move(stateT state, int &bestMove)
{
    int …

我正在为国际象棋比赛做AI.

到目前为止,我已经成功实现了Alpha-Beta Pruning Minimax算法,它看起来像这样(来自维基百科):

(* Initial call *)
alphabeta(origin, depth, -?, +?, TRUE)

function alphabeta(node, depth, ?, ?, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        for each child of node
            ? := max(?, alphabeta(child, depth - 1, ?, ?, FALSE))
            if ? ? ?
                break (* ? cut-off *)
        return ?
    else
        for each child of node
            ? := min(?, alphabeta(child, depth - 1, ?, ?, TRUE))
            if …

我正在写一个国际象棋引擎,最近添加了一个换位表.

在进行一些测试时,我发现尽管搜索仍然返回了相同的最佳移动,但移动的值(对于最大化玩家有多好)会波动.

这是换位表的正常行为吗？我记得读过换位表会导致搜索不稳定.这是什么意思？这是我的代码中的正常事件或严重错误吗？

在我的方法newminimax499我有一个minimax算法,利用memoization和alpha beta修剪.该方法适用于3x3游戏,但是当我玩4x4游戏时,我会为计算机选择奇怪的意外位置.他仍然没有输球,但他似乎没有赢得胜利.为了说明这里的问题,从3x3和4x4的2场比赛开始.首先是一个3x3游戏的场景,其中玩家是X并进行第一步:

这不错,实际上这是人们期望计算机做的事情.现在来看看4x4游戏中的场景.O再次是计算机而X开始:

正如你所看到的,计算机只是一个接一个地将Os放入一个系统的顺序中,只有当它有潜在的胜利时才打破该命令以阻止X. 这是非常防守的比赛,不像在3x3比赛中看到的那样.那么为什么3x3和4x4的方法表现不同？

这是代码:

//This method returns a 2 element int array containing the position of the best possible 
//next move and the score it yields. Utilizes memoization and  alpha beta 
//pruning to achieve better performance. 
public int[] newminimax499(int a, int b){
    //int bestScore = (turn == 'O') ? +9 : -9;  //X is minimizer, O is maximizer
    int bestPos=-1;
    int alpha= a;
    int beta= b;
    int currentScore;
    //boardShow();
    String stateString = "";                                                
    for (int i=0; i<state.length; i++) …

我正在Pacman的基本游戏中的Python 2.7.11中实现minimax。Pacman是最大化代理，而一个或多个幽灵（取决于测试布局）是最小化代理。

我必须实现minimax，以便可能有多个以上的最小化代理，并且它可以创建n层（深度）的树。例如，第1层将是每个幽灵转弯以最小化终端状态实用程序的可能移动，以及pacman进行转弯以最大化幽灵已经最小化的东西。在图形上，层1如下所示：

如果我们将以下任意实用程序分配给绿色终端状态（从左到右）：

-10, 5, 8, 4, -4, 20, -7, 17

Pacman应该返回-4，然后朝该方向移动，根据该决定创建一个全新的minimax树。首先，实现我的实现所需要的变量和函数的列表：

# Stores everything about the current state of the game
gameState

# A globally defined depth that varies depending on the test cases.
#     It could be as little as 1 or arbitrarily large
self.depth

# A locally defined depth that keeps track of how many plies deep I've gone in the tree
self.myDepth

# A function that assigns a numeric …

极小极大算法的描述说，两个玩家都必须发挥最优，这样算法才是最优的。直观上是可以理解的。但是有没有人能具体说明一下，或者证明如果 min 发挥不理想会发生什么？

谢谢