Фон
Hex - это абстрактная стратегическая игра для двух игроков, играемая на K×K
ромбе с шестиугольными плитками. Две противоположные стороны ромба окрашены в белый цвет, а два других - в черный, а два игрока, черный и белый, по очереди размещают жетон своего цвета на незанятой клетке. Игрок, который первым сумел построить путь между противоположными сторонами своего цвета, становится победителем. Известно, что игра не может закончиться ничьей, и что первый игрок имеет выигрышную стратегию независимо от размера доски (подробности см. На странице Википедии).
Задание
В этой задаче мы устанавливаем размер платы на K = 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
, которые обозначают белый, черный и пустой. Они представляют плитки на доске, как перечислено выше. Вы можете выбрать метод ввода (который также определяет ваш метод вывода) из следующих:
- Ввод из STDIN, вывод в STDOUT.
- Ввод в качестве одного аргумента командной строки, вывод в STDOUT.
- Ввод в виде 16 односимвольных аргументов командной строки, вывод в STDOUT.
- Ввод в качестве аргумента именованной функции, вывод в качестве возвращаемого значения.
Ваш вывод представляет тайл, на который вы кладете свой следующий токен, так как ваша очередь двигаться. Вы можете выбрать один из следующих форматов вывода:
- Начинающийся с нуля индекс (как показано на рисунке выше).
- Индекс на основе одного.
- Строка ввода
E
заменяется на ту , которая выбранаW
илиB
выбрана для вашего игрока.
правила
Ваша стратегия должна быть детерминированной. Вы не обязаны правильно обрабатывать игровые позиции, которые недоступны с пустой доски, используя вашу стратегию, или позиции, которые уже выигрывают для любого игрока, и вы можете столкнуться с ними. И наоборот, на досках, которые достижимы с помощью вашей стратегии, вы должны вернуть законный ход.
Это код-гольф, поэтому выигрывает самое низкое число байтов. Стандартные лазейки запрещены.
тестирование
Я написал контроллер Python 3 для проверки записей, так как это было бы чрезвычайно утомительно делать вручную. Вы можете найти это здесь . Он поддерживает первые три формата ввода и функции Python 3 (функции на других языках должны быть включены в программы), все три формата вывода и оба проигрывателя. Если стратегия не выигрывает, она выдаст найденную проигрышную игру, так что вы можете настроить свою программу.
Incorrect response 'WWWWWWWWBBBBBBBB' to message 'WWWWWWWWBBBBBBBB'.
Я должен был выиграть давно или я не прав?Ответы:
Марбелоус, 973б
Это наивная реализация подсказанной стратегии в вопросе. Он ожидает, что доска будет представлена в виде 16 параметров командной строки / основной платы,
hex.mbl B W E E E W E E E B E E E E E E
и выведет нулевую позицию следующего хода белых.Я думаю, что я, вероятно, смогу сыграть около 200 символов из этого с лучшим разветвлением и устранением повторного использования кода.
источник
Python 3, 100b
Стратегия заключается в том, чтобы сначала найти
B
на доске. Если его нет, это возвращает-1
, что в python такое же, какlast index
. При этом на пустой доске мой первый индекс будетindex=-1
, где я и начну двигаться.Если поле слева от меня (
index-1
) свободно, мой следующий ход идет туда. Если это будет сделано, я иду налево. Мне никогда не придется двигаться вверх: если я это сделаю, я теряю темп и теряю игру.На полном пансионе (
E
нигде нет ) я не делаю ход.print
Кажется немного странным на первый: я должен построить новую плату (который я делаю через нарезка) , но тогда мне нужно вырезать 16 символов. Это реликт, так как я работаю с отрицательными индексами иb[i+1:]
, таким образом, верну дырочную доску и все остальное, что я ожидаю, что делает важным отсечь остаток. Другим способом было бы работать с положительными показателями, например, принимая(b.find('B')+16)%16
, но(+16)%16
на один байт больше, чем()[:16]
.Ungolfed:
Тестовое задание
При работе с тестовым набором шестнадцатеричного контроллера я столкнулся со странным поведением:
Я думаю, что либо я должен был выиграть после 4-го хода, либо ответ с той же доской на полную доску должен быть правильным ответом. Не уверен, что там пойдет не так, я не стал погружаться глубже - я просто хотел проверить, покрыл ли я все «особые» случаи. Но так как мне не нужно скрывать ситуации, когда кто-то начинает с места 4 или около того, это все равно не имеет значения.
85b
Однако, если я позволю себе не проверять полный пансион (то есть,
'E' in b
опуская код, я могу еще больше упростить код, чтобы использовать только 85 байтов:Это приведет к следующему:
Это может или не может быть засчитано, и так как я обнаружил, что это не был правильный ход, я решил пойти на более длинный, но более правильный ответ.
источник