Требует ли Alpha Beta / minimax, чтобы каждый узел был полной копией игровой доски? - PullRequest
Новая
       56

Требует ли Alpha Beta / minimax, чтобы каждый узел был полной копией игровой доски?

1 голос
/ 12 января 2020

Это не вопрос конкретного языка c, но ради разговора я сейчас работаю в C# 7.

В течение многих лет я успешно реализовал алгоритм отсечения альфа-бета-версии. (даже в PASCAL, 35 лет go:)

Каждый раз я создавал полуглубокие копии (обсуждаемые ниже) состояния игры, которое повторяется для каждого узла. Я часто задавался вопросом, нужно ли это, и, может быть, я не совсем понимаю алгоритм.

В сети полно запросов о помощи для TicTacToe, что заставляет меня думать, что это должно быть обычным школьным заданием. вопрос - какие засорения какие-то поиски по этому довольно основному c топи c.

полуглубоким копиям ... мне кажется, что каждый узел должен знать:

  • полное состояние доски
  • игрок, чей ход
  • состояние игры - ie: {игра, победа игрока1, победа игрока2, ничья }

Мой вопрос: нужна ли каждому узлу собственная копия платы ? ... например, шахматы имеют сетку 8x8 ... есть ли что-то более тонкое в алгоритме, или каждый из этих узлов нуждается в отдельном снимке состояния платы? Есть ли какой-нибудь классный способ (кроме copy и apply-возможный-переместить), который узлы могут использовать для получения своего состояния от своего родителя?

Возможно, кто-то может объяснить или указать на "чтение" это, фиктивная "запись, или просто подтвердите, что мне нужно создавать эти экземпляры, как я пытался описать, с каждым рекурсивным вызовом, имеющим свою собственную копию игровой доски в памяти.

Я понимаю, что за последние несколько десятилетий память стала дешевой ... но комбинаторный взрыв все еще остается главной темой c. Приветствия.

1 Ответ

0 голосов
/ 13 января 2020

Я не уверен, отвечает ли это на ваш вопрос. Но не могли бы вы вместо того, чтобы делать копию каждый ход, делать ход, делать рекурсивный вызов, а затем отменять ход? Что-то вроде: 

board.make_move(move)
eval = minimax(board, ....)
board.unmake_move(move)
...