Improving Strategic Play in Shogi by Using Move Sequence Trees

Presentation on theme: "Improving Strategic Play in Shogi by Using Move Sequence Trees"— Presentation transcript:

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

2 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

3 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

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

5 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

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

7 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

8 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

9 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

10 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

11 ２六歩(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

12 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

13 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

14 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