Какой твой следующий ход?

18

Задача состоит в том, чтобы написать минимаксную функцию на выбранном вами языке, чтобы вывести следующий лучший ход в игре в крестики-нолики NxN с учетом текущего состояния доски . Входная плата может быть принята в виде матрицы, 2D-коллекции или чего-либо еще, что имеет смысл для вас, но соответствует правилам . Выход будет следующим лучшим ходом для того, чей ход будет в данный момент , где Х считается начатым .

Краткий обзор минимаксного алгоритма

Основная идея алгоритма минимакса состоит в том, чтобы перечислить все возможные результаты в виде DAG, а затем взвесить их с той выгодой, которую последовательность ходов приносит игроку, определяемой первым сделанным ходом. Все возможные исходы затем «разбиваются» на первый ход и оцениваются на основе суммы всех исходов (-1 для проигрыша, 0 для ничьей и 1 для выигрыша). В реализациях, где для игры требуется несколько игроков, вы перечисляете все возможные ходы игрока, а также все возможные ответы оппонентов. Например, в игре в крестики-нолики (после первого хода) есть 8 возможных первых ходов, которые вы можете сделать, и все они могут казаться равными при анализе только следующего хода. Но, перебирая все возможные результаты для каждого возможного набора шагов, которые приводят к окончательному результату, и суммируя их все,

Для лучшего, более глубокого и контекстуального описания алгоритма мини-макс в терминах крестики-нолики читайте здесь: http://neverstopbuilding.com/minimax

XKCD (только решение 3х3)

Все возможные ходы для игры в крестики-нолики 3х3.

Правила

  • Можно использовать любой язык, но внешние минимаксные библиотеки не допускаются.
  • Выходными данными может быть координата (0-n, 0-n) или число (1-n * n), указывающее лучший следующий ход.
    • В дополнение к этому вы должны быть в состоянии определить, когда лучшим вариантом является проигрыш или ничья, а не победа.
    • То, как вы обозначаете проигрыш или ничью, опять зависит от вас.
  • Ввод должен использовать традиционные X и O, и вы должны предположить, что X перемещается первым; пробелы могут быть представлены чем угодно.
  • Вы можете предположить, что любые входные данные, входящие в вашу программу, имеют n O и n + 1 X, другими словами, вы можете предположить, что вы получаете правильно сформированную доску.
  • Текущее состояние платы должно быть единственным входом в вашу программу. Если вы используете рекурсию, должны быть созданы вспомогательные методы для облегчения требований ввода. См. Https://codegolf.stackexchange.com/a/92851/59376 для уточнения.
  • Любое значение 10> = n> = 1 должно поддерживаться; если ваша программа «истекает» при n> 10, я нахожу это также приемлемым, поскольку некоторые языки имеют значительно меньшую вычислительную мощность (особенно при использовании веб-консолей).

судейство

  • Это код-гольф, поэтому выигрывает наименьшее количество байт программы, и стандартные лазейки повсеместно запрещены.
  • В случае ничьей победит программа, которая поддерживает наибольшее «n».

Пример входов

2х2

[[X,O]
 [-,-]]

Вывод: 2 или [0,1] (3 или [1,1] также могут быть правильными) (некоторая форма указания местоположения, произвольная, если вы можете легко объяснить используемый вами формат)


3x3

[[X,O,X]
 [O,X,-]
 [-,-,-]]

Выход: -1 (потеря)


Еще раз, любой входной формат, который вы хотите, разрешен, но X и O должны использоваться, предоставленные примеры не предназначены для того, чтобы ограничивать этот формат, просто чтобы вдохновить.

Урна волшебного осьминога
источник
Извините DJMCMayhem, я на самом деле пытался пометить эти вещи, но я не смог, так как я здесь новичок.
Волшебная урна осьминога
Бонус тоже убрал, ничего не добавил, кроме скуки.
Волшебная Урна Осьминога
Разрешен ли следующий выходной формат: диаграмма положения доски с каждым первоначально пустым пространством уникальным символом, указывающим, приводит ли игра там к выигрышу / проигрышу / ничьей (например, W, L и D)
Ton Hospel
1
В примере 3x3 O должен проигрывать независимо от того, что он играет, но вы говорите, что output должен быть [2,1], почему это так?
Дада
Отредактировано, хороший улов. Не знаю, о чем я думал, это был негативный пример.
Волшебная урна осьминога

Ответы:

8

Perl 101 98 байт

Включает +4в себя для-0p

Запустить с вводом на STDIN

tictactoe.pl
OXO
---
--X
^D

Выходные данные представляют собой ту же диаграмму, но с каждым ходом, который обновляется в соответствии со своим статусом, 1представляет выигрыш, 2представляет ничью и 3представляет убыток. Для этого случая это будет

OXO
223
21X

так что 3 хода ничья, 1 победа и 1 поражение (я обновлю решение, если этот формат вывода неприемлем, но основной код останется прежним)

tictactoe.pl:

#!/usr/bin/perl -0p
m%@{[map"O.{$_}"x"@-"."O|",1-/.(
)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2

Это уже мучительно медленно и использует много памяти для пустой доски 3 * 3 (почему на самом деле рекурсия не идет так глубоко. Должна быть некоторая утечка памяти). Добавление запоминания стоит 6 байт, но намного разумнее:

#!/usr/bin/perl -0p
$$_||=m%@{[map"O.{$_}"x"@-"."O|",1-/.(\n)(.)/,@-]}Z%sx||s%-%$_="$`X$'";y/XO/OX/;do$0%eg?/1/?3:1+/2/:2
Тон Хоспел
источник
Ничего себе, упуская из виду, что это pl и, вероятно, абсолютно не будет работать для n = 10 с большим количеством пустых ... Вы сделали обе вещи, которые я надеялся увидеть, что кто-то сделает. Строковый ввод и отображение результата для всех ходов, а не только для лучших. Браво.
Волшебная урна осьминога
Если одна рекурсивная функция «утечка», как может быть в порядке ??? Слишком высокий язык заставляет не видеть 32-битный регистр в CPU (или что-то в этом роде)
RosLuP
@RosLup Утечка в этом контексте не обязательно означает недостижимую потерянную память. Perl довольно своеобразен, когда он освобождает память, довольно часто делает это позже, чем вы ожидаете, и поэтому использует намного больше памяти, чем вы ожидаете. Он также имеет тенденцию выделять больше, чем необходимо, в расчете на то, что вы будете наращивать свои структуры данных. В этом случае использование «нормальной» рекурсии с функцией вместо злоупотребления do$0использует в 10 раз меньше памяти. Имейте в виду, этот случай настолько экстремальный, что может быть настоящей утечкой памяти.
Тон Хоспел
Не только один не видит регистры или базовые инструкции (из инструкций hlls), но теряет контроль над использованием памяти ... Для меня они не масштабируются ...
RosLuP
Прошло достаточно много времени, ты выиграл, мой мужчина, к сожалению, у нас не было больше попыток.
Волшебная Урна Осьминога
2

Javascript (ES6), 320 294 байта

(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

вход

1) Массив массива символов, описывающих текущую доску, например:

[['X', '-'], ['-', 'O']]

2) Целое число, описывающее текущий ход: 1 = X, -1 =O

Выход

Массив из:

  • массив, описывающий лучший ход в [x, y]формате
  • результат игры в виде целого числа: 1 = победа, -1 = проигрыш, 0 = ничья

пример

В следующем примере Xгарантированно выиграть, играя [1, 2].

let f =
(b,p,d,M,S=-2)=>(T=(p,q,r,s)=>b[p][q]==(n=b[r][s|0])&&n!='-',w=0,b.map((r,y)=>(l=r.length-1,m=15,r.map((c,x)=>(m&=8*T(l-x,x,l)+4*T(x,x,0)+2*T(x,y,0,y)+T(y,x,y))),w|=m)),w?-1:(b.map((r,y)=>r.map((c,x)=>S<1&&c=='-'&&(r[x]='O.X'[p+1],(s=-f(b,-p,1))>S&&(S=s,M=[x,y]),r[x]=c))),S=S+2?S:0,d?S:[M,S]))

console.log(JSON.stringify(f(
  [['O','X','O'],
   ['-','-','-'],
   ['-','-','X']],
  1
)));

СТРАННАЯ ИГРА. ЕДИНСТВЕННАЯ ПОБЕДА НЕ ДУМАЕТ.
КАК О ХОРОШЕЙ ИГРЕ ШАХМАТЫ?

Arnauld
источник
Молодцы, хорошая первая запись. Единственные замечания, которые у меня есть, - это возможность сохранять байты с заданной информацией «Х всегда будет двигаться первым». А ты пробовал с не 3х3 доской;)?
Волшебная Урна Осьминога
@carusocomputing - Не уверен, что понимаешь, что ты имеешь в виду под «X всегда будет двигаться первым». Его можно использовать для определения, какая сторона находится в движении, учитывая только плату, но вычисления, которые на самом деле будут стоить больше байтов; так что я предполагаю, что вы говорите о чем-то другом. И да, я провел несколько тестов с немного большими платами. Это должно работать, как и ожидалось, до тех пор, пока ... эээ ... не слишком много пустых позиций. :-)
Арно
Задача говорит The current state of the board must be the only input to your program. Вашему коду нужны два входа, что нарушает это правило.
Дада
1
@ Дада - мне было интересно, но я предположил, что активный цвет является частью состояния доски (точно так же, как шахматная позиция всегда имеет активный цвет + пассивный квадрат + наличие рокировки). Так что я полагаю, что ОП должен прояснить этот момент. (И если вы правы, это звучит как ненужная дополнительная сложность, ИМХО.)
Арно
1
Ммм .. мне очень нравится объяснение состояния совета в его ответе. Подумав об этом, некоторые ланегии могут использовать в качестве входных данных только строки, поскольку такую ​​доску, как XXOOXO-OO, будет трудно расшифровать при малом числе байтов без дополнительной информации, такой как размеры платы. Я разрешаю любые дополнительные входные данные, которые влияют на состояние доски, хотя я все еще думаю, что информация «предположим, что Х движется первым» отличается от «учитывая, кто это делает». Некоторые языки будут использовать это как допущение;).
Волшебная Урна Осьминога