ダガズ：常識へのキック（パート9）

...そして、古いものとしてすべてが繰り返されます：

夜、運河の氷の波紋、

薬局、通り、ランタン。



アレクサンダーブロック





今日、私は伝統的にほとんどのボードゲーム開発者に無視されていた問題について話したいです。 チェッカーやチェスなどのゲームのコンピューター実装が、プレーヤーの勝ち（または負け）の状況を正しく処理する（これも難しい ）場合、結果は非常に満足できるものと見なされます。 しかし、ゲームが行き詰まっている場合はどうでしょうか？ プレイヤーは勝利の希望なしにピースを移動します（そして無期限に続行できます）。



人がコンピューターで遊ぶ場合、これは問題ではありません（誰が最初に疲れるのかは明らかです）が、2つのボットが演奏されるとどうなりますか？ たとえば、さまざまなAIオプションの「強度」を比較するには、自動モードで多数のゲームを実行する必要があります。 このような状況で「誰も」を正しく処理することは不可欠です。 そして、ゲームのルールに厳密に従って実行することが非常に望ましい。

2.合格の繰り返し

「チェッカー」ファミリーのゲームで使用される最も簡単なアプローチ。 所定の移動回数内にプレーヤーが勝てなかった場合、ゲームは中断されます。 したがって、おなじみのロシアの草案では、ゲームは30の動きで勝てない場合、引き分けと見なされます。 「動きの遅い女性」の詳細に関連するより複雑な規則は、「 英語草案 」で使用されています。 各対戦相手のクイーンが1人残っている場合、ドローとして認識される前に、20を超える動きは許可されません。 1人の対戦相手が3人のクイーンと他の2人のクイーンを持っている場合、後者はゲームを40手以内でプレイすることを要求する権利があります。 「 国際草案 」の規則は、考えられるすべての状況をより詳細に説明しています 。

• 25ムーブのコース内にいるプレイヤーが、単純なチェッカーを動かさず、キャプチャを行わずに、クイーンのみがムーブした場合、引き分けが宣言されます。
• ゲームの最後にプレイヤーが3人の女性、3人の女性と1人のシンプル、1人の女性と2人のシンプル、3人のシンプルなチェッカー、2人の女性、1人の女性と1人の女性、または1人の女性または1人のシンプルに対する1人の女性がいる場合、プレイヤーは5 -thが勝つために移動します。
• ボードにクイーン2人に対してクイーン5人（またはクイーン4人とシンプルなチェッカー1人）が残っている場合、最強のサイドが50の手で勝たなければなりません。そうでなければ、ドローが宣言されます。
• 同じ位置が3回（またはチェッカーの同じ位置）で繰り返される場合（さらに、チェッカーの同じ位置）、さらに毎回同じ側の後ろでムーブのターン-引き分けも宣言されます。

これらのルールの最後のバリエーションは、他のゲームでよく使用されます。 チェスでは、位置の3回の繰り返し（一連の動きを考慮に入れる）が同点を認識する理由の1つです。 一部のゲーム（ Goなど ）では、ポジションの繰り返しが禁止されています。 私はすでにこのゲームの「コ」問題について書いています。 議論されていることを簡単に思い出してください。







位置の繰り返しが許可されている場合、プレイヤーはこの動きのシーケンスを無限に続けることができます（敵からますます多くの石を奪います）。 これは、黒がD17に移動した後、白がC17をプレイすることを禁止することによって戦うことができますが、位置の繰り返しはより難しい場合があります。 ゲームでは、「トリプルコ」の状況と「エターナルライフ」のさらに複雑なポジションが可能です。







Ingaのルールはこの問題を規制しようとしますが、満足のいく結果を得るのは困難です。 「戦闘」会社と「嫌がらせ」会社を区別するには、高い資格が必要です。 初心者プレイヤーがこれを処理する可能性は低いです。 ルールの単純化されたバージョンでは 、位置の繰り返しが禁止されています。 このアプローチは「 superco 」と呼ばれ、2つの異なる方法でポジションの繰り返しを決定できます。

• スーパーポジション-一連の動きを考慮せずに、ポジションの繰り返しを無条件に禁止します
• 状況的スーパーコ-位置の繰り返しの禁止、同じプレーヤーのターンのターンを条件とする

一般に、さまざまなポジションを比較する機能は、一部のボードゲームの実装に役立ちます（そしてAIに不可欠です）が、多くを比較する必要があることを考慮すると、ポジションの単純な要素ごとの比較は高すぎる可能性があります。 この問題を解決するために、有名なコンピューターゲーム開発者のアルバートリンジーゾブリストは 、彼にちなんで名付けられたシンプルでエレガントな方法を開発しました。



Zobristハッシングはほとんどのボードゲームに適用可能であり、その本質は単純です。 まず、各数字の可能な位置ごとに、乱数の表がコンパイルされます（ランダムであるほど良い）。 チェスの場合、64個のボードフィールドのそれぞれに対して、12個のランダムな値が必要になります（色を考慮して、ピースのタイプごとに1個）。 次に、ボード上のピースの対応する配置のためにテーブルから取得した「 モジュロ2 」数を追加することにより、ハッシュがコンパイルされます。 もちろん、2つの位置のハッシュ値が同じである場合、これは位置が同じであることを意味しません。 衝突の確率は常に残りますが、この方法を使用すると、要素ごとの位置の比較の数が最小限に抑えられます。



このハッシュが加算的であることが重要です。 ハッシュを「ゼロから」作成して、毎回ポジション全体を表示する必要はありません。 ハッシュのみを使用して、ボード全体でピースを「移動」できます。 これを行うには、ハッシュから図の古い位置に対応する値を削除し、新しい値を追加します（両方ともxor操作によって実行されます）。 Zobristハッシュは非常に便利な手法であり、ボードゲームのほとんどのコンピューター実装で使用されます。



もちろん、 ZoGでも（確かにAxiomで）使用されますが、内部のニーズのみに使用されます。 exe-nicknameで「釘付け」の位置を3回繰り返したときにゲームを停止する条件！ Axiomでは、動作を無効にする（ドローではなく敗北でゲームを終了する）か、3番目ではなく最初の位置の繰り返しを検出できますが、ZoGのエンジンとして動作しているため、このチェックをまったくキャンセルできません。 個人的には、そのような不変の「デフォルトの動作」 は多くの神経を台無しにしました 。





ZoGで位置リピートチェックを設定する可能性がないため、このプログラムで最も深刻な設計エラーの1つと考えています。 「checkmated」および「maximal captures」とともに、このオプションは「決してする必要はない」というテーマで、ブロンズの記念碑であることに敬意を表して当然です。 ZRFを使用すると、3つの位置が検出された場合にのみ動作を再定義できますが、それ以上は再定義できません。 デフォルトでは、次の定義が適用されます。

 (draw-condition (White Black) repetition)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このチェックを何らかの方法で設定できないという単なる事実（たとえば、3番目の行ではなく、最初の位置の繰り返しを検出する）は、すでに非常に悪いですが、干渉するだけではこのチェックをオフにできないという事実は、ひどいです！ 私のプロジェクトでは、次の定義のようなものを使用します（そして、引き続き使用することを望みます）。

 (not-situation-repeated? 1 1)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これはおなじみのコです。 最初の引数は、位置のどのアカウントの繰り返しを検出するかを決定し、2番目の引数は検索の深さを決定します。 そしてこれは、ゲームを終了するという観点だけでなく（ZRFのように）、移動ジェネレーターによって使用される不変式でも使用できる普遍的な表現である必要があります（Goでは位置を繰り返すと移動が禁止され、ゲームが中断されないため）。 もちろん、 * -position-repeated predicateを使用することも可能です。 、状況に応じて位置Co.を決定します。



おそらく、上記のすべてのために、この記事を開始する価値はありませんが、Zobristハッシュは別の予期しないアプリケーションを見つけました。 CheckersとTic-Tac-Toeを接続する伝説的なゲームが1つあります。 アフリカの「 ボロトウ 」と同じように、敵の石を取り除くために石から「3列」のラインを構築する必要がありますが 、このゲームには2つを禁止するオプションがあります。連続して回。







ビデオの実装では、このようなチェックは実行されず、これは偶然ではないことに気付くのは簡単です！ ZRFで実装するのが難しい要件を思い付くのは困難です。 このチェックは、位置の繰り返しを制御する必要がありますが、全体ではなく、その一部のみを制御する必要があります。 3つの石がライン（「ミル」）を構成している場合、同じ場所でそれらが繰り返される場所を1ターンで禁止するか、キャプチャに至らないようにする必要があります。 しかし、ハッシュは部分的にしか作成できません！





ここでは、選択した方向に沿って移動し、友好的な石がそれらにある場合、ハッシュに3つの位置を順番に追加します。 その後、そのようなハッシュが2回戻って形成されたかどうかを確認します。 すべての石のハッシュキーは一意であることが理解されます。たとえば、石をボードに追加するときに設定された属性値に基づいて生成されます。





敵の石を取り除くと、すべてがそれほど単純でもありません。 まず、ゲームのほとんどのバージョンでは、敵の「製粉所」の1つを構成する石を削除することはできません（いくつかの種類では、他の選択肢がない場合、そのような石は削除できます）。 さらに、私たちが自分で複数の「ミル」を同時に構築できた場合、適切な数の敵の石を受け取る権利があります（このルールもしばしば無視されます）。





ご覧のように、ボードゲームの古代の開発者は、実装に飽きないように一生懸命働いてきました。 DagazプロジェクトでのZobristハッシュの使用についてお伝えしたかったのは、おそらくこれだけです。 私の話があなたにとって興味深いものになったことを願っています。