Experiments

The proposed method was applied to the games of Hex and Y. An implementation is available at http://www.cis.hut.fi/praiko/hex/. Figure 5 shows a game of Hex played by the proposed method against itself. The red player won as can be seen from the path starting from moves 43, 33, 21. The level of play is not very high, but taking into consideration that the system is not game-specific and that the implementation is preliminary, the level is acceptable.

Figure 5: An example game of Hex by self-play of the proposed system.

Figure 6 shows the position before move 31. Because of symmetry of the criterion for selecting new patterns, they are generated in pairs, for instance, the patterns red at $a$ and blue at $a$ were the first two. Patterns in the order of appearance {}, {$a$}, {$c$}, {$d$}, {$h$}, {blue $c$, $f$}, {red $a$, $b$}, {red $c$, $d$}, {red $d$, $c$}, {blue $a$, $g$}, and so forth. The patterns are clearly concentrated on areas of interest and they are local.

Figure 6: At move 31, the first patterns use the cells marked with $a,b,\dots ,h$. See text for explatations.

A tournament between 8 different computer players was held in the game of Y such that each player met every opponent 10 times as black and 10 times as white, 640 games in total. The first player $A$ made just random moves chosen uniformly from all the available moves. Three players $B,C$, and $D$ used the all-moves-as-first heuristic with 100, 1000, and 10000 fully random play-outs per move, accordingly. Players $E$ and $F$ used second-order heuristics, that is, considering all patterns where a single move is made by the player in turn. The final two players $G$ and $H$ used selective patterns, whose number varied from 0 to 99 and size from 0 to 7. The players $E$-$H$ used the second-order move selection in Equation (5). The number of play-outs and the average time per move is shown in table 1.

Table 1: The number of playouts, the order of used statistics, the average thinking time in milliseconds per move, and the winning percentage against other players is given for each player.

player	order	# playouts	time/ms	win %
A	-	0	5	0
B	1	100	8	16
C	1	1000	36	66
D	1	10000	276	65
E	2	1000	125	65
F	2	10000	1155	61
G	N	1000	240	64
H	N	10000	14735	63

The results are shown in Table 2. Black won 53% of the matches since the first move gives an advantage. Player $A$ lost all games againt other players. Player $B$ was also clearly worse than the others. The differences between the players $C$-$H$ are not clear from the limited amount of data.

Table 2: Wins out of ten for the black player (label on the left) against the white player (label on the top).

	A	B	C	D	E	F	G	H
A	7	0	0	0	0	0	0	0
B	10	6	0	1	1	0	0	0
C	10	10	7	3	7	6	6	6
D	10	10	5	2	5	5	5	8
E	10	10	7	7	7	6	3	6
F	10	10	6	6	4	4	6	3
G	10	10	4	5	5	6	8	6
H	10	9	4	5	6	7	6	6