Фон

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

Игровой процесс:

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

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

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

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

Соревнование

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

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

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

Детали

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

w-w-w
|\|/|
b-o-w
|/|\|
b-b-b

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

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

1-2-3
|\|/|
4-5-6
|/|\|
7-8-9

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

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

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

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

Примечания

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

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

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

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

1 - 2 - 3
| \ | / |
8 - 0 - 4
| / | \ |
7 - 6 - 5

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

t(){ tr 0-8a-i $b$b
}
p(){ t<<E
0-1-2
|\|/|
3-4-5
|/|\|
6-7-8

E
}
g(){ b=`tr $x$e $e$x<<<012345678|t`
p
e=$x
}
b=bbbbowwww
e=4
m=0
p
while [ $m != 5 ]&&read x;do
g
m=0
for y in {0..8};do
s=0
S=05011234
grep -E "w.*($y$e|$e$y)"<<<${b:$y:1}30125876340142548746>/dev/null&&for p in wow.\*/ww wow.\*/w bbo.\*/b obb.\*/b www wbw .
do
((s++))
tr $y$e $e$y<<<3012587630/4e|t|grep $p>/dev/null&&break
done
s=${S:$s:1}
[ $s -gt $m ]&&m=$s x=$y
done
g
done

Человек играет как b, компьютер как w. Положение доски нумеруется, как в приведенном здесь документе вверху. Оказывается, эвристика для игры в идеальную игру удивительно проста.

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