0Pricing
Coding Interview Prep · レッスン

Nim と Grundy 数

XOR で impartial game を解きます

「Nim と Grundy 数」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

ニムを始める

Nimには複数の石の山があります。自分の番では1つの山から好きな個数の石を取り、最後の石を取ったプレイヤーが勝ちます。🪨

魔法の量：XOR

ゲーム全体の勝敗は、すべての山のサイズのXORで決まります。その1つの数値が、どちらが勝てるかを示します。

ニム和の規則

山のサイズのXORをニム和と呼びます。ニム和が0なら手番のプレイヤーが負け、0でなければそのプレイヤーが勝ちます。

piles = [3, 4, 5]
nim_sum = 0
for p in piles:
    nim_sum ^= p

0が危険を意味する理由

0のニム和からどの手を打っても均衡が崩れ、相手に0でないニム和を渡すことになります。相手はそれを必ず元に戻せます。

勝ちにつながる手を見つける

ニム和が0でないときは、必ずそれを0に戻す手があります。その手によって、相手を負けの局面に置けます。

ニムの先へ：グランディ数

ほかの不偏ゲームでは、各状態にグランディ数を使います。これはニム和の考え方を、ほぼすべての取り合いゲームに一般化したものです。

mex演算

ある状態のグランディ値はmexです。これは、その状態から行ける手のグランディ値に含まれない、最小の非負整数を表します。

def mex(s):
    i = 0
    while i in s:
        i += 1
    return i

再帰でグランディ数を計算する

到達可能なすべての状態を再帰的に調べ、そのグランディ値を集めてから、その集合のmexを取ります。

def grundy(n):
    return mex({grundy(n - k) for k in (1, 2, 3) if k <= n})

グランディ数0は負け

1つのゲーム状態でグランディ数が0なら、ニム和が0の場合と同じく負け局面です。0でなければ勝ちです。

シュプレーグ・グランディの定理

独立したゲームを同時に行う場合は、それぞれのグランディ数をXORします。このシュプレーグ・グランディの結果により、ゲームの和をNimに変換できます。✨

適用できる条件

グランディ理論には不偏ゲームが必要です。つまり、両プレイヤーが同じ手を持ち、最後に手を打ったほうが勝つゲームです。使う前に確認してください。

確認

山が1、2、3個の石で構成されたNimを始めます。あなたは勝てるでしょうか。

まとめ

Nimの勝敗は山のXORにかかっています。0なら負け、0でなければ勝ちです。グランディ数とmexによって、この考え方を多くの不偏ゲームへ拡張できます。🏆

よくある質問

「Nim と Grundy 数」レッスンは無料ですか？

はい。「Nim と Grundy 数」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「Nim と Grundy 数」で何を学びますか？

XOR で impartial game を解きます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「Nim と Grundy 数」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ゲームの勝ち状態と負け状態
  2. Nim と Grundy 数
  3. Meet in the Middle
  4. 高速デバッグ: ストレステストと切り分け
← Coding Interview Prepに戻る