Вопрос
Я искал Google и Stackoverflow для этого вопроса, но я все еще не понимаю, как работает функция MiniMax.
Я нашел запись Wikipedia имеет псевдокодную версию функции:
function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
α = max(α, -minimax(child, depth-1))
return α
Несколько других функций MiniMax, которые я нашел с Google, в основном то же самое; Я пытаюсь осуществить это в C ++, и это то, что я придумал до сих пор:
double miniMax(Board eval, int iterations)
{
//I evaluate the board from both players' point of view and subtract the difference
if(iterations == 0)
return boardEval(eval, playerNumber) - boardEval(eval, opponentSide());
/*Here, playerTurn tells the findPossibleMoves function whose turn it is;
I mean, how do you generate a list of possible moves if you don't even know
whose turn it's supposed to be? But the problem is, I don't see where I can
get playerTurn from, as there are only 2 parameters in all the examples of
minimax I've seen*/
vector<int> moves = eval.findPossibleMoves(playerTurn);
//I'm assuming -∞ in the wikipedia article means a very low number?
int result = -999999999;
//Now I run this loop to evaluate each possible move
/*Also, the Lua example in the wiki article has
alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
Is alpha a boolean there?!*/
for(int i = 0; i * 2 < moves.size(); i++)
{
//I make a copy of the board...
Board temp = eval;
/*and make the next possible move... once again playerTurn crops up, and I
don't know where I can get that variable from*/
temp.putPiece(moves[i * 2], moves[i * 2 + 1], playerTurn);
/*So do I create a function max that returns the bigger of two doubles?*/
result = max(result, -miniMax(temp, iterations - 1));
}
return result;
/*So now I've returned the maximum score from all possible moves within a certain
# of moves; so how do I know which move to make? I have the score; how do I know
which sequence of moves that score belongs to?*/
}
Как видите, я довольно запутался об этой функции miniMax. Пожалуйста, по крайней мере, дайте мне несколько советов, чтобы помочь мне с этим.
Спасибо! :)
Решение
Этот образец из Википедии делает негамакс с Alpha / Beta Creuning.
Вам может помочь, получая наименование прямой:
Основа является MiniMax, буквальная реализация будет включать в себя 2 метода, которые по очереди (взаимно рекурсивно), 1 для каждой стороны.
Ленивые программисты превращают это в негамакс, один метод с стратегически размещенным
-
оператор.Alpha / Beta Creuning отслеживает окно лучших движений (над несколькими глубинами) для обнаружения мертвых ветвей.
Ваш playerTurn
используется для определения чьей очередь. В негамаксе вы можете получить это с глубины (итерации), нечетных или даже. Но было бы легче использовать 2 параметра (MyColor, OutomColor) и переключите их на каждом уровне.
Другие советы
Ваша функция MiniMax () должна помнить лучшее движение, которое он нашел до сих пор. Поэтому вместо этого кода:
/*So do I create a function max that returns the bigger of two doubles?*/
result = max(result, -miniMax(temp, iterations - 1));
Вы должны сделать что-то вроде этого:
/*So do I create a function max that returns the bigger of two doubles?*/
double score = -miniMax(temp, iterations - 1);
if (score > result)
{
result = score;
bestMove = i;
}
Конечно, вам нужна вариабельная «BestMove» и способ вернуть лучшее движение, найденное звонящему.
Добавить playerTurn
переменная как аргумент miniMax
, и вызов miniMax
который текущий проигрыватель движется изначально и рекурсивно.
Также, opponentSide
должен быть функцией playerTurn
.
Хорошее место для начала игры в поисках дерева Шахматный программирование Wiki. Отказ За ваш вопрос о ходу: я думаю, что наиболее распространено два максимальных функция. Разница между двумя максимальными функциями заключается в том, что один возвращает только оценку, а другой возвращает счет и лучший ход. Рекурсивный заказ звонка будет похоже на следующее:
maxWithBestMoveReturn(...) --> min(...) --> max(...) --> min(...)
Есть несколько хороших бумаг с псевдокодом для алгоритма альфа-бета:
На ваш вопрос в комментарии: и math.max (альфа, счет) или math.min (альфа, счет) - альфа логический там?!
Нет альфа - это окно, связанное в алгоритме Alpha Beta. Альфа-значение обновляется с новым значением. Поскольку Alpha и Beta поменяются рекурсивным вызовом функции негамакса. Переменная альфа ссылается на бета-переменную в следующем рекурсивном вызове.
Одна заметка к переменной Playerturn: MiniMax или Alpha-Beta Algorithm не нуждается в этой информации. Поэтому я бы дал информацию - кто следующий - в состав доски. Функции FindPossiblemoves и Boardeval получают всю необходимую информацию от структуры доски.
Одна заметка к рекурсивному нарушению: если я пойму свой код прямо, то у вас только один с iterations == o
. Отказ Я думаю, что это означает, что алгоритм достиг желаемой глубины. Но что, если не осталось никаких возможных движений, агоритм достигает этой глубины. Может быть, вы должны написать следующее:
vector<int> moves = findPossibleMoves(...);
if (!moves.size())
return boardEval(...);
В вашем псевдокоде переменная узла должна содержать всю информацию о текущей плате (или что-то). Эта информация будет включать чью поворот, чтобы двигаться.