EWIN wins EinStein Würfelt Nicht! tournament

Abstract

The 21^st Computer Olympiad was held in New Taipei City, Taiwan, from July 7 to 13, 2018. One team from China could not attend due to visa problems. In total, nine teams from four countries participated in the EinStein Würfelt Nicht! (EWN) tournament, as listed in Table 1. EWN is a two-player zero-sum stochastic game designed by Althöfer in 2004 (Althöfer, 2011). The game is played on a 5×5 board with a dice. Two players, Red and Blue, respectively own six pieces numbered one to six. At the beginning of a game, red and blue pieces are placed in the top-left and bottom-right corners of the board respectively. The order of the pieces for the two colors should be rotationally symmetric for fairness. The players roll dice in each move to determine which pieces can be moved. The goal of the game is to move one piece to the opponent’s corner or capture all opponent pieces. The detailed game rules can be found in the paper by Chu et al. (2017).

A round-robin system was applied for the tournament. Each program played eight games against all other programs. The initial positions were determined by rolling dice. For each initial position, two games were played with the two programs alternating as the first player. The final ranks were determined by the total numbers of games won by the programs. The detailed scores and the final ranks are listed in Table 2. EWIN won 47 games and was ranked first. The second and the third place winners were Deep Nikita and k = 8πG, which won 37 and 36 games respectively.

Table 1
The participants of the EWN tournament in the 21^st Computer Olympiad

Program name Author(s) Operator Country

k = 8πG Kotaro Ataka Kei Takada Japan

EWNGame Ann Lao, Minqin Lee and Sijin Chen Song Wang China

EWIN Yuan-Hao Chen, Yeong-Jia Roger Chu, Chu-Hsuan Hsueh and I-Chen Wu Chu-Hsuan Hsueh Taiwan

Kaiten Pin-Ju Lin and Shun-Shii Lin Pin-Ju Lin Taiwan

Emil Wen-Yen Chou and Shun-Shii Lin Shun-Shii Lin Taiwan

shuka Hao-Lun Luo Hao-Lun Luo Taiwan

Deep Nikita Andrew Lin Andrew Lin USA

Emc2 Yasumasa Tamura Yasumasa Tamura Japan

VSWTN Yunpeng Zhang, Wei Li and Yuxuan Zhang Yunpeng Zhang China

Program name	Author(s)	Operator	Country
k = 8πG	Kotaro Ataka	Kei Takada	Japan
EWNGame	Ann Lao, Minqin Lee and Sijin Chen	Song Wang	China
EWIN	Yuan-Hao Chen, Yeong-Jia Roger Chu, Chu-Hsuan Hsueh and I-Chen Wu	Chu-Hsuan Hsueh	Taiwan
Kaiten	Pin-Ju Lin and Shun-Shii Lin	Pin-Ju Lin	Taiwan
Emil	Wen-Yen Chou and Shun-Shii Lin	Shun-Shii Lin	Taiwan
shuka	Hao-Lun Luo	Hao-Lun Luo	Taiwan
Deep Nikita	Andrew Lin	Andrew Lin	USA
Emc2	Yasumasa Tamura	Yasumasa Tamura	Japan
VSWTN	Yunpeng Zhang, Wei Li and Yuxuan Zhang	Yunpeng Zhang	China

EWIN is based on Monte-Carlo tree search (MCTS) combined with n-tuple networks trained by Monte-Carlo learning (Chu et al., 2017). Deep Nikita applied expectiminimax and used a large endgame tablebase, while k = 8πG combined MCTS with deep convolutional neural networks (The 21^st Computer Olympiad, 2018). As for other programs, EWNGame, Kaiten, shuka, and VSWTN were based on expectiminimax, Emc2 was based on MCTS, and Emil used convolutional neural networks (The 21^st Computer Olympiad, 2018).

1. Selected games

This report comments on two games, one between EWIN (the gold) and Deep Nikita (the silver), and the other between EWIN and k = 8πG (the bronze). A game record starts with the initial position, specifying the squares of red pieces numbered one to six and then blue pieces numbered one to six respectively. The record then contains all moves played in the game. Each move is denoted by the color to play (R for Red and B for Blue), the rolled dice number, the source square of the moved piece, and the destination square of the moved piece.

Game 1: Deep Nikita (Blue) vs. EWIN (Red) 0-1

Table 2

The detailed scores and the final ranks

No.	Program name	Opponent No.									Score	Rank

		1	2	3	4	5	6	7	8	9
1	k = 8πG	-	4	3	6	6	3	3	5	6	36	3
2	EWNGame	4	-	2	1	5	2	2	4	2	22	9
3	EWIN	5	6	-	6	5	6	6	5	8	47	1
4	Kaiten	2	7	2	-	2	2	3	5	2	25	8
5	Emil	2	3	3	6	-	6	4	2	6	32	5
6	shuka	5	6	2	6	2	-	2	3	2	28	6
7	Deep Nikita	5	6	2	5	4	6	-	7	2	37	2
8	Emc2	3	4	3	3	6	5	1	-	2	27	7
9	VSWTN	2	6	0	6	2	6	6	6	-	34	4

a3 b5 a4 a5 b4 c5 c1 e2 d1 e1 d2 e3, 1. B 2 e2 d2 2. R 5 b4 c3 3. B 6 e3 d3 4. R 2 b5 c4 5. B 6 d3 c4 6. R 2 a4 b3 7. B 6 c4 b5 8. R 1 a3 b3 9. B 2 d2 c2 10. R 2 a5 b5 11. B 5 e1 d1 12. R 6 c5 c4 13. B 4 d1 c2 14. R 3 b3 c2 15. B 4 c1 c2 16. R 5 c3 c2

The initial position of the game is shown in Fig. 1(a). In this game, Blue was the first player. At the 7^th move, Blue rolled the number of six and moved its from c4 to b5, as shown in Fig. 1(b). With a probability of 1/3 (rolling the number of five or six), Blue could win on its next turn by moving the to the target square a5. At the 8^th move, Red rolled one and captured its own to increase the probability of moving (the only piece that could capture the opponent ). With the captured, the probability of moving increased from 1/6 to 1/2 (rolling two, three, or four allows Red to move ). The strategy succeeded as Red rolled two and captured the opponent on the 10^th move, which resolved the crisis of losing on the next opponent move. Finally, Red won the game by capturing all blue pieces on the 16^th move, as shown in Fig. 1(c).

Fig. 1.

The commented game between Deep Nikita (blue) and EWIN (red): (a) the initial position, (b) the 7^th move, and (c) the winning move.

Game 2: EWIN (Red) vs. k = 8πG (Blue) 1-0

b5 c5 b4 a5 a3 a4 e2 e3 d2 e1 c1 d1, 1. R 2 c5 d4 2. B 3 d2 c3 3. R 6 a4 a3 4. B 1 e2 e3 5. R 4 a5 b4 6. B 4 e1 d2 7. R 4 b4 c3 8. B 3 d2 c3 9. R 3 d4 d3 10. B 2 e3 d3 11. R 2 a3 b2 12. B 2 c3 b3 13. R 3 b2 c2 14. B 6 d1 c2 15. R 1 b5 c4 16. B 5 c1 b1 17. R 1 c4 d3 18. B 2 b3 a4 19. R 1 d3 e2 20. B 5 b1 a1 21. R 1 e2 e1

The initial position of the game is shown in Fig. 2(a). In this game, Red was the first player. After Blue captured the opponent on the 14^th move, as shown in Fig. 2(b), Red had only one piece remaining, i.e. , and no longer needed to roll the dice for the rest of the game. On the next (15^th) move, Red moved its to c4, which had a probability of 1/2 to lose on the 16^th move if the opponent rolls one, two, or three to capture by . However, Blue ended up rolling five. Red then captured the opponent on the 17^th move to eliminate the threat, though the probability for the opponent to move (the piece closest to the target square a5) was increased from 1/2 to 2/3. On the 20^th move, Blue had a probability of 2/3 to win if one, two, three, or four is rolled, in which case can be moved to the target square a5. However, Blue rolled five and missed the chance to win, as shown in Fig. 2(c). As a result, Red won on the 21^st move by moving its to the target square e1.

Fig. 2.

The commented game between EWIN (red) and k = 8πG (blue): (a) the initial position, (b) the 14^th move, and (c) the 20^th move.

Fig. 3.

An EWN game set given to the winning team.

Althöfer, the designer of EWN, provided an EWN game set with a wooden board and glass pieces as a reward to the winning team. The game set, as shown in Fig. 3, was awarded to the authors of EWIN.

References

Althöfer, I. (2011). On the origins of EinStein Würfelt Nicht! Available at: https://althofer.de/origins-of-ewn.html.

Chu, Y.-J.R., Chen, Y.-H., Hsueh, C.-H. & Wu, I.-C. (2017). An agent for EinStein Würfelt Nicht! using n-tuple networks. In Conference on Technologies and Applications of Artificial Intelligence (TAAI 2017), Taipei, Taiwan.

The 21^st Computer Olympiad (2018). ICGA Computer Olympiad 2018, Available at: https://www.tcga.tw/icga-computer-olympiad-2018/en/#tsignup.