14
\$\begingroup\$

Background

Mu Torere is a game that is one of only two known to be played by the Maori people of New Zealand before European influence. This makes it a very unique game in that it has an "objective winning criterion" and rules of play that are different from most other games in existence.

Gameplay:

The board is an octagon. There are connections between each adjacent vertex, and there is a center node that is connected to all of the vertices. At any point in time, eight of the nine nodes are occupied by stones. At the start, there are four white stones and four black stones that are each take up one half of the octagon, with the center node empty. Black moves first.

Each turn, a player can move one of his stones along one of the 16 edges from one node to the empty node. A stone can only be moved from an outer node to the center node if the stone is next to an opponent's stone.

A player loses when he is unable to make a legal move, which occurs when there is no edge connecting a stone to the empty node.

A diagram and explanation of the rules

Here is a website that explains the rules (with a diagram) and offers some analysis.

The Challenge

Your challenge is to write the shortest program that can play a perfect game of Mu Torere against a human opponent. Your program should be able to display and update the game board, make moves and receive moves from a human opponent. Most importantly, it should play a perfect game.

Perfect Game?

Yes, perfect game. I've been doing some game analysis, and I found that the game lasts for an infinite amount of time if played perfectly by both sides. This means that your program should never lose. Also, your program should be able to force a win whenever the human opponent makes a mistake that allows the program to force a win. As for how your program finds the perfect move, this is up to you.

Details

After each move (and at the start of the game), your program should print the game board. However you choose to display the board, it must show all of the nodes and be fully connected (all 16 connection lines should be drawn with no crossed lines). At the start, the board should have the correct starting position. One way of accomplishing this is by making the game board a square.

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

The two colors are black and white, or dark/light. The board must show which nodes are occupied by which player's pieces, such as marking them with a "b" or "w", and which node is vacant. Participants are encouraged (but not required) to make the game board more graphical, rather than plain text.

Your game board should have a numbering system that gives each node a unique number. You may choose to number the board any way you like, but it should be explained in your answer or by the program. The square board can be numbered as follows:

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

The human is the first to move. His input will be a single number. This will be the number of the node where the moved stone currently is. If I wanted to move a stone from node 4 to an empty node 5, I will type a 4. The 5 is implied as it is the only empty node.

Assume that the human will always make a legal move.

After the human makes his move, an updated board should be printed. After your program decides on a legal move, it should print another updated board, and then wait for the human to enter another move.

Your program should terminate once it has won.

Notes

Standard code golf rules apply, no accessing external files, etc., etc. Also, I'm going to impose a flexible time limit of 15 seconds (on a reasonable machine) for your program to make each of its moves. As stated, this game has the possibility to form infinite loops, and I don't want a depth-first search getting into an infinite loop.

\$\endgroup\$
  • 2
    \$\begingroup\$ Great challenge. Only "If the human inputs an illegal move, then your program should wait and allow him to input a different move." seems a bit un-golf-ish to me: can't we just leave the behaviour undefined in case of illegal inputs? \$\endgroup\$ – ceased to turn counterclockwis May 28 '12 at 12:40
  • 1
    \$\begingroup\$ I threw that requirement in at the last minute, and I guess it would be okay if we were to eliminate it. That just makes it harder for the human, who is already doomed to not win. :) \$\endgroup\$ – PhiNotPi May 28 '12 at 13:14
  • 1
    \$\begingroup\$ It's not that hard to always enter a legal move... By the way, after fairly detailed analysis I think it's unnecessary to search more than 1.5 moves ahead. Whether that approach is the shortest is another question. \$\endgroup\$ – Peter Taylor May 28 '12 at 14:57
  • 3
    \$\begingroup\$ The linked website isn't available anymore, it would be better to change it into a link to an archived version. \$\endgroup\$ – Tally Oct 15 '14 at 23:34
6
\$\begingroup\$

Ruby, 390 chars

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

An implementation in ruby which directly calculates the game tree (which takes quite some code) and thus always plays optimally. The board positions are spiraling outwards as shown in the following figure:

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

bash and friends (463 447 chars)

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

Human plays as b, computer as w. Board position is numbered as in the here doc at the top. It turns out that the heuristics to play a perfect game are surprisingly simple.

On the other hand, losing down the interesting path is quite hard. http://ideone.com/sXJPy demonstrates the shortest possible suicide against this bot. Note that the extra 0 at the end is to test that it breaks out of the loop correctly.

\$\endgroup\$
  • \$\begingroup\$ NB I could save one character by making the read x compulsory, but that would make testing quite frustrating. I could also save a character by removing the blank line after the board, but... \$\endgroup\$ – Peter Taylor May 29 '12 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.