3

ルークは、標準の8x8チェス盤の左上隅から始まります。2人のプレーヤーが交代で、ルークを水平方向に右に、または垂直方向に下に、好きなだけ正方形に動かします。静止移動は許可されておらず、プレーヤー1が最初に移動します。勝者は、ルークを右下隅のマス目に置いたプレーヤーです。誰が勝つかを言い、勝つ戦略を説明します。

私は上記のステートメントの問題を抱えており、他の人がどのように問題に取り組むかを見たいと思っています。ルークがたどることができるさまざまなパスを計算する方法があることを私は知っています。手作業で問題を解決してみたところ、常にプレーヤー2が勝ったように見えましたが、単純すぎると思っているかもしれません。動的計画法でそれにアプローチすることは、良い方法のように思えました。とにかく、誰もがこの問題に取り組むための洞察やアルゴリズムなどを持っています！

4

4 に答える 4

9

ここに画像の説明を入力してください

H8は勝者ボックスなので、その上と左はすべて敗者ボックスです。

G7 （G8とH7）の右下はすべて敗者ボックスなので、勝者ボックスです。

G7は勝者ボックスなので、その上と左はすべて敗者ボックスです。

など…</p>

ゲームを開始したプレーヤー1は敗者ボックスに行くしか選択できないため、プレーヤー2が常に勝ちます。

プレイヤー2がしなければならないのは、自分の番になるたびにawボックスに移動することだけです。

于 2013-02-27T04:38:21.920 に答える
1

説明されているゲームは、実際には、それぞれ 7 枚のコインを 2 枚重ねるNimゲームであることに注意してください。Nim ゲームの勝者は、各山にあるコインの数を xor することで決定できます。彼らはそれを Nim-sum と呼び、Sprague-Grundy 関数の値を与えます。Nim-sum が正の場合は常にポジションが勝ちです。したがって、あなたのゲームを考えると: 7^7 = 0、これは負けポジションです。すべての斜めの位置は常に 0xであるため、負けてい ます。良いことは、このテクニックを使用すると、このゲームを 3 次元の任意の大きな空間だけでなく、4 次元、5 次元でもプレイできる (そして勝つ) ことです。等々。x^x

于 2013-02-27T12:37:25.573 に答える
1

プレイヤー 2 は、任意のサイズのチェス盤で常に勝ちます。基板の大きさで誘導による証明。

n=1 のケースは無視できるので、n=2 から始めてください。プレイヤー 2 が 2x2 ボードで勝つことは明らかです。

プレーヤー 2 は、サイズ n 以下のボードで常に勝つと仮定します。サイズ n+1 のボードで、プレイヤー 1 は左の列または一番上の行の位置に移動します。次に、プレイヤー 2 は対角線上の位置に移動します (必要な戦略はこれだけです)。これは、サイズ n 以下のボード上の開始位置です。

QED

于 2013-02-27T04:49:16.293 に答える
0

優勝ポジションには次の特性があります。

  • すべてのターミナルポジションが勝っています。この場合、ポジション（8、8）が勝ちポジションです。
  • ステップでゴールポジションに到達できるすべてのポジションが勝利ポジションです。つまり、最後の行または列のすべてのポジションが勝ちポジションです
  • 次のプレーヤーはゲームに勝つことができないので、負けたポジションに移動できる場合、私たちは勝ったポジションにいます。
  • 勝ちポジションにしか移動できない場合は、負けポジションになります

そのことを念頭に置いて、現在のポジションが勝ちポジションか負けポジションかを判断できるアルゴリズムを作成できます。以前に計算された結果を格納するためにテーブル（dpTable）を使用すると、繰り返し計算を行う必要がなくなります。

boolean isWinning(int x, int y) {
    if (dpTable[x][y] != null)
        return dpTable[x][y];

    // From the last row or the last column we can always win the game
    if (x == n || y == n)
        return true;

    for (int i = 1; x + i <= n; i++) {
        // Moving right
        if (x + i <= n && !isWinning(x+i, y) {
            dpTable[x][y] = true;
            return true;
        }

        // Moving down
        if (y + i <= n && !isWinning(x, y+i) {
            dpTable[x][y] = true;
            return true;
        }
    }

    dpTable[x][y] = false;
    return false;
}

このisWinning(x, y)関数はtrue、位置（x、y）から開始すると、最適にプレイしてゲームに勝つことができ、（x、y）falseから開始して勝つ方法がない場合に戻ります。

于 2013-02-27T12:18:48.003 に答える