Tic-Tac-латинский!

Это правдивая история, поэтому имена были изменены.

Мой латинский учитель, мистер Латино, создал свой собственный (без шуток) вариант «крестики-нолики». Давайте назовем это тик-так-латин. Игра проста, по сути, это крестики-нолики, сыгранные по четыре на четыре.

Официальное объявление правила

Линия - это либо строка, столбец или диагональ. Есть два символа, «X» и «O», но один или оба могут быть заменены другим символом.
Вы получаете одно очко, когда у вас есть три символа и один другой персонаж.

Эти договоренности оценивают:

--- O
-O--
XXXO
XOOX

O -XX
- О -
- Х -
--- O

Это не оценка:

----
XXXX
----
ОООО

----
xxx-
----
OOO-

Игра выигрывается, когда у одного игрока больше очков, чем у другого. Игра является ничьей, только если доска заполнена.

Вызов

Решите эту игру. Ваша задача состоит в том, чтобы обеспечить способ гарантировать победу или ничью, в зависимости от того, какой результат является оптимальным.

Ваше решение может выбрать начало или второе (и поэтому может выбрать его символ). Не обязательно реализовывать интерактивную игру, в которой пользовательский ввод перемещается, а соответствующий дисплей изменяется. Это также может быть функция или программа, которая принимает входные данные в качестве игрового состояния и выводит новую доску или описание их хода . Любой из вариантов должен быть запущен в течение примерно десяти секунд за каждый сделанный ход

---

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

---

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

Победитель выбирается по списку, пока не будет выбран один победитель.

• Кратчайшая решаемая реализация, которая всегда выигрывает
  
• Кратчайшая реализация
  

Perl, 147 байт (не конкурирует, занимает больше 10 секунд за ход)

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

Программа играет X. Будет играть в идеальную игру.

Введите плату на STDIN, например:

tictaclatin.pl
-X-O
-X--
X-X-
O--O
^D

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

В этом примере вывод будет:

1O1X
1O33
O3O3
X33X

Таким образом, позиция является победой, Xесли он играет в 3-х точках по верху и слева. Все остальные ходы проигрывают.

Этот запутанный вывод на самом деле удобен, если вы хотите знать, как продолжается игра после хода. Поскольку программа всегда играет, Xвы должны поменяться местами Xи Oпосмотреть ходы O. Здесь, например, довольно ясно, что Xвыигрывает, играя в левом верхнем углу, но что если Xиграть в третьей позиции вдоль верха? Просто скопируйте вывод, поместите Oвместо выбранного движения ход и замените все остальные числа -снова, вот так:

-OOX
-O--
O-O-
X--X

В результате чего:

3XXO
3X33
X3X3
O33O

Очевидно, что каждый ход Oдолжен проигрывать, так как же он проигрывает, если играет в левом верхнем углу? Снова сделайте это, поместив Oверхний левый угол и заменив цифры на -:

OXXO
-X--
X-X-
O--O

Предоставление:

XOOX
1O33
O3O3
X33X

Так что у Х есть только один способ победить:

XOOX
OO--
O-O-
X--X

дающий

OXXO
XX33
X3X3
O33O

Ситуация для Oостается безнадежной. Теперь легко увидеть, что каждый ход позволяет Xсразу же выиграть. Давайте хотя бы попробуем пойти на 3 О подряд:

OXXO
XX--
X-X-
O-OO

Предоставление:

XOOX
OO13
O3O3
X3XX

Xиграет единственный выигрышный ход (обратите внимание, что это делает XXXOвдоль третьего столбца:

XOOX
OOO-
O-O-
X-XX

Вот вывод:

OXXO
XXX-
X-X-
O-OO

потому что игра была уже закончена. Вы можете увидеть победу в третьей колонке.

Актуальная программа tictaclatin.pl:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

Применительно к пустой доске это оценивает 9506699 позиций, что занимает 30 Гб и 41 минуту на моем компьютере. Результат:

2222
2222
2222
2222

Таким образом, каждый стартовый ход ничья. Так что игра ничья.

Чрезвычайное использование памяти в основном вызвано использованием рекурсии do$0. Для использования этой 154-байтовой версии с использованием простой функции требуется 3 Гб и 11 минут:

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/sx;$@<=>0||s%-%$_="$`O$'";$$_||=2+&f%eeg&&(/1/||/2/-1)}f

что более терпимо (но все же слишком много, что-то должно все еще течь память).

Объединение нескольких ускорений приводит к этой 160-байтовой версии (5028168 позиций, 4 минуты и 800M для пустой доски):

#!/usr/bin/perl -0p
sub f{y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}f

Последний использует 0для победы (не путайте с O), 1для ничьей и 2для поражения. Вывод этого также более запутанный. Он заполняет выигрышный ход для X в случае выигрыша без замены цвета, но если входная игра уже была выиграна, он все равно выполняет замену цвета и не выполняет ни одного хода.

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

В принципе, эта 146-байтовая версия также должна работать:

#!/usr/bin/perl -0p
y/XO/OX/,$@=-$@while/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^/sx,--$|;$@<=>0||s%-%$_="$`O$'";$$_||=2+do$0%eg&&(/1/||/2/-1)

но на моей машине это вызывает ошибку Perl и сбрасывает ядро.

Все версии в принципе все еще будут работать, если $$_||=удалено 6-байтовое позиционное кэширование, но оно использует столько времени и памяти, что работает только для почти заполненных плат. Но в теории по крайней мере у меня есть 140-байтовое решение.

Если вы положили $\=(стоимость: 3 байта) непосредственно перед тем, за $@<=>0каждой выходной платой будет следовать статус всей платы: 1для Xвыигрышей, 0для розыгрыша и -1для проигрыша.

Вот интерактивный драйвер, основанный на самой быстрой версии, упомянутой выше. У водителя нет логики, когда игра заканчивается, поэтому вы должны остановить себя. Гольф-код знает, хотя. Если предложенный ход возвращается без -замены, игра окончена.

#!/usr/bin/perl
sub f{
    if ($p++ % 100000 == 0) {
        local $| = 1;
        print ".";
    }
y/XO/OX/,$@=-$@while$|-=/(@{[map{(O.".{$_}O"x3)=~s%O%Z|$`X$'|Z%gr}0,3..5]})(?{$@++})^|$/osx;$@<=>0||s%-%$_="$`O$'";$a{$_}//=&f+1or return 1%eeg&&/1/-1}

# Driver
my $tomove = "X";
my $move = 0;
@board = ("----\n") x 4;
while (1) {
    print "Current board after move $move ($tomove to move):\n  ABCD\n";
    for my $i (1..4) {
        print "$i $board[$i-1]";
    }
    print "Enter a move like B4, PASS (not a valid move, just for setup) or just press enter to let the program make suggestions\n";
    my $input = <> // exit;
    if ($input eq "\n") {
        $_ = join "", @board;
        tr/OX/XO/ if $tomove eq "O";
        $p = 0;
        $@="";
        %a = ();
        my $start = time();
        my $result = f;
        if ($result == 1) {
            tr/OX/XO/ if $tomove eq "O";
            tr/012/-/;
        } else {
            tr/OX/XO/ if $tomove eq "X";
            tr/012/123/;
        }
        $result = -$result if $tomove eq "O";
        my $period = time() - $start;
        print "\nSuggested moves (evaluated $p positions in $period seconds, predicted result for X: $result):\n$_";
        redo;
    } elsif ($input =~ /^pass$/i) {
        # Do nothing
    } elsif (my ($x, $y) = $input =~ /^([A-D])([1-4])$/) {
        $x = ord($x) - ord("A");
        --$y;
        my $ch = substr($board[$y],$x, 1);
        if ($ch ne "-") {
            print "Position already has $ch. Try again\n";
            redo;
        }
        substr($board[$y],$x, 1) = $tomove;
    } else {
        print "Cannot parse move. Try again\n";
        redo;
    }
    $tomove =~ tr/OX/XO/;
    ++$move;
}

JavaScript (ES6) 392 байта

a=>b=>(c="0ed3b56879a4c21f",r=[],k=f=>r.push([a.filter(f),b.filter(f)]),[0,1,2,3].map(i=>k(n=>n%4==i)+k(n=>(n/4|0)==i)),k(n=>n%5==0),k(n=>n&&n-15&&!(n%3)),g=r.find(o=>(o[0].length==1&&o[1].length==2)||(o[0].length==2&&o[1].length==1)),g?parseInt(c[30-[...g[0],...g[1]].map(i=>parseInt(c[i],16)).reduce((p,c)=>p+c)],16):[...a,...b].indexOf(15-a[0])+1?15-a.find(i=>b.indexOf(15-i)==-1):15-a[0])

использование

«Бот» будет играть вторым.

Нарисуйте сетку 4x4, которая пронумерована так:

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 | 15 |
+----+----+----+----+

Давайте запустим это в консоли браузера: просто поместите f=перед кодом

Итак, если я хочу начать с 1, я бы побежал, f([1])([])и это даст мне 14.

Хороший ход ... Что если я сыграю 2потом? f([2,1])([14]), Это вернется 13.

Дай мне попробовать сдаться. Играть 3. f([3,2,1])([14,13]), Ох 0! Ты поймал меня!

Играть 0? f([0,2,1])([14,13]), 15Хорошо, давайте продолжим играть ...

Запись

1. Играйте в интерактивном режиме. Начните с f([your-step])([]).

2. Подготовьте ваш следующий шаг. (См. Демонстрацию выше)

3. Помогите «боту» ввести свои шаги. Это не даст вам хороших результатов, если вы дадите ему случайную настройку. (Как f([1,2,4])([14,12])даст 14- Эй, бот хотел играть 13на своем втором ходу!

Краткое содержание

Пока вы не сдаетесь, бот будет играть зеркальным движением.

Спасибо @EHTproductions за сообщение, что я неправильно понял правила игры и советы по игре в гольф: P

Теперь он также обнаружит, есть ли у него мат. Если да, заблокируйте это!

Его приоритеты: Блок> Зеркало> (запасной вариант) искать способы воспроизведения зеркала.