Mark Goadrich
United States
Shreveport
Louisiana
-
My students and I are experimenting with writing an AI player for Axiom, and we wanted to share some of the games we are generating through Alpha-Beta pruning search. In the spring semester we will be exploring Monte Carlo Tree Search algorithms, which have recently become popular for AI in Go.
We believe we have formulated all the rules correctly in our implementation, but it would really help us out if some seasoned players can double-check that we are not generating invalid games, or provide commentary and strategy tips where the players made mistakes.
The notation used is according to the Play By Email description from 2002 ( http://boardgamegeek.com/file/download/4e0uqcdg7/AxiomEmailP...) since it is better suited for representing the infinite board space than the revised 2008 notation. Player 0 is Orange, and Player 1 is Grey.
We are using a mid-game evaluation function based on summing the number of free cubes you currently have and the number of cubes total, and subtracting the number of free cubes and total number of cubes of your opponent. Moves are sorted in search so that Sceptre moves are explored before Cube moves.
[EDIT: These games are invalid, as pointed out by Ed Abstract below]
Game 1: Alpha-Beta pruning with lookahead of 2 moves
0: Making move 3 S(1,0,2) S(0,1,2)z+
1: Making move 2 S(1,1,2) S(1,0,2)z+
0: Making move 13 C(0,0,2) C(1,1,3)z-
1: Making move 2 S(1,0,2) S(1,0,1)y-
0: Making move 70 C(0,0,1) C(-1,2,1)y- z+
1: Making move 1 S(1,0,1) S(1,0,1)x+
0: Making move 3 S(0,1,2) S(1,1,2)x+
1: Making move 3 C(0,1,1) C(-1,2,2)x+ y+
0: Making move 10 C(1,1,3) C(0,2,1)x-
1: Making move 2 C(-1,2,2) C(0,2,2)x+ z-
0: Making move 6 C(-1,2,1) C(0,2,3)x+ z-
1: Making move 0 S(-1,1,2) S(-1,1,1)y+
0: Making move 2 S(-1,0,2) S(-1,1,2)y+
1: Making move 0 S(-1,1,1) S(-1,1,1)x-
0: Making move 9 S(-1,1,2) S(-1,1,1)y+
Player 0 wins.
Game 2: Alpha-Beta pruning with lookahead of 3 moves
0: Making move 3 S(1,0,2) S(0,1,2)z+
1: Making move 7 S(-1,1,2) S(-1,1,1)y+
0: Making move 1 S(0,1,2) S(0,0,2)z+
1: Making move 5 S(1,1,2) S(1,0,2)z+
0: Making move 4 S(0,0,2) S(1,1,2)z+
1: Making move 5 S(1,0,2) S(0,0,2)z+
0: Making move 0 S(-1,0,2) S(-1,0,1)y-
1: Making move 6 S(0,0,2) S(-1,1,2)z+
0: Making move 3 S(1,1,2) S(1,1,1)y+
1: Making move 2 S(-1,1,2) S(-1,0,2)y-
0: Making move 33 C(1,0,1) C(0,1,2)x+ z-
1: Making move 8 S(-1,1,1) S(0,1,2)y+
0: Making move 3 C(0,0,1) C(-2,0,1)x- y+
1: Making move 1 S(0,1,2) S(0,1,1)y-
0: Making move 0 S(-1,0,1) S(-2,0,1)y-
1: Making move 0 S(0,1,1) S(-1,0,1)y-
0: Making move 0 S(-2,0,1) S(-2,0,1)z+
1: Making move 0 S(-1,0,2) S(-1,1,1)y+
0: Making move 0 S(-2,0,1) S(-2,0,1)y-
1: Making move 0 S(-1,0,1) S(1,1,1)y-
Player 1 wins.
Game 3: Alpha-Beta pruning with lookahead of 4 moves
0: Making move 0 S(1,0,2) S(1,0,1)y-
1: Making move 25 C(0,1,2) C(1,0,3)z-
0: Making move 12 C(0,0,2) C(0,2,1)x+
1: Making move 0 S(1,1,2) S(1,0,2)y-
0: Making move 8 C(0,2,1) C(1,1,3)z-
1: Making move 60 C(0,1,1) C(0,0,2)x+ z-
0: Making move 2 S(-1,0,2) S(-1,0,1)y-
1: Making move 0 S(-1,1,2) S(-1,0,2)y-
0: Making move 1 S(1,0,1) S(0,0,2)y-
1: Making move 3 S(1,0,2) S(1,1,3)y+
0: Making move 0 S(0,0,2) S(1,0,2)y-
1: Making move 9 S(1,1,3) S(1,0,3)y-
0: Making move 1 C(0,0,1) C(1,-1,1)x+ y+
1: Making move 41 C(1,1,2) C(-1,0,3)z-
0: Making move 9 C(1,-1,1) C(1,1,2)x+ y-
1: Making move 14 C(-1,1,2) C(1,2,1)y-
0: Making move 0 S(1,0,2) S(1,1,2)y+
1: Making move 8 S(1,0,3) S(1,1,2)z+
Player 1 wins.
As we improve the speed and efficiency of our implementation, we'll be able to push to further lookahead, and will share those when available.
-
-
Lovely project! I like the rendered images.
Inserting one every five moves or so would be great.
Very probably, move 8 of game 1 is illegal.
White picks up a ground cube 1e5 (0,1,1)
while there is still another cube on top of it.
I assume that Black starts and we use the standard initial position.
Ground cube domes point to the left.
Sorry for introducing yet another notation. (a-i,1-8 grid and "zxy")
1) S 2f4 2e5 u S(1,0,2) S(0,1,2)z+
2) S 2f5 2f4 u S(1,1,2) S(1,0,2)z+
3) C 2e4 3f5 d C(0,0,2) C(1,1,3)z-
4) S 2f4 1f4 s S(1,0,2) S(1,0,1)y-
5) C 1e4 1d6 s u C(0,0,1) C(-1,2,1)y- z+
6) S 1f4 1f4 e S(1,0,1) S(1,0,1)x+
7) S 2e5 2f5 e S(0,1,2) S(1,1,2)x+
8) C 1e5 2d6 e n C(0,1,1) C(-1,2,2)x+ y+ illegal!?!
In my humble opinion, this is the first error.
I'm going to stop here for now, looking forward to your comments.
Ed
-
Mark Goadrich
United States
Shreveport
Louisiana
-
abstracted wrote: Very probably, move 8 of game 1 is illegal.
White picks up a ground cube 1e5 (0,1,1)
while there is still another cube on top of it.
Thank you very much for the comments, Ed! I'm glad to see another enthusiast who knows the notation. 
Yes, I am using the standard initial position, with Black going first (in my case, Orange, since Orange and Grey rendered better than Black and White).
I've rerun the first game above and uploaded a few more images, and [EDIT] I think move 8 is legal. I see what you mean! Here is what the game to looks like after move 6:
In move 7, Orange will move the sceptre from 2e5 to 2f5 pointing east.
When this happens, does not the cube at 2e5 get removed from the game, since the opposing color has just moved off of this free cube? If I understand correctly, this should free up 1e5 and make move 8 legal.
I just reread the cube elimination rules, and I had completely missed the part where the sceptre must be returning to its own color to make the elimination rule activate, thus making move 8 illegal.
Thank you so much for your analysis! Time to dive back into the code and fix up.
-
Mark Goadrich
United States
Shreveport
Louisiana
-
Ok, so I've fixed my cube removal rule and rerun the game for AlphaBeta pruning with 2ply lookahead.
1| 0: Making move 3 S(1,0,2) S(0,1,2)z+
2| 1: Making move 2 S(1,1,2) S(1,0,2)z+
3| 0: Making move 13 C(0,0,2) C(1,1,3)z-
4| 1: Making move 0 S(-1,1,2) S(-1,1,1)y+
5| 0: Making move 0 S(0,1,2) S(0,0,1)z+
6| 1: Making move 20 C(-1,1,2) C(1,1,4)z-
7| 0: Making move 0 S(0,0,1) S(0,1,1)z+
8| 1: Making move 0 S(-1,1,1) S(-1,1,1)x-
9| 0: Making move 4 S(-1,0,2) S(-1,0,2)x-
10| 1: Making move 2 S(1,0,2) S(1,0,2)y-
11| 0: Making move 24 C(0,0,1) C(1,1,5)x+ z-
12| 1: Making move 2 S(1,0,2) S(1,1,1)y+
13| 0: Making move 0 S(0,1,1) S(0,1,1)y-
14| 1: Making move 3 S(1,1,1) S(1,1,5)y-
15| 0: Making move 9 C(1,0,1) C(1,1,6)y- z-
16| 1: Making move 1 S(1,1,5) S(1,1,5)y+
17| 0: Making move 0 S(0,1,1) S(-1,0,1)y-
18| 1: Making move 3 S(1,1,5) S(1,1,6)z+
19| 0: Making move 3 S(-1,0,1) S(-1,0,1)x+
20| 1: Making move 1 S(1,1,6) S(1,1,1)y+
21| 0: Making move 3 S(-1,0,1) S(-1,0,1)y-
22| 1: Making move 4 S(1,1,1) S(1,1,5)y-
23| 0: Making move 3 S(-1,0,1) S(-1,0,1)x+
24| 1: Making move 2 S(1,1,5) S(1,1,1)y-
25| 0: Making move 3 S(-1,0,1) S(-1,0,1)y-
26| 1: Making move 0 S(1,1,1) S(1,1,1)y+
27| 0: Making move 3 S(-1,0,1) S(-1,0,1)x+
28| 1: Making move 0 S(1,1,1) S(1,1,1)y-
At this point, the AIs enter an infinite loop, cycling through moves 25 through 28.
The same thing happened with 3ply lookahead
1| 0: Making move 3 S(1,0,2) S(0,1,2)z+
2| 1: Making move 7 S(-1,1,2) S(-1,1,1)y+
3| 0: Making move 1 S(0,1,2) S(0,0,2)z+
4| 1: Making move 5 S(1,1,2) S(1,0,2)z+
5| 0: Making move 4 S(0,0,2) S(1,1,2)z+
6| 1: Making move 22 C(-1,1,2) C(0,0,3)z-
7| 0: Making move 6 S(1,1,2) S(1,1,1)y+
8| 1: Making move 0 S(-1,1,1) S(-1,1,1)x-
9| 0: Making move 0 S(-1,0,2) S(-1,0,1)y-
10| 1: Making move 28 C(1,1,2) C(-1,0,3)z-
11| 0: Making move 2 S(-1,0,1) S(-1,0,3)z+
12| 1: Making move 38 C(0,1,1) C(0,-1,1)x+ y-
13| 0: Making move 8 S(1,1,1) S(0,0,1)y+
14| 1: Making move 4 S(1,0,2) S(1,0,1)y+
15| 0: Making move 8 S(-1,0,3) S(-1,0,1)y-
16| 1: Making move 21 C(0,-1,1) C(-1,0,3)x+ z-
17| 0: Making move 1 S(0,0,1) S(0,0,3)y-
18| 1: Making move 3 S(1,0,1) S(0,0,1)y+
19| 0: Making move 5 S(0,0,3) S(0,0,2)y+
20| 1: Making move 2 S(0,0,1) S(1,0,1)y+
21| 0: Making move 8 S(0,0,2) S(-1,0,3)y+
22| 1: Making move 0 S(-1,1,1) S(-1,1,1)y+
23| 0: Making move 1 S(-1,0,3) S(-1,0,2)y-
24| 1: Making move 0 S(-1,1,1) S(-1,1,1)x-
25| 0: Making move 0 S(-1,0,2) S(1,0,2)y+
26| 1: Making move 4 S(1,0,1) S(0,0,1)y+
27| 0: Making move 8 S(1,0,2) S(0,0,2)y+
28| 1: Making move 2 S(0,0,1) S(1,0,1)y+
29| 0: Making move 0 S(0,0,2) S(1,0,2)y+
The AI repeats moves 26-29.
I don't believe this is in the official rules, but I think we will have to institute a SuperKo rule to avoid this looping behavior. http://en.wikipedia.org/wiki/Rules_of_Go#Ko_and_Superko
With 4 move lookahead, we have a winner!
1| 0: Making move 25 C(0,0,2) C(0,1,3)z-
2| 1: Making move 3 S(1,1,2) S(0,1,3)x+
3| 0: Making move 0 S(1,0,2) S(1,0,1)y-
4| 1: Making move 4 S(0,1,3) S(1,1,2)z+
5| 0: Making move 3 S(-1,0,2) S(0,1,2)z+
6| 1: Making move 2 S(1,1,2) S(1,1,1)y+
7| 0: Making move 5 S(0,1,2) S(-1,0,2)z+
8| 1: Making move 0 S(1,1,1) S(1,0,2)y-
9| 0: Making move 4 C(0,0,1) C(1,1,3)x+ z-
10| 1: Making move 9 C(0,1,1) C(1,1,4)x+ z-
11| 0: Making move 0 S(-1,0,2) S(-1,0,1)y-
12| 1: Making move 0 S(-1,1,2) S(-1,0,2)y-
13| 0: Making move 0 S(1,0,1) S(1,0,1)x+
14| 1: Making move 5 S(1,0,2) S(1,0,1)y-
Final Board
(black) C (1,0,1)x- z+
(black) S (1,0,1)x+
(white) S (1,0,1)y-
(white) C (1,1,4)x+ z-
(black) C (1,0,2)x+
(white) C (-1,1,2)x-
(black) C (1,1,3)x+ z-
(white) C (1,1,2)x-
(white) C (-1,1,1)x+ z+
(white) C (1,1,1)x+ z+
(black) C (-1,0,1)x- z+
(black) S (-1,0,1)y-
(black) C (-1,0,2)x+
(white) S (-1,0,2)y-
Player 1 wins!
-
-
Indeed, cube elimination applies only when a sceptre moves back to one of your own cubes.
I think this should also be part of the notation.
Just to shamelessly push mine again, I use S: for that. (See below)
I've played through both of your AI games and found no more illegal moves. Looks fine so far (:
To further check, you might want have a look at the two 'unusual situations' mentioned in the Axiom3000 rule booklet: "Trap" and "Diagonal/Slit" (p.15-16)
I'd add one extra "Opposition" case: Sceptres pointing at each other won't fit unless they are three or more spaces apart.
-
-
This is the "4 ply lookahead AI vs. AI" game in my notation, and some comments:
1) C 2e4 3e5 d Cube opening. Cool. But: why this one?
2) S 2f5 3e5 e White thinks it's christmas.
3) S 2f4 1f4 s
4) S: 3e5 2f5 u Maybe it is.
5) S 2d4 2e5 u
6) S 2f5 1f5 n + 'Check'
7) S: 2e5 2d4 u Black flees and gets a cube back.
Was it all forced? (no)
8) S 1f5 2f4 s
9) C 1e4 3f5 de Black probably tries to block C 2f5
10) C 1e5 4f5 de But now White makes sure that one
won't move again, too.
11) S 2d4 1d4 s Black would like to pass his
moves, desperately.
12) S 2d5 2d4 s White tightens the noose even more.
13) S 1f4 1f4 e No choice left.
14) S 2f4 1f4 s # White wins.
-
-
Move Repetition
ensor wrote:
Concerning loops, I'd second a chess-like approach.
Three repetitions of the same position with the same player to move should be counted as a draw.
(Whereas Ko forbids/avoids 'running out of peppermints'.)
PS: Of course, only Michael Seal can really tell.
-
Mark Goadrich
United States
Shreveport
Louisiana
-
abstracted wrote:
To further check, you might want have a look at the two 'unusual situations' mentioned in the Axiom3000 rule booklet: "Trap" and "Diagonal/Slit" (p.15-16)
I'd add one extra "Opposition" case: Sceptres pointing at each other won't fit unless they are three or more spaces apart.
Thanks again very much for your analysis. I did have the Trap and Diagonal/Slit rules accounted for, but not the Opposition you mention; this is now part of our representation.
-
Mark Goadrich
United States
Shreveport
Louisiana
-
My student is making progress on implementing the Monte Carlo Tree Search player. Right now the trees are only stumps (one internal node with a child for each move) and an interesting game occurred against the 2ply Alpha-Beta Player.
0:MonteCarloPlayer vs 1:AlphaBetaPlayer-2ply
1| 0: Making move 25 C(0,0,2) C(0,1,3)z-
2| 1: Making move 2 S(1,1,2) S(0,1,3)z+
3| 0: Making move 9 C(0,0,1) C(1,1,3)x+ z-
4| 1: Making move 0 S(0,1,3) S(0,1,1)y-
5| 0: Making move 0 S(-1,0,2) S(-1,0,1)y-
6| 1: Making move 3 S(-1,1,2) S(-1,0,2)y-
7| 0: Making move 31 C(1,1,3) C(-1,1,3)x+ z-
8| 1: Making move 22 C(1,1,2) C(-1,1,4)z-
9| 0: Making move 0 S(1,0,2) S(1,0,1)y-
10| 1: Making move 32 C(1,1,1) C(1,0,3)y- z-
11| 0: Making move 2 S(1,0,1) S(1,0,2)y-
12| 1: Making move 4 S(-1,0,2) S(-1,1,1)y+
13| 0: Making move 3 S(1,0,2) S(1,0,1)y-
14| 1: Making move 4 S(-1,1,1) S(-1,1,1)x-
15| 0: Making move 0 S(1,0,1) S(1,0,1)y+
16| 1: Making move 3 S(0,1,1) S(-1,1,2)y-
17| 0: Making move 0 S(-1,0,1) S(0,1,1)y-
18| 1: Making move 0 S(-1,1,1) S(-1,1,1)y+
19| 0: Making move 19 C(-1,0,1) C(1,-1,1)y+ z+
20| 1: Making move 0 S(-1,1,1) S(-1,1,1)y-
21| 0: Making move 26 C(1,-1,1) C(-1,1,5)x- z-
22| 1: Making move 10 S(-1,1,2) S(-1,1,5)y+
23| 0: Making move 6 S(1,0,1) S(1,0,3)z+
24| 1: Making move 1 S(-1,1,5) S(-1,1,2)y-
25| 0: Making move 5 S(1,0,3) S(1,0,3)y+
26| 1: Making move 13 C(0,1,2) C(1,1,1)x+
27| 0: Making move 1 S(1,0,3) S(1,0,3)x+
28| 1: Making move 5 S(-1,1,2) S(-1,1,3)y+
29| 0: Making move 3 S(1,0,3) S(1,0,2)x-
30| 1: Making move 0 S(-1,1,3) S(-1,1,3)x-
31| 0: Making move 1 S(0,1,1) S(-1,1,2)y-
32| 1: Making move 1 S(-1,1,3) S(-1,1,3)y-
33| 0: Making move 2 S(-1,1,2) S(0,1,1)y-
34| 1: Making move 0 S(-1,1,3) S(-1,1,3)x-
35| 0: Making move 1 S(0,1,1) S(-1,1,2)y-
36| 1: Making move 1 S(-1,1,3) S(-1,1,3)y-
37| 0: Making move 2 S(-1,1,2) S(0,1,1)y-
38| 1: Making move 0 S(-1,1,3) S(-1,1,3)x-
39| 0: Making move 1 S(0,1,1) S(-1,1,2)y-
40| 1: Making move 1 S(-1,1,3) S(-1,1,3)y-
41| 0: Making move 0 S(-1,1,2) S(-1,1,2)y+
42| 1: Making move 1 S(-1,1,3) S(-1,1,2)y-
Final Board
(black) C (1,0,1)x- z+
(black) C (1,0,2)x+
(black) S (1,0,2)x-
(white) C (-1,1,2)x-
(black) S (-1,1,2)y+
(white) S (-1,1,2)y-
(white) C (-1,1,1)x+ z+
(white) S (-1,1,1)y-
(white) C (1,1,1)x+
(white) C (0,1,1)x+ y+
(black) C (-1,1,3)x+ z-
(white) C (-1,1,4)z-
Player 1 wins!
-
|
|
Posted Sun Dec 4, 2011 6:24 pm
