Codegolf — Сыграйте В Идеальную Игру Му Торере

Фон

Му Торере — это одна из двух игр, в которые, как известно, играл народ маори Новой Зеландии до европейского влияния. Это делает эту игру уникальной, поскольку она имеет «объективный критерий победы» и правила игры, которые отличаются от большинства других существующих игр.

Геймплей:

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

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

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

Здесь это веб-сайт, на котором объясняются правила (с диаграммой) и предлагается некоторый анализ.

Вызов

Ваша задача — написать кратчайшую программу, которая сможет провести идеальную игру Му Торере против человека. Ваша программа должна иметь возможность отображать и обновлять игровое поле, делать ходы и получать ходы от противника-человека. Самое главное, чтобы он играл идеально.

Идеальная игра?

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

Подробности

После каждого хода (и в начале игры) ваша программа должна распечатать игровое поле. Какой бы способ отображения платы вы ни выбрали, на ней должны быть показаны все узлы и она должна быть полностью подключена (все 16 соединительных линий должны быть нарисованы без пересекающихся линий). На старте доска должна занять правильное стартовое положение. Один из способов добиться этого — сделать игровое поле квадратным.

 
 4 
 

Два цвета: черный и белый или темный/светлый. На доске должно быть указано, какие узлы заняты фишками какого игрока, например, помечая их буквами «b» или «w», а какой узел вакантен. Участникам рекомендуется (но не обязательно) сделать игровое поле более графическим, а не простым текстом.

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

Квадратную доску можно пронумеровать следующим образом: w-w-w |\|/| b-o-w |/|\| b-b-b . The 5 is implied as it is the only empty node.

Человек движется первым. Его ввод будет одним числом. Это будет номер узла, в котором в данный момент находится перемещенный камень. Если я хочу переместить камень из узла 4 в пустой узел 5, я наберу

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

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

Ваша программа должна завершиться после победы.

Примечания

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

Руби, 390 символов

 
 
 w 
 
 

Реализация на Ruby, которая напрямую рассчитывает дерево игры (что требует довольно большого количества кода) и, таким образом, всегда работает оптимально. Позиции доски располагаются по спирали наружу, как показано на следующем рисунке:

Баш и друзья (463 447 символов)

Человек играет как 1 - 2 - 3 | \ | / | 8 - 0 - 4 | / | \ | 7 - 6 - 5 , computer as o=->s,c{f=s=~/o/;[*0..8].select{|t|s[t]==c&&(t<1||(t+6)%8+1==f||t%8+1==f||f<1&&(s[(t+6)%8+1]!=c||s[t%8+1]!=c))}.map{|t|k=s*1;k[f]=c;k[t]=?o;k}} v=->s,c,h{f=o[s,c];f==[]?0:h<1?1:2-f.map{|t|v[t,c>?b??b:?w,h-1]}.min} q=->g{puts"1-2-3\n|\\|/|\n8-0-4\n|/|\\|\n7-6-5\n".tr"0-8",g;$>.flush} q[g="obbbbwwww"] (g.tr!?o,?b;g[gets.to_i]=?o;q[g];q[g=o[g,?w].sort_by{|q|v[q,?w,5]}[-1]])while v[g,?b,5]>0 . Позиция на плате пронумерована, как указано в документе вверху. Оказывается, эвристика идеальной игры на удивление проста.

С другой стороны, сбиться с интересного пути довольно сложно. http://ideone.com/sXJPy демонстрирует кратчайшее возможное самоубийство против этого бота. Обратите внимание, что дополнительный 0 в конце предназначен для проверки правильности выхода из цикла.