３目並べを利用したAlphaGo学習の整理 ( ランダム編 / ミニマックス編 / アルファベータ編 / モンテカルロ編 )
1.概要
The Wall Streat Journalの記事に、すべてを変えたAIの「第37手」今や至る所で、が掲載されました。10年前にAlphaGo碁がイ・セドルを勝った時です。その瞬間の感覚は忘れることができずAlphaGo碁の仕組みを知りたいと思って勉強を始めたことを思い出しました。
この記事は2023年の記事です。３目並べをプログラムすることでAlphaGoの学習をすることが目標でした。ロジックで３目並べを強くする考え方を順番に実施しています。当時とても苦労をしたので備忘録として残すことにしました。
AlphaGoの勉強過程で３目並べを学んでいます。考え方の基礎を知る上で大切なことであると思いネット上の資料も参考にしています。まず、参考資料を参照して、３目並べのルールを記述したClassを作成し、手入力とランダム入力の対戦ができることを実現しました。これをベースにして、今後、下記手順で作成したプログラムを改造して、３目並べを強くしていきます。
・ランダム編 ランダムに交互に打つ手順
・ミニマックス編 ３目並べの中心を早く選択する処理を追加
・アルファベータ編 ある手を打った後、勝利する確率が高い手を選択する処理を追加
・モンテカルロ編 勝利する確率が等しい場合、乱数で選択する処理を追加
ゲームAIのロジックは一見すると難しく難解に思えますが、「ランダム」から始めて「ミニマックス」「アルファベータ」と一歩ずつ段階を踏んで考えていくと、複雑なロジックも紐解かれ、解決策が少しずつ見えてきます。本記事では、私が実際に苦労しながら一歩ずつステップアップしていった試行錯誤のプロセスを記録しています。
2.詳細 ランダム編
(1) 概要
３目並べのルールに関しては、do_game(self, action)を実行することでゲームが進行するようにしました。actionは0から8までの数値で３目並べの９個のマス目を示します。２つのpythonコードを記述しました。
(a) tictactoe.py ゲームルール
(b) tttrandam.py 手入力とランダム入力の対戦
(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 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 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) tttrandam.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
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 = input_select(actions)
else:
print('other turn')
action = random_select(actions)
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.詳細 ミニマックス編
実現方法は参考資料とは少し異なります。その理由は参考資料に従うと先手がminimax法の場合に３目並べの中心(4の位置)を選択しません。この位置に着することが優位であると考えていたので、全ての手順を調べて初手が３目並べの中心位置であることを確認して、それを選択するようにプログラムしました。また、後手がminimax法の場合も良い手を打つように改良しました。
(1) 概要
前回記述した３目並べのルールに関しては、do_game(self, action)を実行することでゲームが進行するようにしましたものを活用します。minimax法に関して、すべての手順(9!=362880)を調べて、ある手を打った場合に、勝利する場合の数、敗退する場合の数、引き分ける場合の数を計算して、勝利する場合の数が高かった手を打つことにしました。初手が一番検討すべき手順が多いのですが、数秒で処理されます。
(a) tictactoe.py ゲームルール(minimax法を実現するために、undo_game(self,action)を追加)
(b) tttminimax.py minimax入力とランダム入力の対戦
(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 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) tttminimax.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 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 = random_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()
4.詳細 アルファベータ編
(1) 概要
前回記述した３目並べのルールに関しては、do_game(self, action)を実行することでゲームが進行するようにしましたものを活用します。minimax法に関して、すべての手順(9!=362880)を調べて、ある手を打った場合に、勝利する場合の数、敗退する場合の数、引き分ける場合の数を計算して、勝利する場合の数が高かった手を打つことにしました。
しかし、３目並ぶリーチ局面であるにもかかわらず、３目並ぶ手を選択せずに、２箇所の３目並べリーチとなる手を選択します。そこで、alphabeta法として無駄な処理を刈り取るために、リーチ局面の場合はリーチから勝ちの手を選ぶ方法をminimax法に追加します。
先手番をminimax法、後手番をalphabeta法にするとdraw(引き分け)になり完成度が向上したと思います。
(a) tictactoe.py ゲームルール(alphabeta法を実現するために、is_reach(self)を追加)
(b) alphabeta.py 先手(minimax)、後手(alphabeta)の対戦
(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) alphabeta.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 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 = alphabeta_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()
5.詳細 モンテカルロ編
(1) 概要
前回記述した３目並べのルールに関しては、do_game(self, action)を実行することでゲームが進行するようにしたものを活用します。minimax法に関して、すべての手順(9!=362880)を調べて、ある手を打った場合に、勝利する場合の数、敗退する場合の数、引き分ける場合の数を計算して、勝利する場合の数が高かった手を打つことにしました。
先手番をminimax法、後手番をalphabeta法にするとdraw(引き分け)になります。しかし、毎回同じパターンを繰り返します。同じ選択基準である手が複数ある場合でも最初の手を選択していたことが原因でした。そこで、複数の選択基準がある場合は乱数を利用して手を選択する方式を追加しました。これで様々な場面を見ることができるようになりました。
(a) tictactoe.py ゲームルール(alphabeta法と同じなので省略）
(b) montecarlo.py 先手(minimax)、後手(montecarlo)の対戦
(2) 詳細
(a) tictactoe.py（省略します）
(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」または「6」に打たなければ先手の勝ちが確定してしまいます。しかし、プログラムは「5」または「7」を選択してしまいました。後手のリーチで先手の２箇所リーチを防ぐことが必要ですが、この評価方法がうまく機能していません。
原因の考察
この原因は、今回のプログラムが「ミニマックス（minimax）法」の本来の定義である「相手が常に最善手を打ってくる（自分にとって最も不利な手を選んでくる）」というロジックではなく、「その手を打った先にある『勝ちパターンの総数（累積数）』」を評価基準にしてしまっているためです。
この結果、「1手後にすぐ負ける致命的なルート」があっても、他の分岐に多くの勝ちパターンがあれば、AIはその手を「良い手」と誤認してしまいます。この未来の勝ちマスの数に惑わされ、相手の最善の妨害を読みきれなかったことが敗因です。
6. 所見
三目並べの全ケース計算は可能ですが、今回の実装では負けパターンも発生しました。しかし、失敗の理由を一歩ずつ紐解くことで、ロジックの弱点という解決策のヒントが見えてきました。難しいロジックも最初から完璧を目指さず、ステップを踏んで課題をクリアすれば道は開ける、というのが本作を通じた最大の学びです。今後はこの経験を活かし、次はCNN（畳み込みニューラルネットワーク）を用いたアプローチを検証します。
参考書籍
AlphaZero 深層学習・強化学習・探索 人工知能プログラミング実践入門
布留川 英一 著
記事の更新
2026/08/19
コメント
コメントを投稿