Насколько я понял, ваша основная проблема заключается в следующем: вам показали, как использовать минимакс в ситуации, когда макс/мин идут в цикле, и теперь у вас есть игра, в которой иногда один игрок может делать несколько ходов подряд.
Я объясню вам общий подход, который работает практически для любой игры, а затем добавлю пару вещей, которые можно сделать по-другому для манкалы.
Итак, общий подход
Стандартный минимакс выглядит так:
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val)
return bestValue
Где вы инициализируете минимаксный вызов с помощью max/min, а затем он постоянно меняется. В вашем случае вам нужно всего лишь добавить одну крошечную проверку.
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
# here is a small change
if freeTurn(child):
isMax := TRUE
else:
isMax := FALSE
val := minimax(child, depth - 1, isMax)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
# here is a small change
if freeTurn(child):
isMax := FALSE
else:
isMax := TRUE
val := minimax(child, depth - 1, isMax)
bestValue := min(bestValue, val)
return bestValue
Где ваша функция freeTurn возвращает вам, есть ли у вас свободный ход после вашего текущего хода. Обратите внимание, что для этого алгоритма нет разницы, можете ли вы сделать только 2 хода подряд или 5 ходов подряд.
О Манкале
Есть много вариаций манкалы, но коэффициент ветвления в игре довольно мал (в той, которую я знаю, ‹= 6). Теперь предположим, что у вас есть три хода A, B, C, D, а ход C позволяет сыграть еще раз. Из позиции C можно делать ходы C1, C2. Таким образом, вы можете комбинировать их (C + C1, C + C2) и рассматривать их как один ход (необходимо провести небольшой учет, чтобы помнить, что на самом деле это два хода). Итак, прямо сейчас вы получаете свои минимальные итерации, в которых у вас есть не 4, а 5 ходов: A, B, C + C1, C + C2, D. На самом деле нет ничего плохого в том, чтобы использовать этот подход для игр с большим коэффициентом ветвления.
person
Salvador Dali
schedule
21.10.2015
