В реализации tic-tac-toe я предполагаю, что сложной задачей является определение лучшего движения, которое будет играть машина.
Какими алгоритмами можно заниматься? Я изучаю реализации от простого до сложного. Как мне решить эту часть проблемы?
Какой алгоритм для игры tic-tac-toe можно использовать для определения "лучшего движения" для ИИ?
Ответ 1
Стратегия из Википедии для игры в идеальную игру (победа или галстук каждый раз) кажется простым псевдокодом:
Цитата из Википедия (стратегия Tic Tac Toe #)
Игрок может сыграть в идеальную игру Tic-tac-toe (чтобы выиграть или, по крайней мере, привлечь), если они выбирают первый доступный ход из следующего списка, каждый оборот, как используется в Newell и Simon 1972 tic- tac-toe. [6]
Win: Если у вас есть две строки, играйте третью, чтобы получить три строки.
Блок: если противник имеет две строки, сыграйте третью, чтобы заблокировать их.
Вилка: создайте возможность, в которой вы можете выиграть двумя способами.
Виджет блокировки противников:
Вариант 1: Создайте два ряда, чтобы заставить противник в защиту, как долго поскольку это не приводит к их созданию вилкой или победой. Например, если "X" имеет угол, "O" имеет центр, и "X" также имеет противоположный угол, "O" не должен играть в углу, чтобы выиграть. (Игра в угол в этом сценарий создает вилку для "X" для победа.)
Вариант 2: если есть конфигурация где противник может развить, блокировать это fork.
Центр: воспроизведение центра.
Противоположный угол: если противник находится в углу, сыграйте противоположное угол.
Пустой угол: играйте в пустой угол.
Пустая сторона: играйте на пустой стороне.
Признание того, как выглядит ситуация "вилки", может быть сделано грубым способом, как это было предложено.
Примечание: "идеальный" противник - это отличное упражнение, но в конечном счете не стоит "играть" против. Однако вы могли бы изменить приоритеты, чтобы дать характерные недостатки личностям противника.
Ответ 2
Что вам нужно (для tic-tac-toe или гораздо более сложной игры, такой как Chess) является минимаксный алгоритм или его немного больше сложный вариант, обрезка альфа-бета. Обыкновенный наивный минимакс отлично справится с игрой с таким маленьким поисковым пространством, как tic-tac-toe.
Вкратце, то, что вы хотите сделать, это не поиск хода, который имеет наилучший возможный результат для вас, а скорее переход, где наихудший возможный результат максимально эффективен. Если вы предполагаете, что ваш оппонент играет оптимально, вы должны предположить, что они сделают для вас худший для вас ход, и поэтому вам нужно сделать ход, который минимизирует их максимальный выигрыш.
Ответ 3
Метод грубой силы для создания каждой единственной возможной доски и подсчета ее на основе плат, которые он позже производит дальше по дереву, не требует большой памяти, особенно если вы узнаете, что вращение на 90 градусов является избыточным, вертикальной, горизонтальной и диагональной оси.
Как только вы доберетесь до этой точки, в описании дерева есть что-то вроде менее 1k данных, чтобы описать результат и, следовательно, лучший способ для компьютера.
-Adam
Ответ 4
Типичный алгоритм крестики-нолики должен выглядеть следующим образом:
Доска: вектор из девяти элементов, представляющий доску. Мы храним 2 (с указанием пустого), 3 (с указанием X) или 5 (с указанием O). Поворот: целое число, указывающее, какой ход игры собирается сыграть. 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 opponents 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.
Я использовал это. Дайте мне знать, что вы, ребята, чувствуете.
Ответ 5
Поскольку вы имеете дело с матрицей 3x3 возможных местоположений, было бы легко просто написать поиск по всем возможностям, не обременяя вас вычислительной властью. Для каждого открытого пространства вычисляйте все возможные результаты после того, как они отмечают это пространство (рекурсивно, я бы сказал), а затем используйте ход с наибольшими возможностями выигрыша.
Оптимизация этого была бы пустой тратой усилий. Хотя некоторые простые могут быть:
- Сначала проверьте возможные выигрыши для другая команда, заблокировать первую вы найдете (если есть 2 игры во всяком случае).
- Всегда держите центр, если он открыт (и в предыдущем правиле нет кандидатов).
- Возьмите углы впереди сторон (опять же, если предыдущие правила пустые)
Ответ 6
У вас может быть игра AI в некоторых примерах игр, чтобы учиться. Используйте контролируемый алгоритм обучения, чтобы помочь ему.
Ответ 7
Попытка без использования игрового поля.
- чтобы выиграть (ваш двойной)
- если нет, не потерять (противник дважды)
- Если нет, у вас уже есть вилка (есть двойной двойной)
- если нет, если у противника есть вилка
- поиск в блокирующих точках для возможных двойных и fork (конечная победа)
- если не поиск forks в блокирующих точках (что дает противнику самые проигрышные возможности)
- если не только блокировать точки (не терять)
- если не поиск двойных и fork (конечная победа)
- если не поиск только для вилок, которые дают противнику самые проигрышные возможности.
- если не искать только двойной
- если не тупик, галстук, случайный.
- если нет (это означает ваш первый ход)
- если это первый ход игры;
- дает противнику самую проигрышную возможность (алгоритм приводит только к углам, что дает 7 очков потери возможности противнику)
- или для взлома скуки просто случайно.
- если это второй ход игры;
- найти только те потери (дает немного больше вариантов)
- или найдите точки в этом списке, которые имеют лучший выигрышный шанс (это может быть скучно, потому что это приводит к появлению только всех углов или смежных углов или центра).
- если это первый ход игры;
Примечание. Если у вас есть двойные и вилки, проверьте, дает ли ваш двойник двойнику. Если он дает, проверьте, включен ли ваш новый обязательный пункт в список разметки.
Ответ 8
Ранг каждого квадрата с числовыми баллами. Если взять квадрат, перейдите к следующему выбору (отсортированный в порядке убывания по рангу). Вам нужно будет выбрать стратегию (есть два основных для первого и трех (я думаю) для второго). Технически вы можете просто запрограммировать все стратегии, а затем выбрать один случайным образом. Это сделало бы для менее предсказуемого противника.
Ответ 9
Этот ответ предполагает, что вы понимаете реализацию совершенного алгоритма для P1 и обсуждает, как добиться победы в условиях против обычных человеческих игроков, которые будут делать некоторые ошибки чаще, чем другие.
Игра, конечно же, должна закончиться ничьей, если оба игрока будут играть оптимально. На человеческом уровне игра P1, играющая в углу, выигрывает гораздо чаще. По какой-то психологической причине P2 приманивается к мысли, что играть в центре не так важно, что для них является неудачным, поскольку это единственный ответ, который не создает выигрышную игру для P1.
Если P2 правильно блокируется в центре, P1 должен играть в противоположном углу, потому что, по любой психологической причине, P2 предпочтет симметрию игры в углу, что снова создает для них проигрышную карточку.
Для любого перемещения P1, которое может сделать для начального хода, есть шаг P2, который может создать выигрыш для P1, если оба игрока будут играть оптимально после этого. В этом смысле P1 может играть везде. Движения края слабее в том смысле, что наибольшая часть возможных ответов на этот ход вызывает ничью, но есть еще ответы, которые создадут выигрыш для P1.
Эмпирически (точнее, анекдотически) лучшие стартовые шаги P1 кажутся первым угловым, вторым центром и последним ребром.
Следующим вызовом, который вы можете добавить лично или через графический интерфейс, является не отображение платы. Человек может определенно запомнить все состояние, но добавленная проблема приводит к предпочтению симметричных плат, которые требуют меньше усилий, чтобы запомнить, что привело к ошибке, которую я описал в первой ветке.
Я очень люблю вечеринки, я знаю.
Ответ 10
Крестики-нолики адаптация к минимальному максимальному алгоритму
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
}