Improving Strategic Play in Shogi by
Using Move Sequence Trees
Reijer Grimbergen
Department of Informatics
Yamagata University
2007/11/11
GPW2007
1
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
2
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
3
Opening play in shogi
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
6
9
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
0
0
0
0
0
0
0
0
0
0
0
0
玉（美濃囲い）
2007/11/11
金（美濃囲い）
GPW2007
銀（美濃囲い）
4
The problems of hill-climbing
1） 4八玉
3八玉
2八玉
2） 3八銀
4八玉
5八金(69)
3） 5八金(69)
3八銀
3八銀
4八玉
5八金(69)
3九玉
2八玉
3九玉
2八玉
：
：
2007/11/11
GPW2007
5
The problems of hill-climbing
6七金(58)
6八金(58)
2007/11/11
6七金(68)
GPW2007
6
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
7
Extracting move sequences
Move sequence extraction
1. Collect games with a with a specific opening
strategy
2. Collecting move frequency data
3. Generate a move sequence tree
2007/11/11
GPW2007
8
Collecting games
Find all games with a finished castle
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
9
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 (%)
Move
Fr (%)
Move
Fr (%)
Move
Fr (%)
7六歩(77)
100
6八銀(79)
78
4六歩(47)
32
9六歩(97)
20
6六歩(67)
99
7七銀(68)
78
3五歩(36)
29
7五歩(同)
16
5八金(49)
99
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)
71
2四歩(25)
24
5五歩(同)
12
5六歩(57)
91
7九玉(69)
69
5七銀(48)
24
8六銀(77)
11
4八銀(39)
89
2五歩(26)
60
3八飛(28)
23
7七銀(88)
11
2六歩(27)
89
6八角(79)
47
4六銀(37)
23
5五歩(56)
10
3六歩(37)
84
3七銀(48)
45
7八玉(68)
21
5八飛(28)
10
7九角(88)
83
3七桂(29)
38
8八玉(78)
21
2007/11/11
GPW2007
10
876
6
976
２六歩(27)
２六歩(27)
４八銀(39)
549
85
5
５八金(49)
2813
Start
７六歩(77)
６六歩(67)
3
５六歩(57)
７八金(69)
15
14
12
６八玉(59)
2007/11/11
32
27
3
2
942
58
5
4
80
５八飛(28)
9
5
2
360
６六歩(67)
４八銀(39)
６八銀(79)
Same
position
７八金(69)
517
６六歩(67)**
６八銀(79)
315
７七角(88)
７八銀(79)
7
８八銀(同角)
5
１六歩(17)
５六歩(57)
3
２二角成(88)
2
５八金(49)
2
GPW2007
５六歩(57)
４八銀(39)
２六歩(27)
７八金(69)
５八飛(28)
６八玉(59)
３六歩(37)
７七銀(68)
1
１六歩(17)
11
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
12
Preliminary results
Version
Won
Lost
WP
Yagura
MST
OTO
MST25
23
27
46%
20
21
MST50
27
23
54%
32
20
MST75
28
22
56%
27
15
MST100
25
25
50%
23
15
2007/11/11
GPW2007
13
Conclusions and future work
Conclusions
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
14

高導電 極薄両面テープ （PDF：272KB）