Как начать с Гомоку?

Question

Я читал о Gomoku, что это может быть реализовано с использованием алгоритмов Minimax и Alpha-Beta Pruning. Итак, я прочитал эти алгоритмы и теперь понимаю, как будет решаться игра. Но когда я сел за код, я столкнулся с проблемой, как подойти к нему.

Как в,

• Как спроектировать функции-прототипы, такие как getNextMove или Max(Move)?
• Как будет искать следующий ход?
• До того, когда я должен применить минимаксный алгоритм.
• Я знаю, что могу найти код в Интернете, но я хочу сделать это сам.

Может кто-нибудь, пожалуйста, укажите мне в правильном направлении?

Answer 1

Алгоритм минимакса, представленный в учебнике, обычно применяется в простых играх, например, в крестики-нолики, где конечные состояния достижимы всего за несколько ходов между минимальным игроком и максимальным игроком. Однако для Гомоку невозможно достичь всех конечных состояний. Почему мы должны достичь конечных состояний? Нам нужна оценка для движения, то есть, хорошо ли это движение или нет.

Итак, ваш первый шаг - разработать функцию оценки хода, которая скажет вам, сколько вы получите, если сделаете один ход. например, у вас есть 3 в ряд, движение по этому ряду, чтобы сделать 4 будет очень ценным.

Предположим, что у вас есть очень умная функция оценки, тогда вы сможете каждый раз находить оптимальный ход без поиска. Поэтому, прежде чем вы сделаете какую-либо минимальную, альфа-бета-версию, вы, вероятно, разработаете хорошую функцию оценки. Хорошим примером является исходный код Emacs' gomoku, в котором есть хороший AI-плеер без использования поиска.

Далее вы переходите на мин-макс и альфа-бета.

Кажется, я не ответил на ваши вопросы. На самом деле мне не нужно. Я предполагаю, что вы знаете детали min-max или даже альфа-бета-поиска tic-tac-tao. Разработав функцию оценки, вы получите лучшее представление о гомоку и разработаете алгоритм поиска для него так же, как вы можете сделать это сейчас для tic-tac-tou.