Играй в идеальную игру 4x4 Hex

10

Фон

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

Задание

В этой задаче мы устанавливаем размер платы на K = 4и представляем ее как следующую сетку. Толстые линии обозначают смежные плитки.

Сетка 4х4.

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

Схема одной возможной выигрышной стратегии, при условии, что белые идут первыми. Сначала выберите 5. После этого, если у вас есть путь от 5 до нижнего ряда ИЛИ черный выберет 0 или 1 в любой точке, ответьте, выбрав, какой из 0 или 1 свободен. Если черный выберет 9 или 13, выберите 10, а затем, какой из 14 или 15 свободен. Если черный не выбирает 9, 13 или 14, то выберите 9 и следующий, какой из 13 или 14 будет свободен. Если черный выбрал 14, ответьте, выбрав 15. Далее, выберите 10, если он свободен; если черный выберет 10, ответьте 11. Если черный выберет 6, ответьте 7, и следующий, в зависимости от того, 2 или 3 свободен. Если черный не выбирает 6, выберите его, чтобы у вас был путь от 5 до нижнего ряда.

Вход и выход

Ваш ввод представляет собой строку из 16 символов WBE, которые обозначают белый, черный и пустой. Они представляют плитки на доске, как перечислено выше. Вы можете выбрать метод ввода (который также определяет ваш метод вывода) из следующих:

  1. Ввод из STDIN, вывод в STDOUT.
  2. Ввод в качестве одного аргумента командной строки, вывод в STDOUT.
  3. Ввод в виде 16 односимвольных аргументов командной строки, вывод в STDOUT.
  4. Ввод в качестве аргумента именованной функции, вывод в качестве возвращаемого значения.

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

  1. Начинающийся с нуля индекс (как показано на рисунке выше).
  2. Индекс на основе одного.
  3. Строка ввода Eзаменяется на ту , которая выбрана Wили Bвыбрана для вашего игрока.

правила

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

Это код-гольф, поэтому выигрывает самое низкое число байтов. Стандартные лазейки запрещены.

тестирование

Я написал контроллер Python 3 для проверки записей, так как это было бы чрезвычайно утомительно делать вручную. Вы можете найти это здесь . Он поддерживает первые три формата ввода и функции Python 3 (функции на других языках должны быть включены в программы), все три формата вывода и оба проигрывателя. Если стратегия не выигрывает, она выдаст найденную проигрышную игру, так что вы можете настроить свою программу.

Zgarb
источник
Эта проблема напоминает мне о попытке сжать искусственный интеллект, когда я писал программы для калькулятора. ticalc.org/archives/files/fileinfo/354/35408.html
Спарр
2
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.Я должен был выиграть давно или я не прав?
Себастьян Хеффнер,
@ SebastianHöffner Это похоже на ошибку в контроллере. Я постараюсь исправить это, когда у меня будет время.
Згарб
@ SebastianHöffner Теперь ошибка должна быть исправлена.
Згарб

Ответы:

6

Марбелоус, 973б

Это наивная реализация подсказанной стратегии в вопросе. Он ожидает, что доска будет представлена ​​в виде 16 параметров командной строки / основной платы, hex.mbl B W E E E W E E E B E E E E E Eи выведет нулевую позицию следующего хода белых.

00 }1 }0
&G B? W!
&0 &G &G
!!
00 }0 }1
&H B? W!
&1 &H &H
!!
.. }D .. }9 }9 }D }E }A }D }9 }A .. }E }F }5
}9 B! }E E? W? E? .. E? B? B? W? .. E? .. E?
B! ?0 B! &M &N &O E? &I \\ .. &J .. &K E? &5
?0 ++ ?0 &9 .. &D &P &A &I /\ &J .. &E &L !!
++ .. ++ !! .. !! &E !! \/ &L /\ &K !! &F
\\ .. // .. .. .. !! .. .. \/ .. \/ .. !!
.. =3 \/
&M /\ &N
\/ &O /\ &P
}0 }1 }6 .. }6 .. }7 &7 }2 }3 }A }A }B }E }F
..
..
..
..
..
..
..
..
..
.. .. .. .. .. .. .. .. .. .. .. .. .. B? W!
.. .. .. .. .. .. .. .. .. .. .. .. .. &Q &Q
.. .. .. .. B? .. E? W? E? .. E? B? E? &F \/
.. .. .. &S /\ &T &S &T &U E? &A &R &R !!
.. .. .. &7 .. .. \/ .. &2 &V !! &B \/
.. .. .. !! .. .. &U /\ &V &3 .. !!
.. .. .. .. .. .. .. .. .. !!
.. .. ..
.. .. E?
E? .. &6
&X E? !!
!! &Y
.. !!
}4 }8 }C
\/ \/ \/
30 30 31 31 32 33 35 36 37 39 31 30 31 31 31 33 31 34 31 35
&0 &X &1 &Y &2 &3 &5 &6 &7 &9 &A &A &B &B &D &D &E &E &F &F
:W?
}0
^4
=1
{0
:B?
}0
^0
=0
{0
:E?
}0
^1
=0
{0
:W!
}0
^4
=0
{0
:B!
}0
^0
>0
{0

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

Sparr
источник
Я добавил опцию для аргумента 16 командной строки и обновил скрипт верификатора, чтобы можно было проверить это решение.
Згарб
Marbelous +1 (PPCG считает, что добавление этих символов улучшило комментарий)
Rohan Jhunjhunwala
1

Python 3, 100b

b=input()
i=b.find('B')
if b[i]in'BW'and'E'in b:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])
  • Игрок: ЧЕРНЫЙ
  • Метод: STDIN / STDOUT, MODIFIED_BOARD

Стратегия заключается в том, чтобы сначала найти Bна доске. Если его нет, это возвращает -1, что в python такое же, как last index. При этом на пустой доске мой первый индекс будетindex=-1 , где я и начну двигаться.

Если поле слева от меня ( index-1) свободно, мой следующий ход идет туда. Если это будет сделано, я иду налево. Мне никогда не придется двигаться вверх: если я это сделаю, я теряю темп и теряю игру.

На полном пансионе ( Eнигде нет ) я не делаю ход.

printКажется немного странным на первый: я должен построить новую плату (который я делаю через нарезка) , но тогда мне нужно вырезать 16 символов. Это реликт, так как я работаю с отрицательными индексами и b[i+1:], таким образом, верну дырочную доску и все остальное, что я ожидаю, что делает важным отсечь остаток. Другим способом было бы работать с положительными показателями, например, принимая (b.find('B')+16)%16, но (+16)%16на один байт больше, чем ()[:16].

Ungolfed:

board = input()
index = board.find('B')
if board[index] in 'BW' and 'E' in board:
    index -= 1 + (board[index-1] is 'W') * 4
print((board[:index] + 'B' + board[index+1:])[:16])

Тестовое задание

При работе с тестовым набором шестнадцатеричного контроллера я столкнулся со странным поведением:

OUT: EEEEEEEEEEEEEEEB
OUT: WEEEEEEEEEEEEEBB
OUT: WWEEEEEEEEEEEBBB
OUT: WWWEEEEEEEEEBBBB
OUT: WWWWEEEEEEEBBBBB
OUT: WWWWWEEEEEBBBBBB
OUT: WWWWWWEEEBBBBBBB
OUT: WWWWWWWEBBBBBBBB
OUT: WWWWWWWWBBBBBBBB

Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

Я думаю, что либо я должен был выиграть после 4-го хода, либо ответ с той же доской на полную доску должен быть правильным ответом. Не уверен, что там пойдет не так, я не стал погружаться глубже - я просто хотел проверить, покрыл ли я все «особые» случаи. Но так как мне не нужно скрывать ситуации, когда кто-то начинает с места 4 или около того, это все равно не имеет значения.

85b

Однако, если я позволю себе не проверять полный пансион (то есть, 'E' in bопуская код, я могу еще больше упростить код, чтобы использовать только 85 байтов:

b=input();i=b.find('B')
if i!=-1:i-=1+(b[i-1]is'W')*4
print((b[:i]+'B'+b[i+1:])[:16])

Это приведет к следующему:

Incorrect response 'WWWBWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.

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

Себастьян Хеффнер
источник