Я полагаю, что в реализации крестиков-ноликов сложная часть состоит в том, чтобы определить лучший ход, который будет выполняться машиной.
Какие алгоритмы можно использовать? Я изучаю реализации от простого к сложному. Как мне решить эту часть проблемы?
Стратегия идеальной игры из Википедии (выигрыш или ничья каждый раз) кажется простым псевдокодом:
Цитата из Википедии (Крестики-нолики#Стратегия)
Игрок может сыграть идеальную игру в крестики-нолики (выиграть или, по крайней мере, сыграть вничью), если он каждый ход выбирает первый доступный ход из следующего списка, как это используется в крестиках-ноликах Ньюэлла и Саймона 1972 года. программа.[6]
Выигрыш: Если у вас есть две карты подряд, сыграйте третью, чтобы получить три карты подряд.
Блок: если у противника есть две подряд, сыграйте третью, чтобы заблокировать их.
Вилка: создайте возможность, в которой вы можете выиграть двумя способами.
Блокировать вилку противника:
Вариант 1: Создайте две подряд, чтобы заставить противника защищаться, если это не приведет к созданию вилки или выигрышу. Например, если у «X» есть угол, у «O» есть центр, а у «X» есть еще и противоположный угол, «O» не должен играть в угол, чтобы выиграть. (Разыгрывание углового в этом сценарии создает развилку для победы «X».)
Вариант 2: Если есть конфигурация, при которой противник может разветвляться, заблокируйте эту разветвление.
Центр: Играйте в центре.
Противоположный угол: если противник находится в углу, играйте в противоположном углу.
Пустой угол: сыграйте в пустой угол.
Пустая сторона: Играйте за пустую сторону.
Распознавание того, как выглядит ситуация «форка», может быть выполнено методом грубой силы, как было предложено.
Примечание: «идеальный» противник — это хорошее упражнение, но, в конечном счете, с ним не стоит «играть». Однако вы можете изменить указанные выше приоритеты, чтобы дать характерные слабости персонажам противника.
Что вам нужно (для крестиков-ноликов или гораздо более сложной игры, такой как шахматы), так это минимаксный алгоритм или его несколько более сложный вариант, альфа-бета-обрезка. Однако обычный наивный минимакс вполне подойдет для игры с таким маленьким пространством поиска, как крестики-нолики.
Короче говоря, вам нужно искать не ход, который дает наилучший возможный для вас результат, а ход, в котором наихудший возможный исход является как можно более хорошим. Если вы предполагаете, что ваш оппонент играет оптимально, вы должны исходить из того, что он сделает ход, наихудший для вас, и, следовательно, вы должны сделать ход, который минимизирует его МАКСИМАЛЬНЫЙ выигрыш.
Метод грубой силы для создания каждой отдельной доски и подсчета очков на основе досок, которые он позже создает дальше по дереву, не требует много памяти, особенно если вы понимаете, что повороты доски на 90 градусов избыточны, как и перевороты по вертикали, горизонтальная и диагональная оси.
Как только вы дойдете до этой точки, в древовидной диаграмме будет что-то вроде менее 1 КБ данных для описания результата и, следовательно, лучшего хода для компьютера.
-Адам
Типичный алгоритм для крестиков-ноликов должен выглядеть так:
Board : вектор из девяти элементов, представляющий доску. Мы сохраняем 2 (указывает на пробел), 3 (указывает на X) или 5 (указывает на O). Turn: Целое число, указывающее, какой ход игры будет сыгран. 1-й ход будет обозначен цифрой 1, последний - цифрой 9.
Алгоритм
Основной алгоритм использует три функции.
Make2: возвращает 5, если центральная клетка доски пуста, т. е. если board[5]=2. В противном случае эта функция возвращает любой неугловой квадрат (2, 4, 6 or 8).
Posswin(p): возвращает 0, если игрок p не может выиграть своим следующим ходом; в противном случае возвращается номер клетки, представляющей собой выигрышный ход. Эта функция позволит программе как выигрывать, так и блокировать победу противников. Эта функция работает путем проверки каждой из строк, столбцов и диагоналей. Перемножая значения каждого квадрата вместе для всей строки (или столбца, или диагонали), можно проверить возможность выигрыша. Если продукт 18 (3 x 3 x 2), то X может выиграть. Если произведение равно 50 (5 x 5 x 2), то О может выиграть. Если найден выигрышный ряд (столбец или диагональ), в нем может быть определен пустой квадрат, и эта функция возвращает номер этого квадрата.
Go (n): делает ход на поле n. эта процедура устанавливает для доски [n] значение 3, если ход нечетный, или 5, если ход четный. Это также увеличивает ход на один.
Алгоритм имеет встроенную стратегию для каждого хода. Он делает ход с нечетным номером, если играет X, и ход с четным номером, если играет O.
Turn = 1 Go(1) (upper left corner).
Turn = 2 If Board[5] is blank, Go(5), else Go(1).
Turn = 3 If Board[9] is blank, Go(9), else Go(3).
Turn = 4 If Posswin(X) is not 0, then Go(Posswin(X)) i.e. [ block opponent’s win], else Go(Make2).
Turn = 5 if Posswin(X) is not 0 then Go(Posswin(X)) [i.e. win], else if Posswin(O) is not 0, then Go(Posswin(O)) [i.e. block win], else if Board[7] is blank, then Go(7), else Go(3). [to explore other possibility if there be any ].
Turn = 6 If Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else Go(Make2).
Turn = 7 If Posswin(X) is not 0 then Go(Posswin(X)), else if Posswin(X) is not 0, then Go(Posswin(O)) else go anywhere that is blank.
Turn = 8 if Posswin(O) is not 0 then Go(Posswin(O)), else if Posswin(X) is not 0, then Go(Posswin(X)), else go anywhere that is blank.
Turn = 9 Same as Turn=7.
Я использовал его. Дайте мне знать, как вы, ребята, себя чувствуете.
Поскольку вы имеете дело только с матрицей возможных местоположений 3x3, было бы довольно легко просто написать поиск по всем возможностям, не нагружая вычислительную мощность. Для каждого открытого пространства вычислите все возможные результаты после того, как отметите это пространство (я бы сказал, рекурсивно), а затем используйте ход с наибольшим количеством шансов на победу.
На самом деле оптимизация этого была бы пустой тратой усилий. Хотя некоторые простые могут быть:
Вы можете заставить ИИ играть самого себя в некоторых примерах игр, чтобы учиться. Используйте контролируемый алгоритм обучения, чтобы помочь ему.
Попытка без использования игрового поля.
Примечание: Когда у вас есть дубль и вилки, проверьте, дает ли ваш дубль противнику дубль. Если он дает, проверьте, включен ли ваш новый обязательный балл в ваш список вилок.
Оцените каждый из квадратов числовыми баллами. Если квадрат взят, переходите к следующему выбору (в порядке убывания ранга). Вам нужно будет выбрать стратегию (есть две основные для первого и три (я думаю) для второго). Технически, вы можете просто запрограммировать все стратегии, а затем выбрать одну наугад. Это сделало бы соперника менее предсказуемым.
Этот ответ предполагает, что вы понимаете реализацию идеального алгоритма для P1, и обсуждает, как добиться победы в условиях против обычных игроков, которые будут делать одни ошибки чаще, чем другие.
Игра, конечно, должна закончиться вничью, если оба игрока играют оптимально. На человеческом уровне игра P1 в углу приносит гораздо больше выигрышей. По какой-то психологической причине P2 заставляют думать, что игра в центре не так уж важна, что для них неудачно, поскольку это единственный ответ, который не создает выигрышной игры для P1.
Если P2 правильно блокирует в центре, P1 должен сыграть в противоположный угол, потому что опять же, по какой-то психологической причине, P2 предпочтет симметричную игру в углу, что опять-таки приведет к проигрышу для него.
Для любого хода, который P1 может сделать в качестве начального хода, есть ход, который может сделать P2, который создаст выигрыш для P1, если после этого оба игрока будут играть оптимально. В этом смысле P1 может играть где угодно. Краевые ходы являются самыми слабыми в том смысле, что наибольшая часть возможных ответов на этот ход приводит к ничьей, но все же есть ответы, которые обеспечат победу P1.
Эмпирически (точнее, анекдотически) лучшими начальными ходами P1 кажутся первый угол, второй центр и последний край.
Следующая проблема, которую вы можете добавить лично или через графический интерфейс, — не отображать доску. Человек определенно может запомнить все состояние, но дополнительная проблема приводит к тому, что он предпочитает симметричные доски, которые требуют меньше усилий для запоминания, что приводит к ошибке, которую я описал в первой ветке.
Я очень веселюсь на вечеринках, я знаю.
let gameBoard: [
[null, null, null],
[null, null, null],
[null, null, null]
]
const SYMBOLS = {
X:'X',
O:'O'
}
const RESULT = {
INCOMPLETE: "incomplete",
PLAYER_X_WON: SYMBOLS.x,
PLAYER_O_WON: SYMBOLS.o,
tie: "tie"
}
Нам понадобится функция, которая может проверять результат. Функция проверит последовательность символов. Каким бы ни было состояние доски, результатом будет один из 4 вариантов: либо Незавершенно, либо игрок Х выиграл, либо игрок О выиграл, либо ничья.
function checkSuccession (line){
if (line === SYMBOLS.X.repeat(3)) return SYMBOLS.X
if (line === SYMBOLS.O.repeat(3)) return SYMBOLS.O
return false
}
function getResult(board){
let result = RESULT.incomplete
if (moveCount(board)<5){
return result
}
let lines
//first we check row, then column, then diagonal
for (var i = 0 ; i<3 ; i++){
lines.push(board[i].join(''))
}
for (var j=0 ; j<3; j++){
const column = [board[0][j],board[1][j],board[2][j]]
lines.push(column.join(''))
}
const diag1 = [board[0][0],board[1][1],board[2][2]]
lines.push(diag1.join(''))
const diag2 = [board[0][2],board[1][1],board[2][0]]
lines.push(diag2.join(''))
for (i=0 ; i<lines.length ; i++){
const succession = checkSuccesion(lines[i])
if(succession){
return succession
}
}
//Check for tie
if (moveCount(board)==9){
return RESULT.tie
}
return result
}Our getBestMove function will receive the state of the board, and the symbol of the player for which we want to determine the best possible move. Our function will check all possible moves with the getResult function. If it is a win it will give it a score of 1. if it's a loose it will get a score of -1, a tie will get a score of 0. If it is undetermined we will call the getBestMove function with the new state of the board and the opposite symbol. Since the next move is of the oponent, his victory is the lose of the current player, and the score will be negated. At the end possible move receives a score of either 1,0 or -1, we can sort the moves, and return the move with the highest score.
const copyBoard = (board) => board.map(
row => row.map( square => square )
)
function getAvailableMoves (board) {
let availableMoves = []
for (let row = 0 ; row<3 ; row++){
for (let column = 0 ; column<3 ; column++){
if (board[row][column]===null){
availableMoves.push({row, column})
}
}
}
return availableMoves
}
function applyMove(board,move, symbol) {
board[move.row][move.column]= symbol
return board
}
function getBestMove (board, symbol){
let availableMoves = getAvailableMoves(board)
let availableMovesAndScores = []
for (var i=0 ; i<availableMoves.length ; i++){
let move = availableMoves[i]
let newBoard = copyBoard(board)
newBoard = applyMove(newBoard,move, symbol)
result = getResult(newBoard,symbol).result
let score
if (result == RESULT.tie) {score = 0}
else if (result == symbol) {
score = 1
}
else {
let otherSymbol = (symbol==SYMBOLS.x)? SYMBOLS.o : SYMBOLS.x
nextMove = getBestMove(newBoard, otherSymbol)
score = - (nextMove.score)
}
if(score === 1) // Performance optimization
return {move, score}
availableMovesAndScores.push({move, score})
}
availableMovesAndScores.sort((moveA, moveB )=>{
return moveB.score - moveA.score
})
return availableMovesAndScores[0]
}Алгоритм в действии, Github, Более подробное объяснение процесса
