Back to the Codeコンペティションは終了しました。さまざまなゲームのリプレイを見て、それぞれの戦略を調査するのが本当に楽しかったです。 十分な良いアイデアがありましたので、私たちと同じようにゲームを楽しんでください。
RecarとOlaf69は両方とも順位を上げられる素晴らしい戦略を開発し、彼らがそれを共有することに同意したので、あなたは彼らの秘密成分スープの秘密成分を発見することができます。
リカー
3または4で遊ぶには：
対戦相手は少なくとも4回以上、または占領されたセルで休むまで直線で移動すると想定しています。 これにより、敵が誤って充填計画を台無しにすることを防ぐために、早めに向きを変えることができます。 また、過去に送信するときは、各対戦相手の未来を考慮し、同じように進むことを期待しています。
20回の移動の後、カバーされたパスが20回目の移動で埋めたい領域の周囲に大きくなっているかどうかを確認し、1回目の移動に時間を戻します。
私たちは満たすための最良の方法を探しています：
サイズ3から3までのすべての長方形をソートし、ポイントごとに最適な長方形を選択します。 矩形領域のポイントを計算します。 四角形の中立セルの数を取得します。 中立セルの数が勝つために必要な数よりも多い場合、勝利に必要な最小数を考慮します。 なぜリスクを冒して貪欲になるのか。
長方形に敵のセルがある場合、ポイント= 0で終了します。
3未満のエリアの場合、軸のいずれかのポイント= 1 /左上のポイントまでの距離
セルが境界線のどこにあるかを見て、エリアを埋める瞬間までのステップ数が最小限になるように、円を描く必要があるセルを見つけます。
ボットが現在の長方形にペイントするように動機付けするには、新しく美しい遠くに移動するのではなく、ペイントするポイントまでの距離を掛ける必要があります。ボットがより大きな長方形を取るように動機付けするには、ステップ数に応じて定数を追加します敵。 現在のバージョンでは、この増加はプレイヤーの数に等しくなります。
ポイントは（中立セルの数/ステップの数）としてカウントされます
勝つために十分な中立セルがある場合、ポイント* 2。
2人のプレーヤーの場合：
x = 17でエッジに接する長方形のポイント* 2で、この中央の線はまだ少し塗りつぶされています-10個以上の中立セルがあります。
長方形のサイズがいずれかの軸に沿って14より大きい場合、ポイント/ 2。
3人または4人のプレーヤーの場合：
ポイント* 1.1長方形がフィールドの端に接している場合。
長方形のサイズが3人と4人のプレーヤーのいずれかの軸に沿ってそれぞれ13、12より大きい場合、ポイント/ 2。
各対戦相手が長方形の2マスよりも近い場合、ポイント/ 2。
ポイント/ 10将来の情報から、ライバルがこの長方形を要求していると報告された場合。
より安定した動作のために、最後のフレームから選択された長方形は、1.1の評価にボーナスを与えます。
推定値が1より大きい単一の長方形が見つからなかった場合、最も近い単一のセルを探しています。 同時に、敵とのニュートラルな隣人をすべて無視します。 これにより、隣接する2つのセルのh騒を回避して、同時に敵を捕まえることができます。
現在の位置から「コーナー」を移動するときにキャプチャする非矩形領域を探しています。 最大20セルまでのすべての可能なコーナーをチェックします。
その結果、「最適な」選択された領域を満たすために今すぐ行くことが最適であるポイントを取得します。
ここで、2人のプレーヤーがいる場合、彼らが自分のプレーヤーを選んだように、彼がどのエリアを埋めようとしているのかを調べます。 彼のエリアが私たちのエリアよりも優れていて、彼がそれをより早く終えるなら、私たちは彼に干渉します。 これを行うには、敵が埋めたいエリア内のポイントを探します。 彼がすでに作成した壁に接する内側の最も近い点を選択します。 そのため、彼が塗りつぶし可能な領域を単純に減らすことはより困難になります。
その後、エリアを閉鎖するか、敵に干渉するために、取得したいポイントがあります。 このポイントが現在の位置から斜めに配置されている場合、できるだけ多くの中立セルに沿って歩くことをお勧めします。 動的プログラミングを使用してこれを解決する方が良いでしょうが、水平ステップ後に中立セルがいくつアクセスでき、垂直ステップ後にいくつアクセスすることができるかを簡単にチェックする、より粗いオプションがあります。
オラフ69
ゲーム用に作成したリポジトリをGutHubにアップロードしました。 その中で、とりわけ、 コミットノートのリストを見つけることができます 。
全体として、私のAIは幅優先の検索アルゴリズムに基づいていました。 効率を達成したい場合、各ラウンドで100msの制限内で可能なすべての方向のリターンを評価する必要があることに気付きました。
すべての可能な状態のツリーは非常に大きく（5 ^プレイヤーの数^ 350ノードに近い）、状態オプションのフィールドを制限するいくつかのルールを考え出す必要がありました。 ゲームの終了までに、ツリーを展開するためのルールは次のとおりでした。
- 私の周りに少なくとも1つの中立セルがある場合、各中立セルを調べますが、忙しいセルはスキップします。
- 中立セルがない場合、他のすべてを考慮せずに、最初に計算されたパスに沿ってこのエリアを離れます
最後に、スコアを上げる方法が見つからなかった場合、最も近い中立セルに移動しました。 これは、私がライバルのやり方を評価した方法が原因である可能性があります。
進行するにつれて、各対戦相手の最も可能性の高い動きも評価する必要がありました。 理想的には、アルファベータアルゴリズムを使用する必要があります。これには、相手の可能な動きを評価し、ポイントを割り当てる必要がありますが、生成される可能性のある信じられないほどの数の状態を考えると、これは現実から非常に遠くなります（そしてすべてをわずか100ミリ秒で計算します） ） そのため、次のルールに従って決定論的な方法で敵を移動させることからなる、はるかに単純だが危険な決定に満足する必要がありました。
- その前のセルがニュートラルの場合、そのセルに移動します（移動している場所がわかっていることを意味します）
- そうでなければ、最後の動きで右に曲がった場合、次の右に中立のセルの上に立ち、次に再び左に立ちます。 逆もまた同様です。最後の動きが右だった場合。
- 近くに単一の中立セルがない場合、最も近いセルに移動します。
これらのルールは、対戦相手が積極的に行動せず、私の進行を妨げることを試みる代わりに、彼のアカウントを増やすことを好むと仮定しました。
当初、私の戦略は防衛に向けられたもので、対戦相手がアクセスできるすべてのセルに再帰的に移動することを想定していました。 これにより、私が閉じる可能性が高い領域を評価することができましたが、最終的なコードで取得できる領域よりもはるかに小さく、したがって面白くありませんでした。
実際、これらの拡張ルールでは、使用可能な時間にまだ制限があり、深さの小さいパス（10〜12近く、約60,000の分岐）しか評価できませんでした。 わずかな12個のセルでは、35x20のセルグリッドに大きな長方形を形成するには不十分でした。 現実には、らせん経路に沿って移動するようになりました。
私が大きな進歩を遂げたのは、3つのセルを順番に（ニュートラルでのみ）動かすことで、可能な方向の数をさらに制限することでした。 したがって、30セル先の方向を評価することもできます。
ツリー全体（多くの場合、ゲーム中）を表示できた場合、ステップを2セルに減らしてから1セルに減らしました。
別の大きな問題は、各方向の評価でした。 最初は、基準は単純でした：ポイントの数。 しかし、それは私にとって非常に満足のいくものではなく、このグリッドは次の理由を示しています。
00000000001111111111222222222222233333
01234567890123456789012345678901234
+ ----------------------------------- +
0 | xxxxxxxxxxxx ................ ooooooo | 0 o：私に属するセル
1 | xxxxxxxxxxxx。 oo | 1 O：私の位置
2 | xxxxxxxxxxxx。 oo o | 2 .:最良の推定方法
3 | xxxxxxxxxxxx。 oo | 3
4 | xxxxxxxxxxxx。 oo | 4問題、わずか22ラウンドでエリアを閉鎖します...
5 | xxxxxxxxxxxx..Ooooooo oo | 5
6 | xxxxxxxxxxxx oo oo | 6
7 | xxxxxxxxxxxx o oo o | 7
8 | xxxxxxxxxxxx ooo o | 8
9 | xxxxxxxxxxxx oo o | 9
10 | xxxxxxxxxxxx oo | 10
11 | xxxxxxxxxxxx oo | 11
12 | xxoo | 12
13 | xoo | 13
14 | xo ooooooooo | 14
15 | x ooo | 15
16 | x | 16
17 | x | 17
18 | x | 18
19 | Xxxxxxx | 19
+ ----------------------------------- +
00000000001111111111222222222222233333
01234567890123456789012345678901234
ポイント数という形式の唯一の基準では、ますます多くのエリアをキャプチャすることが最も興味深い動作です。 そして、最終的に、あなたの計画は敵に不満を感じます。 2つの異なる式を使用することにしました。
- 余分なポイントの数/残りのステップ数→小さなエリアを閉じることがより興味深い
- 合計ポイント/合計ステップ→エリアをわずかに最適化しますが、大きすぎるままです
最終的に、次のことに集中することにしました。追加ポイント+ 20 /残りのステップ+ 20
さらに、前進するのに役立ついくつかの改善がありました。 例：
- 充填機能へのリクエストの数をできるだけ制限します。
- 請求書の計算を最適化します。
- 最も近い中立セルの検索を最適化します。
- 効率的な検索ツリーブランチのメモリ管理。
それでも、私はすべてのアイデアを適用する時間、つまり時間を遡って時間を遡るのに十分な時間がなかったことを残念に思います！