「魂のために」プログラミング

いっぱい、鳩、罪を犯さないで！

あなたのペニーを奪います。

私はお金のためではありません。

私は魂のためです。



レオニード・フィラトフ「 射手座フェドトの物語、大胆な若者 」



楽しみのためだけに。



ライナス・トーバルズ



人々が多くの方法で楽しむのは秘密ではありません。 テレビを見るのが好きな人もいれば、クアドロコプターを集める人もいます。 レシピを共有したい。 すべての人に役立つとは考えられませんが、誰かが興味を持つかもしれません。 私はプログラムを書くのが好きです（そして、これはプロのプログラマーの間でも珍しいことではないと思います）が、このプロセスが退屈なルーチンに変わるときはあまり好きではありません。



おもしろいことに、プログラミングは一種の「心の負担」でなければなりません。 このような（有用な）エンターテインメントの良い例は、SQLクエリをコンパイルするスキルの向上に専念する有名なリソースです。 しかし、生きている一人のSQLプログラマーではありません！ 最近、 フォートの所有権を向上させる素晴らしい方法を見つけました。 Axiomを使用すると、Fortで十分にプログラムできます！



公理を楽しくするための私のレシピは簡単です：

1. ZoGコミュニティによってまだ実装されていないものの中から、より完全なルールを持つゲームを選択します
2. Axiomを使用して、それを実現しようとしています。
3. 私たちはこれから生じる問題を解決する過程で楽しみます
4. 結果のアプリケーションを再生することが面白い場合、生成されたFunは自動的に2倍になります！

この計画の最初の段落の実装により、インターネットは通常助けになります。 今回は、非人間的な実験の対象としてSplutを選択しました。 。 IG Game Centerに関する彼の説明を以下に示します。 ルールを改めて説明することなく、このゲームの魅力を説明します。

• 3人以上のプレイヤーがプレイします（ある程度、AIアルゴリズムの課題です）
• プレーヤーのターンには、いくつかの（1から3）ピースの連続した動きが含まれます
• 勝利に至るまでの動きは単純ではありません（ピースを取り、食べるだけではなく、1つの目標に合わせて一連の動きを実行する必要があります）
• このゲームのルールは非常に思慮深く、非常に独創的です。

魔法を明らかにする

Funの開発を始めましょう。 簡単なことから始めましょう-トロールの動きから。 図の通常の移動は、問題を引き起こしません。 その実装は明白であり、Axiomの概念を説明するのに適しています。





すぐにアドバイスしたいので、コメントに注意してください（括弧内）。 スタックで何が起こっているのか混乱しないようにするのに役立ちます（これはFortで本当に重要です）。 スペースにも注意を払う価値があります。 設定されていないスペースが間違った場所にあると、多くの時間を費やすことになります。



コード自体によると、すべてが明確だと思います。 EXECUTEコマンドを使用して、（スタックから取得した）方向に遷移を実行し、その後、遷移のブール結果を確認します（ TRUEでない場合、移動の計算を完了します）。 次に、ターゲットセルが空であることを確認してから、Figureを移動します。 移動を実行する移動コマンドは、スタックから2つの値を取得します。移動の開始点（ from ）と移動後の位置（ ここ ）です。 add-moveコマンドは、移動の形成を完了します。



石の動きを伴うもう少し複雑な動き：





ここで、スタックに2つの方向、つまり移動の方向と反対の方向を同時に配置します。 スタックを操作するため、コード自体はより複雑に見えますが、慣れることができます。 メインフィギュアを移動した後、フィギュアをキャプチャまたは作成するためのすべての「サイド」アクションを実行する必要があることが非常に重要です。 また、各コマンドの後にスタックに何が何の順序で配置されているかを覚えておくことも重要です。 コマンド自体の詳細な説明は、常にAxiomマニュアルに記載されています。



ただし、ある時点では、特に停止する価値があります。 is-stone述部は、現在のセルの形状がStoneであることを検証しますか？ 。 もちろん、これは組み込みのAxiom関数ではなく、私たちのものです。 その実装は次のようになります。





前回の記事で 、オブジェクトの名前（この場合は図形）を定義するまで使用できないと不満を言ったことを覚えていますか？ DEFERを使用すると、この問題に対処できます 。 唯一の悪い部分は、この重要なパターンがAxiomのドキュメントに記載されていないことです。



しかし、なぜ4種類の石があるのでしょうか？ できませんか？ 悲しいかな、Splutのルール！ 石の「個性」なしではできないような方法で編集されています。 なぜこれが必要なのかを後で示します。



これでトロールは移動し、（オプションで）その後ろにストーンをドラッグできますが、何か忘れていたようです。 実際のところ、Splutでシェイプを自然に減らす唯一の方法です！ トロルは彼らに石を投げるという事実のために！ コードをまとめて、不足している機能を追加します。





ヘルパー関数については説明しません。 ここでそれらの実装を見ることができます 。 私はスローにのみ専念します。 トロルは、 テイクストーンムーブ（この関数の実装は簡単です）でストーンを取ることができます。その後、 partial-move-typeコマンドは、指定されたタイプ（ continue-type ）でムーブの継続を有効にします。 このタイプでは、登録されている移動の唯一のタイプは、ボードへのストーンのドロップです 。



とにかく投げることはできませんが、厳密に定義された場所に投げてください！ ルールによれば、石はトロールからまっすぐ（垂直または水平に）飛び、ドワーフの頭上を障害物（魔道士、ボードの端または別のトロール）に向かって飛んでいきます。 メイジはすぐにノックし、他の場合にはボードに落ちます。 ドワーフがこの場所で終わった場合、彼は単に運が悪かった。 これは実装するのが難しいルールであり、もう一方の端から開始する方が便利です。 障害物に隣接するフィールドを探し、空のセルまたはドワーフが占有しているセルに沿って、反対方向に移動します。 道路に沿ってトロールに出会った場合、移動を開始した場所に石を投げることができます。



さらに、関連するルールがコードに実装されています。 たとえば、メイジが殺されると、彼のチーム全体がフィールドから削除されるという事実と、石が投げられた後、その動きはすぐに別のプレイヤーに渡るという事実です。 これについては詳しく説明しません。



わずかに異なる種類のパズルは、特別なGnomeの動きです。 ノームは、独自の力で、その前にある任意の数のフィギュア（ストーンを含む）を一列に動かすことができます。 これらすべての形状を保存するには、明らかにスタックが必要です。 他のすべてのために、変数を使用できます：





はい、これを理解することは前のコードよりも困難ですが、アクションの本質は簡単です。 私たちは一方向に移動し、スタック上のピースを空のセルにスタックしてから、ボード上でそれらを作成し、1ステップ移動します（同じセルに複数のピースを置くことはできないため、ピースを削除することを心配する必要はありません-ZoGはそれらを削除します独立して）。 このコードがどのように機能するかを理解してみてください;それは良い「心の体操」です。



もちろん、メイジが私たちに最大の問題を引き起こさなければ、メイジはメイジではありません。 メイジは石を浮遊させることができます。 任意、ただし...特定の条件下で。 たとえば、前の移動で（何らかの形で）移動した石を浮上させることはできません。 これはすぐに疑問を提起します：前の動きとして何を考慮するべきですか？ 残念ながら、ルールはこの瞬間を解読しません。 私のコードでは、動きを最初のプレーヤーに渡す直前に、動く石の兆候のクリーニングを実装しました（ここでは、個性が必要です。各石には独自のフラグがあります）。 もちろん、これは彼に深刻な利点をもたらします（彼はどの石も動かすことができ、後続のプレイヤーは彼が動かなかったものだけを動かすことができます）が、このルールの他の可能な実装も完璧ではありません。





ここでは、必要なものをすべて実装していることを考えると、間違いを犯しやすいです。 しかし、すべての可能性が実現しているわけではありません！ ストーンの隣に空のセルがある場合、メイジはストーンが占有しているセルに移動できますか？ ゲームのルールには「はい」とありますが、コードはそうではないと考えています。 実際、メイジは彼の前でストーンを「プッシュ」することもできます。 これは一種の浮揚です！





このコードは、フィールド全体でStonesを検索する必要がないため、より簡単です。 石で占められたフィールドに立ちたい場合、浮揚できる石はこれだけです。

AとBはパイプの上に座っていた

上記で述べたように、3人以上のプレーヤーが関与するゲームのAIの実装には、いくつかの困難が伴います。 ゲームを終了するための条件を決定するとき、問題はすでに始まります。 たとえば、私が最近実施したゲームYonin Shogi （4人用の日本のチェスのバリアント）では、敗北条件を次のように定義するのは魅力的です。

 (loss-condition (South North West East) (checkmated King))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このエントリは、プレイヤーのいずれかの王にマットの前にゲームをプレイする必要があることを意味します。 残念ながら、このアプローチは機能しません！ 私はすでに、 checkmatedコマンドが持つ「魔法」が多すぎると書きました。 特に、王は常にシャーを離れなければならない（そしてシャーの下に決して立ち入らない）と彼女は決定します。 全体として、2人のプレイヤーがゲームに参加している限り、機能します。 ビデオは問題を示しています：







ご覧のとおり、 チェックメイトは4人のプレイヤーのうち1人だけで問題なく動作します。 他のプレイヤーの場合、チェックに対する防御は必須の動きとは見なされません！ もちろん、次の動き、そのような王は食べられるかもしれませんが、この事実は状況を悪化させるだけです。 好むと好まざるとにかかわらず、このようなゲームでは通常のマットを使用することはできません。



Splut！ 状況はさらに悪化しています。 ボードにチームが1つだけ残るまで、ゲームをプレイする必要があります。 ただし、ZoGではゲーム中に移動の順序を変更することはできません！ これは、出て行く各チームは、それに関しては動きをしなければならないことを意味します（もちろん、動きをする他の方法がないので、それはフォールドします）。 Splutでも！ 各チームは連続して複数の動きをします（ゲームの開始時に1〜2回、ゲームの途中に3回）。 一般的に、通常のAI Axiomがこのゲームに対処できなかったのは驚きではありませんでした。



それは確かに機能し、プログラムは動きます（私の意見ではかなり愚かです）が、プレイヤーの1人が排除された後、問題が始まります。 逃した各動きを計算するとき、プログラムは、指定された時間枠のいずれにも該当せずに、ますます「考え」始めます。 評価関数（ OnEvaluate ）を再定義しても、状況は修正されません。 一般に、Axiomにはこのような機会があるので、これを独自のAIアルゴリズムを実装しようとする正当な理由と考えました（先を見て、うまくいかなかったと言いますが、試してみる価値がありました）。



基礎として、私は、多くの人によく知られている次のアルゴリズムをYevgeny Kornilovの本「Programming Chess and Other Logic Games」から取りました。





簡単にわかるように、元の形式では、このアルゴリズムは完全に不適切です。 3人以上のプレイヤーがいますが、交互の動きははるかに複雑です。 しかし、このアルゴリズムは、独自のバージョンを開発するための良い出発点です。



少し考えてみると、最悪のシナリオでは、移動をカウントするプレイヤーに反対する3人のプレイヤーが力を合わせることが理解できます。 言い換えれば、私たちにとってこれは敵対的なプレイヤーです（彼らが団結しなければ、彼らにとってはさらに悪いことです）。 もう1つの重要な点は、評価関数の計算です。 移動を計算するとき、評価関数は常に同じプレイヤー（移動が計算されるプレイヤー）の「視点から」計算される必要があります。 敵対的なプレイヤーの場合、スコアは反対の記号で取られるべきです（私たちが良いほど、彼らは悪いと感じます）。 これらの考慮事項を考慮して、アルゴリズムを次のように書き換えることができます。





動きと位置の生成に関連するフォートと公理には多くの「魔法」がありますが、緊張があるため、元のアルゴリズムはかなり目に見えます。 スタックをアンロードするには、再帰呼び出しで使用される変数でいくつかのスタックをエミュレートする必要がありました。 スタック自体には、計算プロセス中に、 alphaとbetaの 2つの値しかありません。 再帰呼び出し（ RECURSE ）では、それらは常に同じ順序で送信されますが、計算が敵対的なプレイヤーに対して実行される場合、符号を変更した後、これらの値を変更します。 また、敵プレイヤーによって位置を評価するときに得られる評価のマークを変更します。



この関数は、前回の記事で既におなじみのカスタムエンジンの実装から呼び出されます。





このコードでは、評価値に1〜5の乱数を追加していますが、これは、推定される動きがわずかに異なる場合にプログラムが常に同じにならないようにするためです。



いつものように、主な困難は評価関数を構築することにあります。 現在のバージョン（ GitHubのコードを常に表示できることを希望する人）をリストして記事をダウンロードすることはありません。現在、次の点を考慮に入れていると言えます。

• 敵のメイジの数（主な目標はこの値を減らすことです）
• 味方メイジの数（この値が1から0に変わると、ゲームは終了します）
• 敵のドワーフの数（相手の手を結ぶのはいつでもいいことです）
• 友好的なドワーフの数（それなしではできなかったのではなく、とにかく自分の数字）
• ストーンと並んで友好的なメイジを見つけることに対するペナルティ（これは本当に危険です）
• Stonesと同じラインで敵のメイジを見つけるためのボーナス（同じ理由で）
• TrollsからStonesまでの合計ステップ数（私たちは自分自身で減らし、他の人で増やすことを試みます）

これは確かに理想的なオプションではありません。 重量値はより最適に選択する必要があります。たとえば、魔術師が石と同じ線上にいるという事実自体は、それ自体では何の意味もありません。 キャストラインは、たとえばトロールによってブロックされる可能性があり、投げられるためには石にも到達する必要があります。 なんらかの方法でコードを記述し、どのように機能するかを確認できます。







予想どおり、AIはインテリジェンスで輝きを放ちません（そして、非常にゆっくりと動作します）が、少なくとも「スマートにパス」しようとします。 少なくともこれはすでに再生できます。

カウント-泣いた

もちろん、AIの品質を評価するために、何度も使用して「エキスパート評価」を構築できますが、これは私たちの方法ではありません。 Axiomには、このプロセスを自動化できる素晴らしいAutoPlayユーティリティが付属しています。 残念ながら、彼女は2人以上のプレーヤー向けに設計されたゲームの操作方法を知りませんが、これは問題ではありません。 特に彼女のために、2人のプレイヤーで構成を作成します（4つの石を残します）。





また、プレイヤーがランダムな動きをする構成が必要です。





結果は、驚くべきことではありませんでした（100ゲームを計算するのに一晩かかりましたが）：

 Final results: Player 1 "Random", wins = 13. Player 2 "Duel", wins = 87. Draws = 0 100 game(s) played
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

なぜプログラムがこれほど長く機能するのですか？ コースを計算するときに、評価関数が呼び出される回数を確認しましょう（深さ5の動きの計算データ）：







はい、評価関数の8000回の呼び出しは確かにたくさんありますが、なぜここに3つの行があるのですか？ 説明しようと思います。 Eval呼び出しの数をカウントする方法は次のとおりです。





出力では、次のシーケンスが取得されます。





数字の各グループ（空の行で区切られている）には、現在の位置からのすべてのプレーヤーの動きを表示した結果が含まれています。 上記のグラフでは、最初の行はグループ内の最小値、2番目は平均、3番目は最大値を示しています。 最大値と最小値の差は、アルファ-ベータクリッピングの効果によって決まります。平均値-特定の検索深度で期待できるパフォーマンスを決定します。



グループの数が主に減少していることに気付くかもしれませんが、単調な減少に違反する「バースト」が時々あります。その数を計算してみましょう：







多すぎる！一部のグループでは、16を超える単調減少の違反があります。動きをより最適な順序で表示することができた場合、パフォーマンスインジケーターを改善することは確かに可能です（そして、より深い検索を実現することは可能です）。残念ながら、次の2つの点により、これを行うことができません。

1. 私は、ゲームSplutでの動きの「品質」の予備評価を行うことができるヒューリスティックを持ちません。
2. , Axiom ( )

検索の深さを増やす別の方法は、「強制」移動の「詳細な」検索です。また、繰り返される位置を切り取るといいでしょう（Zobristハッシュはこれに大いに役立ちます）



検索深度の増加に伴って表示される位置の数がどのように変化するかを見てみましょう：







すべての対戦相手の動きの完了までの平均待機時間（深度5の動き）は約1分であるため、これがアルゴリズムの現在の実装で期待できる最大の探索深度であることは明らかです（それを増やすと、プログラムでのゲームが完全に不快になります）。



しかし、Splutゲームの5つの動きについて考えてみましょう。？これは、すべてのプレイヤーの可能な動きを計算するのにも十分ではありません！デュエルモードでも。チェスのゲームを1ターン先に数えるようなものです！そのようなプログラムから特別な知性を期待することは困難です。



もちろん、Splut！チェスよりもピースがはるかに少ないですが、動きはより複雑です！勝つためには、プログラムは長期計画を立てることができなければならず、多くの前進があります。Axiomを使用してこれを達成する方法はわかりませんが、おそらく何らかの形で可能です。

私はそれに取り組んでいます。