ミニマックス法はわかったけどソースコードがわからない（AIプログラミング 第４回）

はじめに

三目並べに限らず、チェスや将棋などの対戦ゲームでは何手目か先まで読んで一番良い手を打ちます。もし最後までの全通りを読めれば最強です。

それをコンピュータでやってしまおうというのが今回の試みです。

木構造（ツリー構造）とは？

局面が枝分かれして木のようなデータ構造のことをいいます。（始まりを「根（ルート）」、分かれ道を「枝（エッジ）」、次の局面を「節点（ノード）」、最終局面を「葉（リーフ）」と呼ぶことが多いです）

「ここに打てば相手はこう打ってきて、次はあそこに打とう」「こっちに打てばあそこに打たれたら負ける」と人が考えるのを「ゲーム木（木構造）」といい、機械学習などでよく使われます。

「完全ゲーム木」を使えば、全通りを試してみて最良を手を探すことが出来ます。

ミニマックス法とは？

コンピュータに思考させるためのアルゴリズムの一つです。簡単にいうと「自分の手と相手の手に点数を付けて一番有利な次の手を探す方法」です。

自分が打てる手に複数の候補がある時に最高maxの点数の手、相手が打てる手に複数の候補がある時に最低mini（相手にとっては最高）の点数の手を選びます。それを最終局面「葉」から現在の局面「根」までさかのぼって計算して繰り返します。

オセロや将棋だと最終局面まで全通り（完全ゲーム木）で読み切るには局面が膨大になりすぎて、計算処理する多大な時間が必要になります。（オセロの必勝法はまだ解析されていません。昔なにかで解析まで100年以上かかるような記事を見ました。６×６のオセロは後手必勝で解析の処理時間は100時間以内らしいです）また数手先までのゲーム木だと点数の付け方が難しいです。

ミニマックス法はわかったけど、どのようにプログラミングをすればいいかわかりません。

qiita.com

見つけました。こちらのサイトにPythonのソースコードとミニマックス法が詳しく解説されています。早速プログラムを拝借させていただきました。

動きました。AIと勝負しても勝てませんでした。
すごく短いプログラムで感動しました。じっくり解読していきます。いろんな技が使われていてとても勉強になります。ここでどうしても理解できない部分が出てきました。

「再帰関数」

def関数の中に自分自信を呼び出す関数があり、ループしているように見えます。

ググってみると「再帰」という言葉が見つかりました。説明を読んでも難しそうだったので簡単な例から実際の動きを追ってみたいと思います。

例：

def func(n):
    if n <= 0:
        return n
    return n + func(n-1)

print(func(10))

実行してみると「55」（1から10の和）が表示されました。

print(func(10))

func関数を「n=10」で呼び出しています。

return n + func(n-1)

func(10)で「10 + func(9)」を返します。
func(9)で「9 + func(8)」を返します。
func(8)で「8 + func(7)」を返します。
　　　：
func(1)で「1 + func(0)」を返します。
func(0)で（if n <= 0:）「0」を返します。

一行にまとめます

func(10)で「10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0」を返します。

つまり、print(func(10))で「55」を表示することになります。

なんとなく「再帰関数」の基本はわかったような気がしますが、まだしっくり来てないです。（このままミニマックス法に移っても再帰関数でつまづきそう）

次回は、再帰関数についてもう少し深く勉強していきたいと思います。