こんにちは。ヒトツメです。
前回は、CPUを作る上での考え方の一つとして、アルファベータ法による探索について考えていきました。
今回は、前回の考え方をベースにして、実装をしていこうと思うのですが、そこで非常に重要な考え方である、再帰関数を使いこなせる必要があります。
今日は再帰関数の考え方を、少し別の話題をベースに考えていきたいと思います。
再帰関数とは何か
そもそも、再帰関数とは、関数の中でその関数を呼び出すというものです。
それだけ聞くと意味が分からないので、例を交えて解説していこうと思いますが、一番簡単な例として使われるのが、階乗の計算式で、次のような実装です。
def Factorial(n):
if n <= 1:
return n
return n * Factorial(n - 1)
print(Factorial(5))この関数を実行すると、次のように、120という結果が得られます。
最初、Factorial関数に5という数字が入れられてこの関数が呼び出されると、まだifがTrueではないので、5とFactorial関数に4という数字が入れられて呼び出された結果を掛けた数字が返却されます。この時点では、Factorial関数に4という数字が入れられて呼び出された結果に何が入るかわからないので、Factorial関数に4という数字を入れてこの関数を呼び出しますが、その結果は、4とFactorial関数に3という数字が入れられて呼び出された結果を掛けた数字になります。
このような呼び出しが、Factorial関数に1という数字が入れられるまで続くと、ifがTrueとなり、初めてここで、返却値が決まります（n、つまり1が返却されます。）
これをすべて展開すると、5×4×3×2×1となり、「5!」つまり120が返却される、ということになります。
試しにこの関数に100を入れると、「93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000」というとんでもない数字が返却されます。
Googleで「100!」と検索すると、「9.332622e+157」となりますので、どうやらあってそうだ、とわかります。
何故再帰関数が必要か
さて、そんな再帰関数が、前回検討した内容の実装に、なぜ必要かというと、白番の選択肢の先に黒番の選択肢があり、さらにその先に白番の選択肢があり、その組み合わせを（枝刈りをしなければ）すべて検討する必要があるからです。
このような、全ての組み合わせを検討するときに、再帰関数はすごい威力を発揮します。
試しに、1~5までのすべての数字を1回ずつ使った数列の組み合わせを、全て書き出すということをやってみたいと思います。
1が使われれば2桁目は2~5のいずれか、2桁目に2が使われると3桁目は3~5のいずれかと、選択肢に変化が発生しながら、全ての組み合わせを書き出すということになるので、実装すると、次のようになります。
def myfunc(my_list):
if len(my_list) == 1:
return [my_list]
else:
result = []
for i in range(len(my_list)):
copy_list = my_list.copy()
val = copy_list.pop(i)
rest = myfunc(copy_list)
for rest_item in rest:
result.append([val] + rest_item)
return result
my_list = [1, 2, 3, 4, 5]
result = myfunc(my_list)
print(result)
ポイントは、copy_listというものを使って、対象の桁に使われた数字を削除し、残りの数値を次のmyfuncの再帰呼び出しに使っているというところです。一つ一つ展開しながら読み解くと、resultに結果としてすべての組み合わせが格納されていくことが確認できます。
ちなみにこの結果、「5!」通り、つまり120通りとなります。
さいごに
再帰関数は、慣れると非常に便利で強力な力を発揮する考え方です。ただ、慣れないと読み解くのに非常に時間がかかります。
次回はこの再帰関数を使って、3手先のすべての局面を書き出し、価値判断をしながら最適な次の一手を選択する方法について考えていきたいと思います。
コメント