1.概要
AlphaGoの勉強過程で３目並べを学んでいます。考え方の基礎を知る上で大切なことであると思いネット上の資料も参考にしています。まず、参考資料を参照して、３目並べのルールを記述したClassを作成し、手入力、ランダム入力、minimax法、alphabeta法の対戦ができることを実現しました。今回は、montecarlo法に関して記述します。
2.詳細
(1) 概要
前回記述した３目並べのルールに関しては、do_game(self, action)を実行することでゲームが進行するようにしたものを活用します。minimax法に関して、すべての手順(9!=362880)を調べて、ある手を打った場合に、勝利する場合の数、敗退する場合の数、引き分ける場合の数を計算して、勝利する場合の数が高かった手を打つことにしました。
先手番をminimax法、後手番をalphabeta法にするとdraw(引き分け)になります。しかし、毎回同じパターンを繰り返します。同じ選択基準である手が複数ある場合でも最初の手を選択していたことが原因でした。そこで、複数の選択基準がある場合は乱数を利用して手を選択する方式を追加しました。これで様々な場面を見ることができるようになりました。
(a) tictactoe.py ゲームルール(alphabeta法と同じ)
(b) montecarlo.py 先手(minimax)、後手(montecarlo)の対戦
(2) 詳細
(a) tictactoe.py
class Tictactoe:
def __init__(self, fields=None):
self.fields = fields if fields != None else [0] * 9
self.myturn = True
self.data = [[0,1,2],[3,4,5],[6,7,8],
[0,3,6],[1,4,7],[2,5,8],
[0,4,8],[2,4,6]]
def do_game(self, action):
self.fields[action] = self.do_play()
check = self.do_check()
self.myturn = not(self.myturn)
return check
def undo_game(self, action):
self.fields[action] = 0
self.myturn = not(self.myturn)
def do_play(self):
if self.myturn == True:
return 1
else:
return -1
def do_check(self):
if self.is_win() == True:
return self.do_play()
if self.is_draw() == True:
return 0
return None
def is_win(self):
for i in range(8):
count = 0
for j in range(3):
count = self.fields[self.data[i][j]] + count
if count == 3 or count == -3:
return True
return False
def is_draw(self):
count = 0
for i in range(9):
if self.fields[i] == 0:
count += 1
if count == 0:
return True
else:
return False
def is_reach(self):
for i in range(8):
count = 0
action = None
for j in range(3):
count = self.fields[self.data[i][j]] + count
if self.fields[self.data[i][j]] == 0:
action = self.data[i][j]
if count == 2 or count == -2:
return action
return None
def next_action(self):
actionlist = []
for i in range(len(self.fields)):
if self.fields[i] == 0:
actionlist.append(i)
return actionlist
def game_state(self):
str = ''
for i in range(9):
if self.fields[i] == 1:
str += 'o'
elif self.fields[i] == -1:
str += 'x'
else:
str += '_'
if i % 3 == 2:
str += '\n'
return str
(b) montecarlo.py
from tictactoe import Tictactoe
import random
def random_select(actions):
index = random.randint(0, len(actions) - 1)
return actions[index]
def input_select(actions):
while True:
print(actions)
action = int(input('select actions='))
if action in actions:
break
else:
print('input again')
return action
def montecarlo_select(actions):
if (len(actions) % 2) == 1:
flg = 1
else:
flg = 2
result = []
for action in actions:
reach = obj.is_reach()
if reach != None:
print("reach action ", reach)
return reach
score = obj.do_game(action)
init = [action,0,0,0]
minimax(obj.next_action(), init)
result.append(init)
obj.undo_game(action)
maxvalue = -1
maxaction = None
maxlist = []
for item in result:
value = item[flg]
if value > maxvalue:
maxvalue = value
maxaction = item[0]
maxlist = [item[0]]
elif value == maxvalue:
maxlist.append(item[0])
if len(maxlist) != 1:
maxaction = maxlist[random.randint(0, len(maxlist) - 1)]
return maxaction
def alphabeta_select(actions):
if (len(actions) % 2) == 1:
flg = 1
else:
flg = 2
result = []
for action in actions:
reach = obj.is_reach()
if reach != None:
print("reach action ", reach)
return reach
score = obj.do_game(action)
init = [action,0,0,0]
minimax(obj.next_action(), init)
result.append(init)
obj.undo_game(action)
maxvalue = -1
maxaction = None
for item in result:
value = item[flg]
if value > maxvalue:
maxvalue = value
maxaction = item[0]
return maxaction
def minimax_select(actions):
if (len(actions) % 2) == 1:
flg = 1
else:
flg = 2
result = []
for action in actions:
score = obj.do_game(action)
init = [action,0,0,0]
minimax(obj.next_action(), init)
result.append(init)
obj.undo_game(action)
maxvalue = -1
maxaction = None
for item in result:
value = item[flg]
if value > maxvalue:
maxvalue = value
maxaction = item[0]
return maxaction
def minimax(actions, result):
for action in actions:
score = obj.do_game(action)
if score == 1:
result[1] += 1
elif score == -1:
result[2] += 1
elif score == 0:
result[3] += 1
else:
minimax(obj.next_action(), result)
obj.undo_game(action)
if __name__ == "__main__":
obj = Tictactoe()
actions = [0,1,2,3,4,5,6,7,8]
for i in range(9):
if obj.myturn == True:
print('my turn')
action = minimax_select(actions)
else:
print('other turn')
action = montecarlo_select(actions)
print(actions)
print("select", action)
result = obj.do_game(action)
print(obj.game_state())
if result == 1:
print("o Win")
break;
if result == -1:
print("x Win")
break;
if result == 0:
print("Draw")
break;
actions = obj.next_action()
(3) 評価
最強になったと思ったのですが、先手番が手入力と対戦すると勝てません（下図参照）。先手番で２箇所リーチを作る手順をプログラムは読みきれません。３目並べも中々難しいものです。
先手(4) -> 後手(8) -> 先手(0) の局面
o _ _
_ o _
_ _ x
この局面で、後手(2 or 6)以外は先手勝ちになります。しかし、プログラムは後手(5 or 7)を打ちます。後手のリーチで先手の２箇所リーチを防ぐことが必要ですが、この評価方法が難しい。
参考
AlphaZero 深層学習・強化学習・探索 人工知能プログラミング実践入門
布留川 英一 著
コメント
コメントを投稿