『囲碁ディープラーニングプログラミング』を引き続き読んでいる。
肝心のディープラーニングの内容についての部分まで、なかなか到達しそうにない(^_^;
今回は、「三目並べ」である。
囲碁AIが次の一手を決めるとき、妥当な次の一手のリストを作成し、そのリストのそれぞれについて、相手がどう打つか、それに対して自分がどうするか、先まで読んで、その一手についての結論を出す。
その検討を次の一手のリスト全てについておこなう。その結果で次の一手を決定する。そのアルゴリズムがこれである。
ただ、これはこのゲームだからできるので、このアルゴリズムは時間がかかりすぎる。
さて、このアルゴリズム minimax探索の根幹はこのbest_result 関数である。
この関数では再帰処理を使っている。
<A>の部分が終了条件である。
game_stateが is_over() であるとき、
winner() が next_player すなわち 自分であるとき、GameResult.win が返る。
winner() が None すなわち 勝者がいないときは、GameResult.draw が返る。
その他は、GameResult.loss が返る。def best_result(game_state):
# <A> 終了条件
if game_state.is_over():
if game_state.winner() == game_state.next_player:
return GameResult.win
elif game_state.winner() is None:
return GameResult.draw
else:
return GameResult.loss
# <B> 次の手を求める処理
best_result_so_far = GameResult.loss # <1>
opponent = game_state.next_player.other # <2>
for candidate_move in game_state.legal_moves(): # <3>
next_state = game_state.apply_move(candidate_move) # <4>
opponent_best_result = best_result(next_state) # <5>
our_result = reverse_game_result(opponent_best_result) # <6>
if our_result.value > best_result_so_far.value: # <7>
best_result_so_far = our_result # <8>
return best_result_so_far # <9>
# best_result_so_far -- これまでの最高の結果<B>が次の手を求める処理で、再帰処理をしながら最終的に <A> の終了条件に
いきつく。
<1> -- best_result_so_far に GameResult.loss をセットしておく。
<2> -- opponent を相手とする。
<3> -- game_state.legal_move() -- 妥当と思われる次の手のリストを返す。
candidate_move -- そのリストを１つひとつ candidate_move として
検討する。
<4> -- next_state -- candidate_move すなわち、検討すべき次の手を適用し
た局面。
<5> -- その next_state を引数として、この best_result を実行する。例えば以下のような局面があったとする。
A B C
1|o| |
2|x|x|
3| | |
今、黒は B2 と打ったところである。
(1) B1(o)-(row=1,col=2)と打つ手から検討する。
A B C
1|o|o|
2|x|x|
3| | |
それに対して黒(x)は、C1、C2、A3、B3、C3 という手が考えられる。
(1-1) 黒(x)が C1(row=1,col=3) と打った場合
next_state.next_player == Player.black
A B C
1|o|o|x
2|x|x|
3| | |
(1-1-1) それに対して白(o)が C2(row=2,col=3) と打った場合
next_state.next_player == Player.white
A B C
1|o|o|x
2|x|x|o
3| | |
(1-1-1-1) それに対して黒(x)が A3(row=3,col=1) と打った場合
next_state.next_player === Player.black
opponent_best_result our_result
GameResult.win --> reverse --> GameResult.loss
A B C
1|o|o|x
2|x|x|o
3|x| |
(1-1-1-2) 次は黒(x)が B3(row=3,col=2) と打った場合
next_state.next_player === Player.black
A B C
1|o|o|x
2|x|x|o
3| |x|
(1-1-1-2-1) それに対して白(o)が A3(row=1,col=2) と打った場合
next_state.next_player === Player.white
opponent_best_result our_result
GameResult.draw --> reverse --> GameResult.draw
A B C
1|o|o|x
2|x|x|o
3|o|x|他にもいろいろな結果が考えられるが、
(1-1)のように、黒(x)が C1(row=1,col=3) と打った場合には、
GameResult.loss と GameResult.draw の2種類の結果が得られる。
黒(x)も best_result関数を使って GameResult.win の手を探し出す。
(1)の白(o)B1 という手については、黒が C3 (GameResult.win) という手を見つけだす。だから、白(o)B1 という手は、GameResult.loss という値を返すことになる。
白(o)は、B1, C1, C2, A3, B3, C3 と、順に best_result関数を使って最善手を探す。B1 は GameResult.loss であったが、C1, A3, B3, C3 については、黒(x)が C2 と打てば GameResult.loss という値が返ってくるので、白(o)の C2 という手のみが GameResult.draw もしくは GameResult.winという値を返すことになる。
『囲碁ディープラーニングプログラミング』
Max Pumperia、Kevin Ferguson 著
山岡忠夫 訳
マイナビ出版
2019年4月22日 初版第1刷
