Grundyのゲームは2つ以上のヒープに拡張されました

Question

Grundyのゲームでヒープを2つのヒープに分割するにはどうすればいいですか？

ヒープを任意の数のヒープに分割するとどうなりますか（2つは同じではありません）？

Answer 1

このタイプのゲームは、本シリーズ "Winning Ways for your Mathematical Plays"で非常に詳細に分析されています。あなたが探しているものの大半は、おそらくボリューム1にあります。

また、Nimbers (Wikipedia),Sprague-Grundy theorem (Wikipedia)のリンクを参照するか、「combinatorial game theory」を検索してください。

これに関する私の知識はかなり錆びているので、私はこの特定の問題に関して自分自身を助けることはできません。あなたがすでに私がリンクしているすべてを知っていたら、私の言い訳。

編集：一般に、これらのタイプのゲームを解決する方法は、スタックサイズを「構築」することです。だから、1のスタックから始め、誰が最適なプレーで勝利するかを決めます。次に、2のスタックについて同じことを実行します。これは1 &に分割することができます。1に移動すると、1に変更することができます。& 2. 4と同じです（ここではよりトリッキーになります）：3 & 1または2 & 2、Spague-Grundy定理&を使用して、nimbersの代数ルールを使用して、誰が勝つかを計算することができます。あなたが答えを知る必要があるスタックサイズに達するまで続けてください。

編集2：コメントの中で私が話していたウェブサイトはダウンしているようです。ここにそのバックアップのリンクがあります：Wayback Machine - Introduction to Combinatorial Games。

Answer 2

グランディーのゲーム、およびそれのような多くのゲームでは、このようなアルゴリズムを用いて解決することができます。

//returns a Move object representing the current player's optimal move, or null if the player has no chance of winning 
function bestMove(GameState g){ 
    for each (move in g.possibleMoves()){ 
     nextState = g.applyMove(move) 
     if (bestMove(nextState) == null){ 
      //the next player's best move is null, so if we take this move, 
      //he has no chance of winning. This is good for us! 
      return move; 
     } 
    } 

    //none of our possible moves led to a winning strategy. 
    //We have no chance of winning. This is bad for us :-(
    return null; 
} 

GameStateの実装と移動がゲームに依存します。 Grundyのゲームでは、どちらもシンプルです。

GameStateは、ゲーム内の各ヒープのサイズを表す整数のリストを格納します。

Moveは、整数のinitialHeapSizeと、resultingHeapSizesの整数のリストを格納します。

GameState::possibleMovesは、そのヒープサイズリストを反復し、それぞれの法的分割を決定します。

GameState::applyMove(Move)は、与えられた動きがボードに適用されることを除き、GameStateのコピーを返します。

---

GameState::possibleMovesは「クラシック」グランディーのゲームのようになどに実装することができます。

function possibleMoves(GameState g){ 
    moves = [] 
    for each (heapSize in g.heapSizes){ 
     for each (resultingHeaps in possibleDivisions(heapSize)){ 
      Move m = new Move(heapSize, resultingHeaps) 
      moves.append(m) 
     } 
    } 
    return moves 
} 

function possibleDivisions(int heapSize){ 
    divisions = [] 
    for(int leftPileSize = 1; leftPileSize < heapSize; leftPileSize++){ 
     int rightPileSize = heapSize - leftPileSize 
     if (leftPileSize != rightPileSize){ 
      divisions.append([leftPileSize, rightPileSize]) 
     } 
    } 
    return divisions 
} 

が、これはルール「不平等な山の任意の数に分割」を使用して変更の実装を変更するだけですpossibleDivisions

---

私はまさにそれを計算していないが、最適化されていないbestMoveはかなりクレイジー最悪の場合の実行時間を有します。約12石の開始状態を開始すると、あなたは長い待ち時間を取るでしょう。したがって、パフォーマンスを向上させるにはmemoizationを実装する必要があります。最良の結果を得るために

、ソートされた各GameStateのヒープサイズのリストを維持し、サイズ2または1