Определить победителя Connect 4

19

Вам предоставляется частично заполненная сетка Connect 4 (7x6).

O X             
O X          
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(Ввод может быть представлен в виде 1D или 2D массива, а также букв или цифр и т. Д.)

Предположить, что

  • Х начал игру.
  • Никто еще не победил.
  • Игроки, возможно, не играли хорошо до сих пор, но теперь они оба будут использовать оптимальные стратегии.
  • Входная сетка не является неисправной.

Вы должны вывести единственное значение, которое указывает, какой игрок выигрывает (или ничья)

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

ghosts_in_the_code
источник
Связанный.
Мартин Эндер
@ MartinBüttner Означает ли это, что я буду лишен права голоса, или можно оставить свой вопрос здесь?
ghosts_in_the_code
4
Это просто означает, что вопросы связаны, ни больше, ни меньше. Цель публикации ссылки - чтобы задачи отображались на боковой панели «Связанные» друг друга, чтобы людям было легче находить связанные проблемы. Если бы я считал ваш вопрос дубликатом, я бы сказал (или просто закрыл), так что не волнуйтесь. :)
Мартин Эндер
2
Хорошо ли определена «оптимальная игра»? Если да, можете ли вы предоставить ссылку, описывающую алгоритм оптимальной игры?
Рейнболт
2
@Rainbolt Это было решено, и существуют также совершенные алгоритмы . Читайте Википедию для большего.
ghosts_in_the_code

Ответы:

16

Perl 119 118 117 байт

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

Дайте повернутую доску, дополненную пробелами на STDIN (гравитация тянет камни вправо)

connect4.pl
  OXXX
   XOO
    OX
  OOXX
  XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

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

Выводит 3, выигрывает 1ли игрок на ходу, проигрывает ли игрок на ходу и 2на ничью.

На старых perls вы можете использовать литерал, ^Sчтобы получить один байт. Если вы не возражаете против крайней неэффективности, вы можете опустить $$_||=(таблицу транспонирования) и получить еще 6 байтов. Если вы пропустите, $_=он покажет вам, где играть вместо результата (играйте 1и выигрывайте, если таковой имеется, играйте 2и тяните, если есть, или играйте на любом 3и проигрывайте)

Строит и оценивает полное минимаксное дерево. Вам не хватит памяти и времени, если доска уже не будет достаточно хорошо заполнена.

Тон Хоспел
источник
2
С какой стати кто-то понизил голос? Игра в гольф действительно восхитительна (я играю в гольф с Perl, и получить такое решение крайне сложно - я не уверен, что любой другой игрок в Perl, которого я знаю, мог бы придумать этот код). И код имеет требуемое поведение.
Дада
Это делает мой мозг болит. +1!
levelonehuman
@ Дада, откуда ты знаешь, что за этот ответ проголосовали? Я вижу 3 как голосование ...
РосЛюП
@RosLuP, когда я впервые увидел этот пост, у него было 1 downvote. Кроме того, когда у вас достаточно репутации, вы можете увидеть, сколько голосов за и против имеет пост: в этом случае теперь он имеет 4 вверх и 1 вниз.
Дада