2

I am writing a simple game engine that can play games like Chess and Checkers and I'm not sure if I'm implementing the root method of alpha beta function correctly. This is the regular function:

double AlphaBeta(GameState gameState, int depth, double a, double b)
    {
        if (depth == 0 || gameState.IsOver)
            return Evaluate(gameState);

        var moves = gameState.GetMoves();
        var bestValue = double.MinValue;
        foreach (Move move in moves)
        {
            double value = -AlphaBeta(gameState.MakeMove(move), depth - 1, -b, -a);
            bestValue = Math.Max(value, bestValue);
            a = Math.Max(value, a);
            if (a >= b)
                break;
        }
        return bestValue;
    }

Here Evaluate method always returns the value from the perspective of the player that has the turn and MakeMove returns a copy of the original game state with the move made. But I'm not sure what to do with the root function. This is what I have right now:

Move AlphaBetaRoot(GameState gameState, int depth)
    {
        var moves = gameState.GetMoves();
        moves = moves.OrderBy(o => AlphaBeta(gameState.MakeMove(o), depth - 1, double.MinValue, double.MaxValue)).ToList();
        return moves[0];
    }

This seems to work perfectly fine so far (I tested it with 3x3 Tic Tac Toe), but it doesn't do any pruning for the root node. So I thought maybe it should be more like this:

Move AlphaBetaRoot2(GameState gameState, int depth)
    {
        double a = double.MinValue;
        double b = double.MaxValue;

        var moves = gameState.GetMoves();
        Move bestMove = null;

        foreach (Move move in moves)
        {
            var value = -AlphaBeta(gameState.MakeMove(move), depth - 1, -b, -a);
            if (value >= a)
            {
                a = Math.Max(value, a);
                bestMove = move;
            }
            if (a >= b)
                break;
        }
        return bestMove;
    }

But I just can't get this to work and I don't know what to do. Whatever I change, I end up with something that plays incomprehensible or losing moves.

Although there's a lot of literature and questions on Alpha-Beta Pruning on the web, I haven't found anything about how to implement the root method. So, I'd appreciate any help.

Terry Anderson
  • 117
  • 1
  • 1
  • 8
  • 1
    When I wrote something similar for a connect four, I had to take the depth into account (fewer moves to a win should be preferred) and when there are multiple moves that are equally the best I would randomly pick one. http://stackoverflow.com/questions/36792847/implementing-and-using-minmax-with-four-in-row-connect4-game – juharr Dec 09 '16 at 20:36
  • I have the random-if-all moves-are-equal thing in the real implementation too; it makes the games much less boring. However, I don't think it would add anything to the question. Prioritizing wins in fewer act makes sense though, I'm going to check that out. – Terry Anderson Dec 09 '16 at 20:47
  • See: http://stackoverflow.com/questions/3884793/why-is-double-min-value-in-not-negative. You probably want `double a = -double.MaxValue;` – Jeff Y Dec 09 '16 at 21:23
  • @JeffY This is in C# so I don't think that applies here; but it was nevertheless interesting to learn since I use Java too and I haven't heard about it before. – Terry Anderson Dec 09 '16 at 21:37

0 Answers0