Chomp というゲームのプログラムを書いています。ウィキペディアでゲームの説明を読むことができますが、とにかく簡単に説明します。
次元 nxm のチョコレート バーでプレイします。つまり、バーは nxm の正方形に分割されます。各ターンで、現在のプレーヤーは正方形を選択し、選択した正方形の下と右のすべてを食べます。したがって、たとえば、次は有効な最初の動きです。
目的は、対戦相手にチョコレートの最後の部分を強制的に食べさせることです (毒が入っています)。
AI 部分に関しては、深さ切り捨てを伴うミニマックス アルゴリズムを使用しました。しかし、適切な位置評価関数が思いつきません。その結果、私の評価関数では、人間のプレイヤーが私のプログラムに勝つのは非常に簡単です。
誰でもできます：
ボードの大きさは？
ボードがかなり小さい場合は、動的計画法を使用してゲームを正確に解くことができます。Python の場合:
n,m = 6,6
init = frozenset((x,y) for x in range(n) for y in range(m))
def moves(board):
return [frozenset([(x,y) for (x,y) in board if x < px or y < py]) for (px,py) in board]
@memoize
def wins(board):
if not board: return True
return any(not wins(move) for move in moves(board))
関数 wins(board) は、ボードが勝ちポジションかどうかを計算します。ボードの表現は、ピース (x,y) がまだボード上にあるかどうかを示すタプル (x,y) のセットです。関数 move は、1 回の移動で到達可能なボードのリストを計算します。
wins 関数の背後にあるロジックは次のように機能します。私たちの移動中にボードが空の場合、他のプレイヤーは最後のピースを食べたに違いないので、私たちは勝ちました. ボードが空でない場合、結果のポジションが負けポジションになるような動きがあれば勝つことanyができます (つまり、勝てませんnot wins(move))。
結果をキャッシュする memoize ヘルパー関数も必要です。
def memoize(f):
cache = dict()
def memof(x):
try: return cache[x]
except:
cache[x] = f(x)
return cache[x]
return memof
キャッシングにより、特定の位置に複数の方法で到達できる場合でも、特定の位置の勝者は 1 回だけ計算されます。たとえば、チョコレートの 1 列の位置は、最初のプレーヤーが最初の移動で残りの列をすべて食べた場合に取得できますが、他の多くの一連の移動によって取得することもできます。1 列のボードで誰が勝つかを何度も計算するのは無駄なので、結果をキャッシュします。これにより、漸近的なパフォーマンスが から にO((n*m)^(n+m))改善さO((n+m)!/(n!m!))れます。大きなボードではまだ遅いですが、大幅な改善です。
また、便宜上、デバッグ印刷機能を次に示します。
def show(board):
for x in range(n):
print '|' + ''.join('x ' if (x,y) in board else ' ' for y in range(m))
このコードはまだかなり遅いです。これは、コードがまったく最適化されていないためです (これは Python です...)。C または Java で効率的に記述すれば、おそらく 100 倍以上のパフォーマンスを向上させることができます。10x10 のボードを簡単に処理できるはずで、最大で 15x15 のボードを処理できる可能性があります。また、ビット ボードなど、別のボード表現を使用する必要があります。複数のプロセッサを使用すれば、おそらく 1000 倍高速化することもできます。
ミニマックスから始めましょう:
def minimax(board, depth):
if depth > maxdepth: return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -minimax(move, depth-1))
return alpha
深度チェックを削除して、完全な検索を行うことができます。
def minimax(board):
if game_ended(board): return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -minimax(move))
return alpha
ゲームが終了したため、どちらのプレイヤーが勝ったかに応じて、heuristic は -1 または 1 を返します。-1 を偽、1 を真と表すと、max(a,b)となりa or b、 と-aなりnot aます。
def minimax(board):
if game_ended(board): return heuristic(board)
else:
alpha = False
for move in moves(board):
alpha = alpha or not minimax(move)
return alpha
これは次と同等であることがわかります。
def minimax(board):
if not board: return True
return any([not minimax(move) for move in moves(board)])
代わりに、アルファ ベータ プルーニングを使用してミニマックスから始めた場合:
def alphabeta(board, alpha, beta):
if game_ended(board): return heuristic(board)
else:
for move in moves(board):
alpha = max(alpha, -alphabeta(move, -beta, -alpha))
if alpha >= beta: break
return alpha
// start the search:
alphabeta(initial_board, -1, 1)
検索は、alpha = -1 および beta = 1 で開始されます。alpha が 1 になるとすぐに、ループが中断されます。したがって、再帰呼び出しでは、アルファが -1 のまま、ベータが 1 のままであると想定できます。したがって、コードは次と同等です。
def alphabeta(board, alpha, beta):
if game_ended(board): return heuristic(board)
else:
for move in moves(board):
alpha = max(alpha, -alphabeta(move, -1, 1))
if alpha == 1: break
return alpha
// start the search:
alphabeta(initial_board, -1, 1)
したがって、パラメーターは常に同じ値として渡されるため、単純にパラメーターを削除できます。
def alphabeta(board):
if game_ended(board): return heuristic(board)
else:
alpha = -1
for move in moves(board):
alpha = max(alpha, -alphabeta(move))
if alpha == 1: break
return alpha
// start the search:
alphabeta(initial_board)
-1 と 1 からブール値への切り替えを再度行うことができます。
def alphabeta(board):
if game_ended(board): return heuristic(board)
else:
alpha = False
for move in moves(board):
alpha = alpha or not alphabeta(move))
if alpha: break
return alpha
したがって、これは、常に子のリスト全体を計算するのではなく、True 値が見つかったらすぐに反復を停止するジェネレーターで any を使用することと同等であることがわかります。
def alphabeta(board):
if not board: return True
return any(not alphabeta(move) for move in moves(board))
ここではany(not alphabeta(move) for move in moves(board))の代わりに があることに注意してくださいany([not minimax(move) for move in moves(board)])。これにより、妥当なサイズのボードの検索が約 10 倍高速化されます。最初の形式の方が速いからではなく、True の値を見つけたらすぐに、再帰呼び出しを含む残りのループ全体をスキップできるからです。
これで、wins 関数は変装したアルファベット検索にすぎませんでした。勝つために使用した次のトリックは、それをメモすることです。ゲームプログラミングでは、これは「転置テーブル」を使用して呼び出されます。そのため、関数 wins は、転置テーブルを使用してアルファベット検索を行っています。もちろん、この導出を行うよりも、このアルゴリズムを直接書き留める方が簡単です ;)
チェスのようなゲームとは異なり、勝ち負け以外に「進行」がないため、ここでは適切な位置評価関数は使用できないと思います。ウィキペディアの記事は、最新のコンピューターでは徹底的な解決策が実用的であることを示唆しています。
興味のある関連ゲームはNimです。