Improving Strategic Play in Shogi by Using Move Sequence Trees Reijer Grimbergen Department of Informatics Yamagata University 2007/11/11 GPW2007

Outline Opening play in Shogi The problems of hill-climbing Move sequence trees Extracting move sequences Using move sequence trees Preliminary results Conclusions and future work 2007/11/11 GPW2007

Opening play in shogi The weak point of shogi programs is opening play “Endgame: 6-dan, opening: 1-kyu” Shogi programs cannot handle long term strategy Strategic knowledge cannot be obtained by search alone Example: building a castle formation can take more than 10 moves by one player 2007/11/11 GPW2007

Opening play in shogi 玉（美濃囲い） 金（美濃囲い） 銀（美濃囲い） 2007/11/11 GPW2007 3 6 9 3 6 9 1 9 2 玉（美濃囲い） 金（美濃囲い） 銀（美濃囲い） 2007/11/11 GPW2007

The problems of hill-climbing 1）　4八玉　　3八玉　　2八玉　　3八銀　　5八金(69) 2）　3八銀　　4八玉　　5八金(69)　　3九玉　　2八玉 3）　5八金(69)　　3八銀　　4八玉　　3九玉　　2八玉 　　　　　　　　　　　　　　　　： 2007/11/11 GPW2007

The problems of hill-climbing 6七金(58) 6八金(58) 6七金(68) 2007/11/11 GPW2007

Move sequence trees Information about move order is needed to solve the problems of hill-climbing Move sequence trees For each opening strategy, collect information about common move orders Save this data in move sequence trees Use move sequence trees to guide the search 2007/11/11 GPW2007

Extracting move sequences Move sequence extraction Collect games with a with a specific opening strategy Collecting move frequency data Generate a move sequence tree 2007/11/11 GPW2007

Collecting games Find all games with a finished castle Yagura In the Shogi Club24 database (240,000 games) Personal professional game database (5,000 games) Yagura Sente: 2548 games (SC24: 1815, Pro: 733) Gote: 2036 games (SC24: 1520, Pro: 516) 2007/11/11 GPW2007

Collecting move frequency data Yagura for sente 1288 different moves in the first 50 moves of the game Only 153 moves were played in 1% of the games or more Move Fr (%) 7六歩(77) 100 6八銀(79) 78 4六歩(47) 32 9六歩(97) 20 6六歩(67) 99 7七銀(68) 3五歩(36) 29 7五歩(同) 16 5八金(49) 1六歩(17) 72 6八玉(59) 27 6五歩(66) 15 7八金(69) 98 6九玉(59) 71 1五歩(16) 26 4七銀(48) 13 6七金(58) 97 8八玉(79) 2四歩(25) 24 5五歩(同) 12 5六歩(57) 91 7九玉(69) 69 5七銀(48) 8六銀(77) 11 4八銀(39) 89 2五歩(26) 60 3八飛(28) 23 7七銀(88) 2六歩(27) 6八角(79) 47 4六銀(37) 5五歩(56) 10 3六歩(37) 84 3七銀(48) 45 7八玉(68) 21 5八飛(28) 7九角(88) 83 3七桂(29) 38 8八玉(78) 2007/11/11 GPW2007

２六歩(27) ２六歩(27) ６八銀(79) ４八銀(39) ６六歩(67) ４八銀(39) ５八金(49) ７八金(69) 876 976 ２六歩(27) ２六歩(27) 360 6 549 ６八銀(79) ４八銀(39) ６六歩(67) 85 5 ４八銀(39) ５八金(49) Same position 80 ７八金(69) 2813 517 942 ６六歩(67)** Start ７六歩(77) ６八銀(79) 315 58 ７七銀(68) ７七角(88) 5 32 ６六歩(67) 7 ７八銀(79) ５六歩(57) 27 4 ８八銀(同角) ５六歩(57) 5 15 ４八銀(39) １六歩(17) 3 14 3 ７八金(69) ５六歩(57) ２六歩(27) 12 3 ２二角成(88) 2 ６八玉(59) ７八金(69) 9 ５八金(49) 2 2 5 ５八飛(28) ５八飛(28) ６八玉(59) 2 1 ３六歩(37) １六歩(17) 2007/11/11 GPW2007

Using move sequence trees Step 1: Select a move sequence tree Not all move sequence trees can be loaded at the same time Use move frequencies to find the best match Step 2: Access the move sequence tree during the search Use a pointer to the move sequence tree Award an evaluation bonus for each move that follows the move sequence tree 2007/11/11 GPW2007

Preliminary results Version Won Lost WP Yagura MST OTO MST25 23 27 46% 20 21 MST50 54% 32 MST75 28 22 56% 15 MST100 25 50% 2007/11/11 GPW2007

Conclusions and future work Using move sequence trees may be an improvement of hill-climbing methods It seems unlikely that move sequence trees are the best solution Future work Generate move sequence trees for all opening strategies Bonus values should be based on move frequency Move sequence tree selection should be based on partial hashcodes 2007/11/11 GPW2007