Я пишу простой игровой движок, который может играть в такие игры, как шахматы и шашки, и я не уверен, правильно ли я реализую корневой метод альфа-бета-функции. Это обычная функция:
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;
}
Здесь метод Evaluate всегда возвращает значение с точки зрения игрока, у которого есть ход, а MakeMove возвращает копию исходного состояния игры со сделанным ходом. Но я не уверен, что делать с корневой функцией. Это то, что у меня есть прямо сейчас:
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];
}
Кажется, пока это работает отлично (я тестировал это с помощью 3x3 Tic Tac Toe), но не делает никакой обрезки для корневого узла. Поэтому я подумал, может быть, это должно быть больше похоже на это:
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;
}
Но я просто не могу заставить это работать, и я не знаю, что делать. Что бы я ни менял, в итоге я получаю что-то, что играет непонятными или проигрышными ходами.
Хотя в Интернете есть много литературы и вопросов по Alpha-Beta Pruning, я ничего не нашел о том, как реализовать корневой метод. Так что буду признателен за любую помощь.
double a = -double.MaxValue;
- person Jeff Y   schedule 10.12.2016