簡単なゲーム木探索
もはや裏技とか関係なく、単なるPythonネタのお蔵出し（私が大昔にやった趣味のBASICプログラミングの焼き直し）になってしまいますが、簡単なゲームを作ってみることにします。
ゲームといっても、PCで完全読み切りをやっても数秒で終わるくらいの軽いものです。
とりあえずルール。
- プレイヤーは2人
- PC対人であれば、人が先手か後手かを選択できる。
- 紙に数字(1桁)を書いたマスを5つ書く。ゴールの数を決める。合計は最初0。
- 先手は5つのマスのどこかにコマを置き、合計にそのマスの数を加算。
- 後手は先手が置いたのとは別のマスにコマを動かし、合計にそのマスの数を加算。
- 必ず別のマスに動かし、同じマスを指定することはできない。
- 先手も同様に別のマスにコマを動かし、合計にそのマスの数を加算
- これを繰り返して最終的に合計がゴールの数に一致した方が勝ち、ゴールの数を超えてしまったら負け
このルールで、常に必勝手を打つプログラムを作ってみます。
このゲームはシンプルなので、自分の手が必勝かどうかを返す winning(今の合計, 次に打つ手) は
- 合計がゴール数を超えたらFalse
- 相手の番のwinning(...)を調べて、1つでもTrue (相手の勝ち) があったらFalse (自分の負け)
- それ以外はTrue
というように、実は再帰的な定義が可能です。
また将棋のように複雑なゲームだと、駒得や利き筋などから割り出して評価点をつけて min/max でカットするといった感じですが、このゲームは終了条件がはっきりしているので
# any(必勝手かどうか(x) for x in 次に打つことが可能な手のリスト)
みたいにしてお手軽に枝カットができます。
ただそれでも同じ枝を何度もたどると時間がかかるので、「関数の戻り値をキャッシュする」を使って同じ枝をたどらないようにしています。
target = 37
cells = [1, 2, 3, 4, 5]
def winning(t, n, cache={}):
key = (t, n)
return cache.get(key) or cache.setdefault(key, _winning(t, n))
def _winning(t, n):
if t + n > target:
return False
elif any(winning(t+n, x) for x in cells if x != n):
return False
else:
return True
マスの数が[1,2,3,4,5]、ゴールが37である場合、先手は1手目をどこにおけばいいでしょうか？
>>> [winning(0, x) for x in cells] [False, False, False, True, False]
つまり先手は「4」に置けば必勝ということが分かります。
