minimax探索だと時間がかかりすぎるので、時間短縮の方法として、探索木の深さを制限する。
今回は DEPTH=3 とした。
たとえば、以下のような局面があるとする。
A B C
1|x| | |
2| | | |
3| | | |白の手としては、いろいろ考えられる。が、それを深さ 3 までしか考えないとする。
DEPTH=3 DEPTH=2 DEPTH=1 DEPTH=0
(パターンA)
A B C A B C A B C A B C
1|x|o| | 1|x|o| | 1|x|o| | 1|x|o| | 局面評価
2| | | | -> 2| |x| | -> 2| |x| | -> 2|x|x| | ->
3| | | | 3| | | | 3| | |o| 3| | |o|
(パターンB)
A B C A B C A B C A B C
1|x| | | 1|x|x| | 1|x|x|o| 1|x|x|o| 局面評価
2| |o| | -> 2| |o| | -> 2| |o| | -> 2| |o| | ->
3| | | | 3| | | | 3| | | | 3|x| | |
さまざまなパターンが考えられるが、DEPTH=0 の時に局面を評価する関数を考えておく。
その関数の性能が良ければ、このAIは賢くなる。
今回はその関数については考えず、単に 0 を返すだけとする。
minimax.py
import enum
import random
from dlgo.agent import Agent
MAX_SCORE = 10
MIN_SCORE = -10
DEPTH = 3
def eval_situation(game_state):
return 0
# 深さで枝刈りされたミニマックス検索
def best_result(game_state, max_depth, eval_fn):
if game_state.is_over():
if game_state.winner() == game_state.next_player:
return MAX_SCORE + max_depth
elif game_state.winner() == game_state.next_player.other:
return MIN_SCORE - max_depth
else:
return 0
if max_depth == 0:
return eval_fn(game_state)
best_so_far = MIN_SCORE
for candidate_move in game_state.legal_moves():
next_state = game_state.apply_move(candidate_move)
opponent_best_result = best_result(next_state, max_depth - 1, eval_fn)
our_result = -1 * opponent_best_result
if our_result > best_so_far:
best_so_far = our_result
return best_so_far
# best_so_far -- これまでの最高
def print_best_moves(str, best_moves):
for move in best_moves:
print(str, move.point)
class MinimaxAgent(Agent):
def select_move(self, game_state):
best_moves = []
our_best_outcome = None
for possible_move in game_state.legal_moves():
print('possible_move %s %s' % (possible_move.point, game_state.next_player))
next_state = game_state.apply_move(possible_move) # <1>
opponent_best_outcome = best_result(next_state, DEPTH, eval_situation) # <2>
our_better_outcome = -1 * opponent_best_outcome # <3>
if our_best_outcome is None: # <4>
our_best_outcome = our_better_outcome
best_moves.append(possible_move)
elif our_best_outcome == our_better_outcome: # <5>
best_moves.append(possible_move)
elif our_best_outcome < our_better_outcome: # <6>
our_best_outcome = our_better_outcome
best_moves.clear()
best_moves.append(possible_move)
else:
print('負ける手なので、考慮の対象外')
print('our_better_outcome:%d our_best_outcome:%d' % (our_better_outcome, our_best_outcome))
if best_moves:
print_best_moves('best', best_moves)
return random.choice(best_moves)
else:
print('best_movesがないなんて、あり得ない...')
# <1> game_state.apply_move は、next_state を 相手側とする。
# つまり、possible_moveを適用した盤状況で、player は相手側であ
# る。
# <2> DEPTH -- 定数とした。
# <3> 相手が MAX_SCORE なら、こちら側は MIN_SCORE である。
# <4> our_best_outcome が None ならば、our_better_outcome の値を
# our_best_outcome に入れて、best_moves にその着手を入れる。
# <5> our_best_outcome と our_better_outcome が同じなら
# best_moves にその着手を追加する。
# <6> our_best_outcome よりも our_better_outcome の方が大きければ
# best_moves を空にして、その着手をリストに入れる。
実際にやってみる。
$ python3 play_ttt.py
A B C
1 | |
2 | |
3 | |
-- a1
A B C
1 X | |
2 | |
3 | |
possible_move Point(row=1, col=2) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=1, col=3) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=2, col=1) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=2, col=2) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=2, col=3) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=3, col=1) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=3, col=2) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=3, col=3) Player.o
our_better_outcome:0 our_best_outcome:0
best Point(row=1, col=2)
best Point(row=1, col=3)
best Point(row=2, col=1)
best Point(row=2, col=2)
best Point(row=2, col=3)
best Point(row=3, col=1)
best Point(row=3, col=2)
best Point(row=3, col=3)
A B C
1 X | |
2 | | O
3 | |
A1と黒（人間）が打った。それに対して、白（AI）はすべての着手を検討しているが、深さを3までにしているので、プログラムからは、0が返ってきている。
AIは、ランダムに手を選択して、C2とした。
-- b2
A B C
1 X | |
2 | X | O
3 | |
possible_move Point(row=1, col=2) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=1, col=3) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=2, col=1) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=3, col=1) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=3, col=2) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=3, col=3) Player.o
our_better_outcome:-10 our_best_outcome:-10
best Point(row=3, col=3)
A B C
1 X | |
2 | X | O
3 | | O
黒が B2 と打った。それに対して、白はすべての手を検討し、C3以外は -12 という点で負け。C3 でも負けなのだが、まだ勝負は続くので、max_depthの値が小さくなるので -10 という値になる。それで C3 を選択している。
ここで、黒は C1 と打つと黒の勝ちになるが、AIはどう判断するであろうか？
-- c1
A B C
1 X | | X
2 | X | O
3 | | O
possible_move Point(row=1, col=2) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=2, col=1) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=3, col=1) Player.o
our_better_outcome:-12 our_best_outcome:-12
possible_move Point(row=3, col=2) Player.o
our_better_outcome:-12 our_best_outcome:-12
best Point(row=1, col=2)
best Point(row=2, col=1)
best Point(row=3, col=1)
best Point(row=3, col=2)
A B C
1 X | | X
2 | X | O
3 O | | Oどこに打っても負けと見ている。白はA3を選択したが、これはたまたまである。
B1で黒の勝ちだが、わざとB3と打ってみることにする。
-- b3
A B C
1 X | | X
2 | X | O
3 O | X | O
possible_move Point(row=1, col=2) Player.o
our_better_outcome:0 our_best_outcome:0
possible_move Point(row=2, col=1) Player.o
負ける手なので、考慮の対象外
our_better_outcome:-12 our_best_outcome:0
best Point(row=1, col=2)
A B C
1 X | O | X
2 | X | O
3 O | X | O白は、B1 だと引き分け。A2 は負けとしている。
そこで、B1を選択している。
今後のこと
A B C
1 X | |
2 O | |
3 | | この局面は、黒の勝ちである。黒がB2と打てば、白は負けになる。
ということは、黒がA1と打ったときに、どこに打てば負けないかというと、これはなかなか難しい。B2、C3以外は負けだろうと思われる。
これを初期データとして組み込めばいいんだろうけど、AIに学習させれば面白いと思う。
機械学習って、そういうことなのだろうなと思った。
『囲碁ディープラーニングプログラミング』
Max Pumperia、Kevin Ferguson 著
山岡忠夫 訳
マイナビ出版
2019年4月22日 初版第1刷
