0Pricing
Coding Interview Prep · レッスン

ゲームの勝ち状態と負け状態

最適なプレイで誰が勝つかを考えます

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

2人の完全な対局

組合せゲームでは、2人のプレイヤーが交互に手を進め、どちらも最善を尽くし、手を打てなくなったほうが負けます。あなたの仕事は勝者を予測することだけです。🎯

すべての局面にラベルがある

ゲームの各局面を状態と呼びます。あなたの仕事は、手番のプレイヤーにとって各状態が勝ちか負けかを判定することです。

勝ち状態の意味

手番のプレイヤーが、相手を負け状態に導く手を少なくとも1つ持つなら、その状態は勝ち状態です。

負け状態の意味

どの手を選んでも相手を勝ち状態にしてしまうとき、その状態は負け状態です。何をしても行き詰まってしまいます。

基底の場合

まったく手を打てない局面が基底ケースです。その局面に直面したプレイヤーはすでに負けているため、負け状態とします。

最下層から積み上げる

基底ケースから始めて、外側へ向かって処理します。新しい状態のラベルは、その手によって到達する状態だけで決まります。

良い手は1つで十分

勝つために必要なのは、相手の負け状態へ進む1つの手だけです。逃げ道を1つでも見つければ十分です。

小さな例

山から石を1個または2個取り、最後に取った人が勝つゲームを考えます。石が0個のときは手番のプレイヤーが負けるため、負け状態です。

勝敗判定をコードにする

この再帰では、すべての手を試し、その結果に対して再帰呼び出しを行うことで状態を判定します。⚙️

def win(n):
    if n == 0:
        return False
    return any(not win(n - k) for k in (1, 2))

メモ化で高速化する

分岐が異なっても同じ状態が現れるため、各結果をキャッシュします。単純なメモによって、指数時間の処理を線形時間にできます。

from functools import lru_cache
@lru_cache(None)
def win(n):
    return n != 0 and any(not win(n - k) for k in (1, 2))

対称性を近道にする

局面が完全に対称なら、後手は相手の手をまねることで勝てる場合があります。このミラー戦略に注目してください。

確認

ある状態に直面しています。あなたにとって負け状態になるのはどのようなときでしょうか。

まとめ

これで状態を判定できるようになりました。勝ちは相手の負けへ進む手が1つあり、負けはその手が1つもありません。基底ケースから構築し、メモ化してください。🧠

よくある質問

「ゲームの勝ち状態と負け状態」レッスンは無料ですか？

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

「ゲームの勝ち状態と負け状態」で何を学びますか？

最適なプレイで誰が勝つかを考えます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「ゲームの勝ち状態と負け状態」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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