Chompのゲームのアルゴリズム

Question

私はChomp of Chompのプログラムを書いています。ゲームの説明を読むことができます ウィキペディア, しかし、とにかく簡単に説明します。

寸法NXMのチョコレートバーで演奏します。つまり、バーはNXMの正方形に分割されています。それぞれのターンで、現在のプレーヤーは正方形を選択し、選択した広場のすべてのものをすべて食べます。したがって、たとえば、以下は有効な最初の動きです。

目的は、相手に最後のチョコレートを食べさせることです（毒されます）。

AI部分に関して、深度削減を伴うMinimaxアルゴリズムを使用しました。ただし、適切な位置評価機能を思い付くことができません。その結果、私の評価機能により、人間のプレーヤーが私のプログラムに勝つことは非常に簡単です。

誰でもできます：

• 適切な位置評価機能を提案するか
• いくつかの有用な参照を提供するか
• 代替アルゴリズムを提案しますか？

Answer 1

あなたのボードはどれくらいの大きさですか？

ボードがかなり小さい場合は、動的プログラミングでゲームを正確に解決できます。 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))

関数は勝ちます（ボード）は、ボードが勝利ポジションであるかどうかを計算します。ボード表現は、ピース（x、y）がまだボード上にあるかどうかを示すタプル（x、y）のセットです。関数の動きは、1つの動きで到達可能なボードのリストを計算します。

Wins機能の背後にあるロジックは、このように機能します。私たちの移動時にボードが空いている場合、他のプレイヤーは最後の作品を食べたに違いないので、勝ちました。ボードが空でない場合、ある場合は勝つことができます any 動き、結果として生じる位置が負けの位置になるようにすることができます（つまり、つまり、つまり、 not wins(move)）、その後、他のプレーヤーを負けた位置に導いたからです。

また、結果をキャッシュするメモヘルパー関数も必要です。

def memoize(f):
    cache = dict()
    def memof(x):
        try: return cache[x]
        except:
            cache[x] = f(x)
            return cache[x]
    return memof

キャッシュすることにより、このポジションが複数の方法で到達可能であっても、特定のポジションの勝者のみを計算するだけです。たとえば、最初のプレイヤーが最初の動きで残りのすべての列を食べると、チョコレートの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倍までスピードアップすることもできます。

これはMinimaxからの派生です

Minimaxから始めます：

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

ゲームが終了したため、ヒューリスティックは、どのプレーヤーが勝ったかに応じて-1または1のいずれかを返します。 -1をfalseとして、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)])

代わりに、Alpha-Beta PruningでMinimaxで始めていた場合：

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になるとすぐに、ループが破損します。したがって、Alphaは-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

したがって、これは、常に子供のリスト全体を計算するのではなく、真の値を見つけたらすぐに反復を停止するジェネレーターを使用することと同等であることがわかります。

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倍になります。最初のフォームがより速くなるからではなく、本当の値を見つけたらすぐに、再帰呼び出しを含むループの残り全体をスキップできるからです。

それで、あなたがそれを持っている、Wins機能は変装したアルファベット検索でした。勝利に使用した次のトリックは、それをメモ化することです。ゲームプログラミングでは、これは「転置テーブル」を使用して呼び出されます。したがって、Wins機能は、転置テーブルを使用してAlphabeta検索を行うことです。もちろん、この派生を通過するのではなく、このアルゴリズムを直接書き留めることは簡単です;）

Answer 2

チェスのようなゲームとは異なり、勝ち負けに欠けている「進歩」はないので、ここでは良いポジション評価機能は可能ではないと思います。ウィキペディアの記事は、最新のコンピューターにとって徹底的なソリューションが実用的であることを示唆しており、適切なメモと最適化を考えると、これが当てはまると思います。

あなたが興味を持っているかもしれない関連するゲームはそうです nim.