SQLでオセロAIを実装する夢をPythonに託す
こんにちは。コグラフ株式会社データアナリティクス事業部の塩見です。
SQLはとてもおもしろい言語です。原因と結果の関係を記述するだけで、結果からさかのぼって原因を知るようなことが簡単にできます。
SELECT * FROM 原因, 結果 WHERE 結果 = 成功原因テーブルと結果テーブルの間にカンマがあります。この書き方に馴染みのない方もいらっしゃると思います。このカンマはCROSS JOINだと思ってください。つまりこのコードは SELECT * FROM 原因 CROSS JOIN 結果 WHERE 結果=成功 という意味です。
そして私は、SQLの強力な記述能力を使えばオセロゲームのAIも作れそうだと考えました。
SELECT * FROM 局面1, 局面2, … , 最終局面 WHERE 最終局面 = 勝利つまり、関係演算が知的な振る舞いの源泉になるのではないかと夢想したのです。実際には記述力の限界や計算量の問題から実現できませんでしたが、このアイデアを近似的に実行するPythonのコードを書きました。Google Colaboratoryで動きますので、ぜひ試してみてください。
基本的な方針
オセロのすべての局面の組み合わせを計算するのは現実的ではないので、一部分だけを考えることにします。コマを置く場所をランダムに選び、それを最後まで繰り返します。最終局面では勝敗がはっきりわかるので、最初にコマを置いた場所と勝敗の関係がわかります。このような試合をたくさん繰り返し、確率的に関係を考えると、どこにコマを置くと勝ちやすいのかわかってくるのです。
舞台の設定
局面を意味するFrameというクラスを作成し、その中に必要な変数やメソッドを定義していきます。
クラスを使ったことがない方へ
データサイエンスの勉強をしていますと、クラスを使う機会が少ないですよね。オセロゲームのような親しみやすいテーマで慣れていただけたらうれしいです。
class Frame:
def __init__(self):
# 空白(0)の盤面(cells)を100個つくる
self.cells = [0] * 100
# cellsの周囲を壁(-1)にする
for i in range(10):
self.cells[pos(i, 0)] = -1
self.cells[pos(i, 9)] = -1
self.cells[pos(0, i)] = -1
self.cells[pos(9, i)] = -1
# 真ん中の4箇所にコマを置く 1: 白, 2: 黒
self.cells[pos(4, 4)] = 1
self.cells[pos(5, 5)] = 1
self.cells[pos(4, 5)] = 2
self.cells[pos(5, 4)] = 2
# ゲームを制御する変数たち
self.player = 2
self.pass_num = 0
self.seq = 1
self.first_player = self.player
self.first_pos = None
# 続く白と黒のコマを置く盤面(cells)を作成します。cellsは一次元のリストですが10個ずつ並べて横方向にi、縦方向にjという座標をとって二次元的に解釈することにしましょう。
ところでオセロゲームの盤面は8x8のはずですが、cellsは10x10としています。これは周囲に壁を設置するためです。-1という値で壁を表すことにしました。なぜ壁を設置するのかといいますと、その方がコマを置く処理が簡単に書けるからなんです。壁が存在する設計にしておけば、一マスずつ値を見ながら調べていく処理で、壁だったら終わりと素直に書くことができるのです。posは座標(i, j)からリストの位置を計算する補助関数です。Frameクラスの外側でこのように定義しています。
# 座標i, jからリストの位置を計算する補助関数
def pos(i, j):
return j * 10 + iそして、盤面（cells）の真ん中4箇所にコマを置きます。1が白、2が黒です。playerは、現在の局面（frame）におけるプレイヤーの色を示し、初期値は2（黒）です。pass_numはパスの回数を記録し、2回連続でパスすると、どちらのプレイヤーもコマを置けなくなり、試合終了となります。seqは局面の番号を示し、最初の局面（seq=1）のみ特別な処理を行います。
first_playerには最初の局面におけるプレイヤーの色を、first_posには最初の局面でコマを置いた場所を保存します。最初の手と勝敗の関係を知るために、最初の手だけは記録しておく必要があるためです。
描画処理
盤面(cells)を描画するメソッドdraw()をこのように書きました。cellsの値によって場合分けしてprintしているだけです。
class Frame:
# 続き
# 盤面(cells)を描画する
def draw(self):
for j in range(10):
for i in range(10):
if self.cells[pos(i, j)] == 0:
print('.', end=' ')
elif self.cells[pos(i, j)] == 1:
print('o', end=' ')
elif self.cells[pos(i, j)] == 2:
print('x', end=' ')
elif self.cells[pos(i, j)] == -1:
print('*', end=' ')
print('')
# 続くFrameのインスタンスを作ってdraw()を実行してみましょう。
frame = Frame()
frame.draw()
コマを置いてひっくり返す
プレイヤー黒と白が交互に、ランダムにコマを置いていきます。その実装を書いていきましょう。
ひっくり返せるコマの数を確認
checkメソッドは、指定した(i, j)座標にコマを置いたとき、相手のコマをいくつひっくり返せるかを確認します。戻り値は、ひっくり返せるコマの数です。ただし、このメソッドで確認できるのは一方向だけです。確認する方向は、viとvjで指定します。例えば、(vi, vj)が(1, 0)なら右方向、(vi, vj)が(-1, 1)なら左斜め下方向を確認します。
class Frame:
# 続き
# ひっくり返せるコマの数を確認
def check(self, i, j, vi, vj):
opponent = 3 - self.player
counter = 1
while(True):
next_cell = self.cells[pos(i+vi*counter, j+vj*counter)]
if next_cell == opponent:
counter += 1
elif next_cell == self.player:
return counter-1
elif next_cell == -1:
return 0
elif next_cell == 0:
return 0
# 続くoppenentは相手のコマの色です。3から自身のコマの色を引き算して相手のコマの色opponentを求めています。
counterはひっくり返せるコマを数える変数です。初期値を1として条件があえば増やしていきます。
となりのマス(next_cell)が相手のコマ(opponent)である限りcounterを増やし続けて、さらにとなりのマスを調べていきます。マスが自身のコマ(player)であればひっくり返せるコマの数はcounter-1個と判定しています。壁(-1)か空白(0)であればひっくり返せるコマは0個とします。
マスにコマを置けるか確認
is_legalメソッドは盤面の指定した(i, j)座標のマスにコマを置くことができるかどうか判定します。戻り値はTrueかFalseです。
class Frame:
# 続き
# マスにコマを置けるか確認
def is_legal(self, i, j):
if self.cells[pos(i, j)] != 0: return False # 空白(0)でない場所には置けない
elif self.check(i, j, 1, 0) > 0: return True
elif self.check(i, j, 1, 1) > 0: return True
elif self.check(i, j, 0, 1) > 0: return True
elif self.check(i, j, -1, 1) > 0: return True
elif self.check(i, j, -1, 0) > 0: return True
elif self.check(i, j, -1, -1) > 0: return True
elif self.check(i, j, 0, -1) > 0: return True
elif self.check(i, j, 1, -1) > 0: return True
else: return False
# 続く先ほど定義したcheckメソッドを上下左右斜めの8方向に適用しているだけです。ひっくり返せるコマの数が正であればTrueと判定しています。
コマを置けるマスを探してリストに入れる
searchメソッドは盤面全体からコマを置けるマスを探してリストに入れます。戻り値はそのリストです。
class Frame:
# 続き
# コマを置けるマスを探してリストに入れる
def search(self):
legal_cells = []
for j in range(1, 9):
for i in range(1, 9):
if self.is_legal(i, j):
legal_cells.append(pos(i, j))
return legal_cells
# 続く最初legal_cellsリストを空にしておいて、is_legalであればlegal_cellsに追加していっています。
コマを置いて相手のコマをひっくり返す
putメソッドは指定された場所に自分のコマを置き、相手のコマをひっくり返します。戻り値はありません。
class Frame:
# 続き
# コマを置いて相手のコマをひっくり返す
def put(self, i, j):
self.cells[pos(i, j)] = self.player
for vi in [-1, 0, 1]:
for vj in [-1, 0, 1]:
n = self.check(i, j, vi, vj)
for k in range(n):
self.cells[pos(i+(k+1)*vi, j+(k+1)*vj)] = self.player
# 続く盤面の走査方向を制御する変数viとvjの組み合わせを作って、それぞれの方向に対してcheckメソッドでひっくり返せるコマの数nを調べます。そして、その方向のn個のマスの色を自分のコマの色に書き換えるのです。
ちなみに、(vi, vj) = (0, 0)という意味のない組み合わせの走査も発生するのですが、特に影響がないのでそのまま走査させています。コードが単純で済みますので。
ランダムにコマを置く
moveメソッドは、試合の局面を一歩進めます。戻り値はありません。
import random
# リストの位置(pos)から座標iを計算する補助関数
def index_i(pos):
return pos % 10
# リストの位置(pos)から座標jを計算する補助関数
def index_j(pos):
return pos // 10
class Frame:
# 続き
# ランダムにコマを置く
def move(self):
legal_cells = self.search()
if len(legal_cells) == 0:
self.pass_num += 1
else:
random.shuffle(legal_cells)
pos = legal_cells[0]
self.put(index_i(pos), index_j(pos))
self.pass_num = 0
if self.seq == 1: # 初手の場合の処理
self.first_player = self.player
self.first_pos = pos
self.player = 3 - self.player
self.seq += 1
# 続く盤面からコマを置けるマスを探して、見つかったマスからランダムに一つ選んで、そこにコマを置きます。見つからなければパス回数(pass_num)を一つ増やします。そして、playerを相手のコマの色に変更し、局面番号(seq)を一つ増やして終了します。
これで準備が整いました。
試合開始
moveを実行すると盤面にランダムにコマが置かれ、相手のコマをひっくり返します。moveを1回実行してその結果を見てみましょう。
frame = Frame()
frame.move()
frame.draw()するとこのように局面が1回進みます。（ランダムなので、別のところにコマが置かれている場合もあります。）
moveをたくさん繰り返すと、playerを交代しながら局面がたくさん進みます。
frame.move()
frame.move()
frame.move()
frame.move()
frame.move()
frame.draw()
パス回数が2より少ない間はmoveを実行し続けましょう。そうすると勝負が決まります。
while(frame.pass_num < 2):
frame.move()
frame.draw()
どちらが勝ったのでしょう。黒(2)の個数を数えてみましょう。
print(frame.cells.count(2))この結果は24でした。（実行するたびにランダムに変わります。）
オセロの盤面は64マスなので、32マス以上ないと負けてしまいます。したがって黒(2)の負けですね。
初手と勝敗の関係を探る
ところで初手は何だったでしょうか。frameに記録してありますので見てみましょう。
print(index_i(frame.first_pos), index_j(frame.first_pos), frame.first_player)この結果は
4 3 2
でした。（実行するたびにランダムに変わります。）
つまり初手は(i, j)=(4, 3)の位置に黒(2)を置いたのでした。そして、試合の結果は黒の負けでした。
このような試合を何度も何度も繰り返していけば、初手(i, j)=(4, 3)の位置に黒(2)置いた場合に、勝てる率が何パーセントかわかってしまうのです。初手と勝敗の関係がわかるので、オセロゲームのAIを作ることができてしまいました。まさに冒頭で紹介したSQLでやりたかったことです。確率的にではありますがPythonで実装することができました。
-- やりたかったこと
SELECT * FROM 局面1, 局面2, … , 最終局面 WHERE 最終局面 = 勝利ちょっと補足
オセロの本当の初手には対称性があり、どの位置においても勝率は同じという性質があることをご存知の方は、上記の説明をおかしく感じたかもしれません。実は初手だけを探るのではなくて、中盤についても探り続けるのだと考えてください。中盤の配置から、その次の手を探ることも同じコードで実現できるのです。
データ分析に興味のある方募集中！
コグラフ株式会社データアナリティクス事業部ではPythonやSQLの研修を行った後、実務に着手します。
研修内容の充実はもちろん、経験者に相談できる環境が備わっています。
このようにコグラフの研修には、実務を想定し着実にスキルアップを目指す環境があります。
興味がある方は、下記リンクよりお問い合わせください。
X(Twitter)もやってます！
コグラフデータ事業部ではX(Twitter)でも情報を発信しています。
データ分析に興味がある、データアナリストになりたい人など、ぜひフォローお願いします！
📢Wantedly新掲載！
— アラリコ@コグラフ株式会社 | データ事業部 (@CographData) July 14, 2023
「データに興味がある」
「データに携わる仕事がしたい」
そこのあなた！
私たちと一緒にデータ分析しませんか？
IT業界未経験の方も大歓迎です☺️#エンジニア転職 #データ分析 #駆け出しエンジニアと繋がりたいhttps://t.co/S9o7VSjGRt
コードまとめ
記事ではコードが小間切れになっていますので、最後にひとまとめにしておきます。
import random
# 座標i, jからリストの位置を計算する補助関数
def pos(i, j):
return j * 10 + i
# リストの位置(pos)から座標iを計算する補助関数
def index_i(pos):
return pos % 10
# リストの位置(pos)から座標jを計算する補助関数
def index_j(pos):
return pos // 10
class Frame:
def __init__(self):
# 空白(0)の盤面(cells)を100個つくる
self.cells = [0] * 100
# cellsの周囲を壁(-1)にする
for i in range(10):
self.cells[pos(i, 0)] = -1
self.cells[pos(i, 9)] = -1
self.cells[pos(0, i)] = -1
self.cells[pos(9, i)] = -1
# 真ん中の4箇所にコマを置く 1: 白, 2: 黒
self.cells[pos(4, 4)] = 1
self.cells[pos(5, 5)] = 1
self.cells[pos(4, 5)] = 2
self.cells[pos(5, 4)] = 2
# ゲームを制御する変数たち
self.player = 2
self.pass_num = 0
self.seq = 1
self.first_player = self.player
self.first_pos = None
# 盤面(cells)を描画する
def draw(self):
for j in range(10):
for i in range(10):
if self.cells[pos(i, j)] == 0:
print('.', end=' ')
elif self.cells[pos(i, j)] == 1:
print('o', end=' ')
elif self.cells[pos(i, j)] == 2:
print('x', end=' ')
elif self.cells[pos(i, j)] == -1:
print('*', end=' ')
print('')
# ひっくり返せるコマの数を確認
def check(self, i, j, vi, vj):
opponent = 3 - self.player
counter = 1
while(True):
next_cell = self.cells[pos(i+vi*counter, j+vj*counter)]
if next_cell == opponent:
counter += 1
elif next_cell == self.player:
return counter-1
elif next_cell == -1:
return 0
elif next_cell == 0:
return 0
# マスにコマを置けるか確認
def is_legal(self, i, j):
if self.cells[pos(i, j)] != 0: return False # 空白(0)でない場所には置けない
elif self.check(i, j, 1, 0) > 0: return True
elif self.check(i, j, 1, 1) > 0: return True
elif self.check(i, j, 0, 1) > 0: return True
elif self.check(i, j, -1, 1) > 0: return True
elif self.check(i, j, -1, 0) > 0: return True
elif self.check(i, j, -1, -1) > 0: return True
elif self.check(i, j, 0, -1) > 0: return True
elif self.check(i, j, 1, -1) > 0: return True
else: return False
# コマを置けるマスを探してリストに入れる
def search(self):
legal_cells = []
for j in range(1, 9):
for i in range(1, 9):
if self.is_legal(i, j):
legal_cells.append(pos(i, j))
return legal_cells
# コマを置いて相手のコマをひっくり返す
def put(self, i, j):
self.cells[pos(i, j)] = self.player
for vi in [-1, 0, 1]:
for vj in [-1, 0, 1]:
n = self.check(i, j, vi, vj)
for k in range(n):
self.cells[pos(i+(k+1)*vi, j+(k+1)*vj)] = self.player
# ランダムにコマを置く
def move(self):
legal_cells = self.search()
if len(legal_cells) == 0:
self.pass_num += 1
else:
random.shuffle(legal_cells)
pos = legal_cells[0]
self.put(index_i(pos), index_j(pos))
self.pass_num = 0
if self.seq == 1: # 初手の場合の処理
self.first_player = self.player
self.first_pos = pos
self.player = 3 - self.player
self.seq += 1
frame = Frame()
frame.draw()
frame.move()
frame.draw()
frame.move()
frame.move()
frame.move()
frame.move()
frame.move()
frame.draw()
while(frame.pass_num < 2):
frame.move()
frame.draw()
print(frame.cells.count(2))
print(index_i(frame.first_pos), index_j(frame.first_pos), frame.first_player)
この記事が気に入ったらサポートをしてみませんか？