Python 再帰関数をもう少し詳しく学ぶ（AIプログラミング 第６回）

はじめに

実践で「再帰関数」を使ってみようと思ったのですが、少し気になったことがあったのでもう少し詳しく学んでいきます。

応用（動きを追いかける）

前回の最後の例を少し変えました。

def func4(n):
    if n >= 3:
        return
    for i in range(2):
        #print("n=", n,"i=", i)
        # 再帰
        func4(n+1)
        print("n=", n,"i=", i)
    return

func4(0)

値の表示を「再帰」の後にもってきてみました。

for文に書き直して考えてみます。

for i in range(2):
    for j in range(2):
        for k in range(2):
            print("n=", 2,"k=", k)
        print("n=", 1,"j=", j)
    print("n=", 0,"i=", i)

結果はこちらです。

n= 2 k= 0
n= 2 k= 1
n= 1 j= 0
n= 2 k= 0
n= 2 k= 1
n= 1 j= 1
n= 0 i= 0
n= 2 k= 0
n= 2 k= 1
n= 1 j= 0
n= 2 k= 0
n= 2 k= 1
n= 1 j= 1
n= 0 i= 1

図にするとこうなります。

「再帰関数」の前に記述すると上から処理していきますが、「再帰関数」の後に記述すると下から処理していくのがわかります。

「ゲーム木」で「再帰関数」を扱う場合は、下から処理していく必要があります。

三目並べのゲーム木（ミニマックス法）

拡大します。この部分で解説していきます。

プログラムの作り方

「再帰関数」を作ってその後に処理をします。上の図では①～⑫の順で処理することになります。

勝敗が決まった場合（引き分けも含みます）

・評価点をつけます。勝った時は「10 - [深さ] 」点、負けた時は「[深さ] - 10 」点、引き分けの時は０点にします。（早く勝てば点数が高く、早く負けると点数が低い）

・その「再帰関数」は終了して、評価点を返します。

勝敗が決まっていない場合（まだ手が打てる場合）

・自分（ＡＩ）のターンの時は、（一つ下の深さの評価点から）一番低い点数を引き継ぎます。※相手に打たれると一番都合の悪いルートを選びます。

・相手（プレイヤー）のターンの時は、（一つ下の深さの評価点から）一番高い点数を引き継ぎます。※自分が打てる一番良いルートを選びます。

　　深さが一番上の場合（n = 0）

　　・すべての「再帰関数」が終了し、打つ場所の値を返します。

　　深さが一番上でない場合（n > 0）

　　・その「再帰関数」は終了して、評価点を返します。

ちょっと細かいところまで詰められていませんが、この流れでいけそうです。

次回は、ミニマックス法を使って三目並べを作成したいと思います。