Play a perfect game of Mu Torere

Question

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.

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.

Answer 1

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

Answer 2

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.