ダガズ：先を見る

1秒間に113回、それは伸び、さらに引っ張ります。 確認が来た場合、シグナル-それは停止する可能性があり、停止しません。 それは手を伸ばし、これまでにない新しい方法を見つけます。 即興で勉強します。 何をしているのかわかりません...



ジェームズ・コリー「シボレの火」



一般的に、強力なAIゲームは私の優先事項ではありません。 特殊なゲームエンジンと競争するのは愚かで、普遍的であり、コンピューティングリソースとしてブラウザに組み込まれたシングルスレッドJavaScriptのみを持っています。 さらに、複雑なAIの必要性がまったく生じないゲームがいくつかあります。 ここでは、たとえば、AI全体が最短経路を見つけることになり、 このゲームではタスクはタスクに完全に対応します。 残念ながら、そのようなゲームはルールよりも例外である可能性が高いです。 多くの場合、単純にばかげているとは思えない動きをプログラムが行うために一生懸命働く必要があります。



私のプロジェクトの目標は、ボードゲームを普及させることです。 あまり知られていない、または忘れられたボードゲームを探して、それらを復活させようとしています。 さまざまなゲーム：2人以上のプレイヤーのための、古代、現代、複雑で非常に子供向け。 1人のプレーヤーでも（パズルもゲームです）。 基準は1つだけです- ゲームは面白いはずです！ 少なくとも私には。



プロジェクト開発の現在の段階では、サーバー部分は、JavaScriptコードを伴うHTMLページのセットよりも少なくとも何らかの形で複雑になることを意図していません。 インターネットにアクセスせずに、ローカルを含む最新のWebブラウザでゲームをロードして動作させたい。 あらゆる種類の競争、格付け、そして人間同士の相互作用に関連するすべて-これはすべて私のプロジェクトに関するものではありません。 おそらくそうなるでしょうが、近い将来にはほとんどありません。



そして、ここでボットとその制御アルゴリズムの開発が前面に出ています。 つまり、ゲームのルールを最も完全に制御できるインタラクティブなボードは確かに優れていますが、ゲームに完全に不慣れな人に興味を持たせるには、彼と遊ぶ必要があります。 そして、人々同士のゲームはまだ提供されていないため、ボットに対処する必要があります。

基本的な本能

私が言ったように、マシンが本能ほど多くの知性を必要としないゲームがあります。 そして、これはゲームが悪いという意味ではありません！ 原則として、そのようなゲームは非対称です。 パーティーの1つから創造的なアプローチが必要です（人がこれを行います）。反対側のゲームはより日常的です。 このようなゲームの良い例がここにあります。



その側に完全なチェス「軍隊」があるので、チェス騎士と女王の動きを組み合わせて、マハラジャだけを捕まえる（食べる）必要があります。 これは非常に強力な作品ですが、ホワイトが正しくプレーすれば、結果は当然の結論です。 一方、黒のために遊ぶことは非常に簡単です。 ボットの実装はランダムと大差ありません。 彼は次のことを行います。

1. 利用可能なすべての動きの中で、勝利に直接つながる動きを探します（この場合、これは相手の王の攻略です）
2. そのような動きがない場合、彼は相手の駒を奪う動きを求め、報復攻撃の代わりにマハラジャを使いません
3. 適切な動きがない場合-安全な動きをします
4. 安全な動きがない場合、バトンを別のボットに渡します（通常はランダム）

奇妙なことに、このような単純な戦略は多くのゲームに適しています。 いずれにせよ、最初の近似に。 これはかなりエキゾチックなテイクルールを持つビデオゲームです。 駒が3枚以上の対戦相手で脅かされた場合（チェスクイーンの規則に従って）、駒はすぐにボードから削除されます。





別の例を示します。 「 三銃士 」では、捕獲は敵の1人だけによって行われますが、各ターンに行われます。 他のプレイヤーのタスクは、「銃士」を同じ垂直または水平になるように送ることです。 目標が達成されず、どちらの側も次の動きができない場合、「銃士」が勝ちます：





「銃士」のために遊んでいると、ランダムな家でうまくいくことができますが、別の安全な動きを用意して、コンピュータが誤って並んでしまうのは残念です。 ボットはより慎重にプレイする必要があります。 コードは可能な限り単純です。





もちろん、ボットはより複雑なアルゴリズムを使用してこれらのゲームをより良くプレイするとは言いませんが、最も単純なソリューションには独自のアプリケーションがあります（たとえば、 ランダムプレーヤーは必要なゲームでサイコロを振ることができます）。 さらに、単純なアルゴリズムには1つの重要な利点があります。 彼らは非常に高速に動作します。

一人用ゲーム

パズルの場合、ゲームAIは、あなたの手を「満たす」方法ほど必要ではありません。 最終的には、その人が自分で解決すると想定されています！ 一方、コンピューターがあなたの場所でパズルを解こうとする様子を際限なく見ることができます。





単純な検索アルゴリズム（このクラスのパズルにこれほど効果的なものはまだ発明されていません）。 位置が繰り返されないようにするには、 Zobrist Hashを使用します。 このビデオでは、単一の正方形が互いに長すぎてワルツしていることがわかります。 これは、ボットがそれらを異なる形状と見なしているためです。 これは簡単に修正できます。 現在、ソリューションははるかに高速です。





個人的に非常にいらいらしたもう1つのポイントは、ボットが「まっすぐに」わずか数ステップという大事な目標に到達する前に、「横に」ステップを取り、さらに30分ダイスを動かして、ソリューションからさらに遠くに移動できることでした。 この問題を解決するために、移動をアニメーション化するために割り当てられた時間を使用しました。 人間にはほとんど見えない100ミリ秒の間、何百もの位置を並べ替えることができます。





時間があれば、いろいろな動きをするだけです。 目標が見つかったら、まっすぐに行きます！ このボットの動作は非常に明白ですが、問題を解決する最良の方法を使用していません。 解決策が見つかった後、最初にアニメーションを実行するためにより多くの時間を費やす方が賢明でしょう。 これはまさに、ソリティアソリティアゲームを解決するためのボットを開発するときにやったことです。





ライプニッツの例に従って、この問題を反対方向に解決します。つまり、ボードの中央に1つのチップを立て、逆の動きを実行して、元のピースを作成しようとします。 この角度から、タスクは、通常の戻り検索に要約されます 。 ログの一部を次に示します。





6組の位置に達した後、検索を中断することに気付くかもしれません（求められているソリティアは、そのような数の数字で構成されていました）。 もちろん、これが唯一の最適化ではありません。 上記の単純なアプローチでは、位置を繰り返すことができます。 いつものように、位置の繰り返しに関しては、Zobrist Hashが助けになります（実際、それはもっと早く役立ちます：位置を比較する前に、要素ごとにハッシュを比較する方がはるかに効率的です）。





パズルでたくさん練習したので、さらに複雑な問題に進むことができます。

伸びる

チェスやチェッカーなどのそれほど深刻ではないゲームの場合、上記で説明したすべてよりも複雑なAIが必要になることは明らかです。 概して、選択は小さい：Minimax、その「 アルファ-ベータクリッピング 」および「 モンテカルロ 」法（およびこれら両方のHabrに関する素晴らしい記事があります）。 これらのアプローチはそれぞれ普遍的です。 それぞれに長所と短所があります。 完全なレビューであると主張することなく、頭に浮かぶ最初のものをリストします。

1. ミニマックス手法を使用するには、位置を評価する関数を定義する必要があります（経験のあるボードゲームの開発者として、一部のゲームではこれが非常に難しい場合があります）。
2. アルファベータクリッピングは、深さ検索または結合検索を実行する場合に特に効果的です（幅、一定の保証された深さ、たとえば2〜3移動まで、その後、深さはNレベル以下）。 これにより、コンピューティングリソースが限られている状況では不適切になり、最も重要なこととして、必要に応じて指定された時間までに回答を出力します（間違えた場合は知識のある人に訂正してもらいます）。
3. アルファ-ベータクリッピングの有効性は、動きの予備的なランキングをその品質別に適用することで大幅に改善できます（以下で説明するように、モンテカルロ法を使用する場合、このようなヒューリスティックも役立ちます）。
4. ミニマックス法を使用する場合、深さ検出を任意の場所で停止することはできません。 チェッカーやチェスで駒を取るなどの強制的な動きが発見された場合、より「穏やかな」位置が生じるまで検索を継続する必要があります。
5. モンテカルロ法を使用する場合、シミュレーションはターミナルの位置（プレイヤーの1人の勝利または引き分けの認識）に対して実行されます。 パーティー時間が長いゲームでは、これが問題になる可能性があります。

これらすべての考慮事項を考慮して、ミニマックス法を完全に考慮せずに、現在の反復では、 モンテカルロ法に焦点を当てることを決定しました（もちろん、それに適したタスクを選択します）。 アルゴリズムをテストするゲームの1つとして、私は韓国の子供向けゲームである「 4階河野」を選択しました。



これは、キャプチャを使用したシンプルなゲームで、その目的は敵からすべてのピースまたは移動の可能性を奪うことです。 河野での捕獲はかなり独特です。 対戦相手の駒を拾うには、その駒の1つを別の駒にジャンプさせて「着陸」する必要があります（これにより、ボードは初期位置で駒で完全に満たされているにもかかわらず、ゲームを開始できます）。 移動の1つを計算するときのデバッグ出力を次に示します（制限時間〜3秒）：





私たちの目の前にそのような結論があると、アルゴリズムの正確さを評価できます。 最初に注意する必要があるのは、アルゴリズムによって記録された「目標」が、ゲームのルールに従ってプレーヤーの目標に対応しているかどうかです。 デバッグの過程で、アルゴリズムが単に「not that」を検索しようとする状況がいくつかありました。 すべてが目標を満たしていれば、動きの評価を確認します（Winは記録された勝利の数、Allはプレイされたゲームの合計数です）。 UCTの「箱から出して」は、原則として機能しますが、悪くはありませんが、いくつかの変更を行いました。

1. 限定された検索深度（デフォルトでは100）
2. 移動のヒューリスティックを追加

つまり、キャプチャは「サイレント」ムーブよりも10倍望ましいです。 ここで、ミニマックス法とは異なり、モンテカルロでのソートの動き（ヒューリスティックによる）は役に立たないことに注意してください。 動きを選択する確率がその発見的推定に比例するような方法でアルゴリズムを構築する必要があります。 両方のイノベーションは、河野のために行われた勝利/ゲームの統計に好影響を与え、私は他のゲームを取り上げました。





このゲームにはテイクはありません。 勝つためには、フィールド全体にピースを引き、ボードからそれらを削除する必要があります（これは動きと見なされます）。 （直交線に沿って）前方、左右にのみ移動できます。 敵の駒は動きに垂直に動き、通過を防ぎます。 敵のピースをロックすることは不可能です！ 明らかな気取らない点については、ゲームはかなり深いです。 お使いのコンピューターで再生してみてください 。





デバッグに関しては、ゲームは大きなボード上のアルゴリズムの動作に関する情報を提供しました。 移動の勝利数の推定値はすべて、即座にゼロにリセットされます。 アルゴリズムには、単一の勝利を見つける時間がありませんでした。その結果、彼は出会った最初の動きを始めました（最高ではありません）。 検索の深さを増やすことはあまり助けにはなりませんでした-シミュレーション段階でプレイされるゲームの「クリティカル」な質量を設定するには、3秒では明らかに十分ではありませんでした。 移動を選択するときは、ヒューリスティックを考慮する必要がありました。





ヒューリスティックな動きはUCTが提供するものよりも確かに悪いですが、それほど複雑ではないゲームでは、UCTが機能する瞬間までコンピューターが「生き残る」ことができます。 重みは、モンテカルロアルゴリズムが機能しない場合にのみヒューリスティックが顕著な効果を持つように選択されます。



次のゲームは上佐渡でした。 前に彼女についてすでに書いた。 これは、モンテカルロ法がここで非常にうまく機能するということではありません。 プログラムは非常に適切な動きをしますが、目標を設定しても、それを打ち負かすことはまったく難しくありません。





主な理由は、このゲームの単純で適切なヒューリスティックを思い付くことができなかったからです。 その結果、プログラムはその動きを「タッチ」します。 十分なコンピューティングリソースがあれば、これは問題になりません（念のため、このゲームにはモンテカルロアルゴリズムが適しています）が、1つのスレッドで3秒の動きを計算することは、私が余裕がある最大値です（ところで、UCTは非常に良い場合があります複数のスレッドがある場合にスケーリングします）。



もちろん、私に現在実装されている形式のモンテカルロ法は、すべてのゲームに適しているわけではありません。 私は彼に夢中になるつもりはありません。 チェスのようなゲームでは、おそらくミニマックスの方が優れています。 私はまだこの問題を探求する機会があります。 また、UCTの現在の実装の改善についても考えています。 何が良くなるか見てみましょう。