1

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

ヒープを任意の数のヒープに分割するのはどうでしょうか (それらの 2 つが同じになることはありません)。

4

2 に答える 2

1

このタイプのゲームは、書籍シリーズ「数学的プレイで勝つ方法」で詳細に分析されています。あなたが探しているもののほとんどはおそらく第1巻にあります.

次のリンクを参照することもできます: Nimbers (Wikipedia)、Sprague-Grundy theorem (Wikipedia)または「組み合わせゲーム理論」を検索してください。

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

編集:一般に、これらのタイプのゲームを解決する方法は、スタック サイズを「構築」することです。したがって、スタック 1 から始めて、最適なプレイで誰が勝つかを決定します。次に、1 と 1 に分割できる 2 のスタックに対して同じことを行います。1 と 2 に分割できる 3 に進みます。4 の場合も同じです (ここではややこしくなります): 3 & 1 または 2 & 2. スパーグ・グランディの定理とニンバーの代数規則を使用して、誰が勝つかを計算できます。答えを知る必要があるスタックサイズに達するまで続けてください。

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

于 2012-03-21T11:22:24.493 に答える
0

Grundy's Game、およびそのような多くのゲームは、次のようなアルゴリズムで解決できます。

//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とMoveの実装は、ゲームによって異なります。Grundyのゲームでは、どちらも単純です。

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

MoveinitialHeapSize整数とresultingHeapSizes整数のリストを格納します。

GameState::possibleMovesヒープサイズリストを繰り返し処理し、それぞれの法的な区分を決定します。

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

GameState::possibleMoves次のように、「クラシック」なGrundyのゲームに実装できます。

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石の開始状態を与えると、待ち時間が長くなります。したがって、パフォーマンスを向上させるためにメモ化を実装する必要があります。

最良の結果を得るには、各GameStateのヒープサイズリストを並べ替えたままにし、サイズ2または1のヒープを破棄します。

于 2012-03-21T18:04:41.307 に答える