コンピューターでプレイするための最適な戦略を見つけようとすると、すぐにこの近似に到達します。
すでにいくつかの細胞の状態を知っていて、勝利に近づく動きをしたいとします。 この場合、利用可能な情報と矛盾しない、可能な限り多くの船の場所で敵の船によって占有されているセルを選択することは理にかなっています
実際に。 可能な構成が1つしかない場合は、1ターンでゲームを終了し、彼の船を順番に撃ちます（構成がわかっているためです！）構成がさらにある場合は、可能な限りその数を減らして、利用可能な情報量を増やします。 船に乗り込めば、何も失うことはありません（結局、動きはそのままです！）そして、逃した場合、残りの組み合わせの数は、この動きの後に最小限になります。
これは最適な戦略への近似にすぎないことは明らかです。 敵が私たちの計画を知っている場合、彼は船がゲームの開始時に射撃するセルに落ちないように配置しようとします。 確かに、これは彼を少し助けます-私たちはまだ彼を隅に固定することになります-しかし、いくらかの柔軟性が私たちを傷つけない可能性があります。 さらに、よく考え抜かれた一連の動き（最初の動きは最適ではありません）がより良い結果をもたらす可能性があります。 ただし、現時点では、すでに困難なタスクを複雑にすることはせず、すべての構成を計算して、フィールドを満たす確率のマップを作成します。
一見、タスクは耐えられないようです。 構成の数は10 20のオーダーであるようで（実際、それらの数はわずかに少なく、10 15に近い）、徹底的な検索に時間がかかりすぎます。 フィールドの色を整理して許容できるものだけを残すのは良くありません。とにかく、それぞれの組み合わせを調べる必要があります。
他に何を試してみる？ オリンピアードはすぐに答えます-動的プログラミング。 しかし、それを整理する方法は？
上から下に行きます。 どのような情報が必要ですか？
それで、上から下に行きます。 フィールドが2つの部分に分割されているとします-部分Aは最初のk行で構成され、部分Bは残りすべてで構成されています。 フィールドの一部を塗りつぶすのは、セルを2色で着色したものです。 黒いセルがルールを満たす船のセットを形成する場合（船は真っ直ぐで、触れないでください、長さは望ましいセットを形成します）、フィールド全体を埋めることは正しいと呼ばれます。 パーツAの2つの充填S1とS2は、パーツBの充填Tに対して、フィールドS1 | TおよびS2 | T全体の充填が同時に正しいか正しくない場合、同等と呼ばれます。
問題を解決するには、それで十分です。
- パートAのすべてのパディング同等クラスを説明する
- 各クラスについて、異なる塗りつぶしの数を計算し、エリアAの各セルについて、黒だった塗りつぶしの数を示します（この情報をこのクラスのマップと呼びます）
- エリアAに新しい行を追加するときのクラスとそのマップの変換を説明します。
エリアAの未知の充填SとエリアBの既知の充填Tがあるとします。Sについて何を知る必要がありますか？
まず、最後の行の完全な状態を保持しておくと便利です。 この場合にのみ、領域Bの最初の行のどのセルをまだ占有でき、どのセルを占有しないかを決定できます。
第二に、エリアAに既に何隻の完成船が存在するかを知る必要があります。 終了すると、エリアBに拡張できなくなった船を意味します。この場合、最後の行にセルを持たない船、または完全にその中にある（そして2つ以上のセルを占有する）船のいずれかです。
第三に、まだエリアBに拡張できる各船について、現在の長さを知る必要があります。 これらの船自体は最後の行で簡単に認識できます。白い船に囲まれた黒いセルを1つ占有します。
それだけです。 等価クラスはこのデータによって完全に決定され、それらの組み合わせのすべてでさえ有効ではありません。 それがどれだけ判明したかを計算しましょう：
- 最後の行：10ビットで、すべてのオプションが可能というわけではありません。連続して4ユニットを超えることはできず、4ユニットの2つのグループ（0111101111）はありません。 合計909のオプション。
- すでに露出した船。 0〜4の1デッキ、0〜3の2デッキ、0〜2の3デッキ、0または1の4デッキ。 120のオプションのみ。
- ラインの分離された各ビット-Aに該当する垂直船のセルの数：1から4。このような船は5個まで、合計で1024個までのオプションです。
したがって、各クラスは27ビットで記述され、その合計数は1億2000万を超えません。 実際、この見積もりは非常に誇張されており、プログラムは1053,612クラスを見つけることができました。
新しい行を追加する
充填Sがあるとします。これについては、上記の情報のみがわかっています。 さらに1行追加します。取得可能なすべての塗りつぶしをリストし、それらのクラスを定義し、新しいクラスごとに密度マップを作成します。
まず、塗りつぶしに追加できる行を見てみましょう。 主な基準はすべての人に知られています。新しいラインの黒セルは、最後のラインSの黒セルに斜めに隣接することはできません。さらに、すでに知っているように、新しいラインには長すぎる船はありません。 それでも、垂直船の1つの長さが4である場合、彼は新しいラインに進むこともできません。 残りの制限は船のセットに関連しており、後で確認する方が便利です。
追加できるすべての行を繰り返します。 連続して複数のユニットがある場合、それらは水平船を形成します-完成した船のカウンターですぐに考慮します。 孤立したユニットには3つの状況があります。
- 最後の行Sには孤立したユニットがありましたが、この場所の新しい行にはありません。 そのため、船は完成し、その長さがカウンターに追加されます。
- 新しい行には孤立したユニットがありますが、Sの最後の行にはこの場所には何もありませんでした。 そのため、新しい垂直船が登場し、その長さは1になりました。
- 孤立したユニットはSの最後の行にあり、新しい行にあります。 これは、垂直船が継続し、その長さが1増えることを意味します。
次に、長さのセットが有効かどうかを確認します。 s1、s2、s3、s4をそれぞれ長さ1,2,3,4の完成した船の数とし、n1、n2、n3、n4を対応する長さの未完成の船の数とします。 キットが条件と矛盾しないようにするために、以下が必要です。
s1<=4 && s2<=3 && s3<=2 && s4+n4<=1 && (s3+s4+n3+n4)<=3 && (s2+s3+s4+n2+n3+n4)<=6 && (s1+s2+s3+s4+n1+n2+n3+n4)<=10
新しいクラスの情報の準備ができました。 マップを作成するには、古いマップの最初の行をコピーし、次の行に追加されたビット線に組み合わせの数を掛けて入力します。 異なる構成から取得した同じクラスのカードを合計します。
終了
最初の空の構成に10行を追加した後、それぞれ独自のマップを持つ1053612クラスのリストを取得しました。 フィールドのすべての構成のマップを取得するには、これらすべてのクラスを調べて、未完成の船を「仕上げ」、各サイズの結果の船の数を計算し、それが正しい場合は、クラスマップを合計に追加する必要があります。
空の10x10フィールドの場合、18555545978831780構成が判明し、フィルマップは次のようになります（すべての数値は10 9で除算されます）。
438487 418064 475795 466986 459000 459000 466986 475795 418064 438487 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 459000 287065 361127 334756 338709 338709 334756 361127 287065 459000 466986 287231 357367 330652 334756 334756 330652 357367 287231 466986 475795 311381 378334 357367 361127 361127 357367 378334 311381 475795 418064 273993 311381 287231 287065 287065 287231 311381 273993 418064 438487 418064 475795 466986 459000 459000 466986 475795 418064 438487
対称的であるという事実は、プログラムに重大なエラーがないことを間接的に確認します:)最も人口の多いセルはC1、最も満たされていないセルはB2です。
C1への移行後、カードは次の形式を取ります。
334039 316782 362205 354834 348680 348723 354859 362278 316825 334105 316847 204441 234170 214857 214919 214952 214721 234125 204338 316830 362174 234066 286949 270246 273421 273609 270199 287338 234109 362286 354993 215372 270082 249099 252049 252445 248433 270251 214694 354875 347443 215675 272189 252807 255040 256554 252272 273744 214941 348764 344351 216423 272030 253365 252114 255722 251441 273431 214746 348625 351029 226597 265572 262005 251178 255339 249502 271093 215027 354867 347356 238783 245635 276238 258889 268837 266947 286297 234182 362174 342552 273993 227511 287231 237138 226857 216325 233431 204620 316794 292453 231475 0 269650 316361 349490 359545 360275 316193 333632
一定のミスを伴う「ベストムーブ」のシーケンスは次のようになります（図を参照）。
C1、J8、A8、H1、A4、J4、D10、G10、E1、D2、B3、A2、C9、B10、H9、I10、I7、J6、I5、H6、J2、I3、H4、G5、G2 F3、E4、B7、A6、B5、C6、C3、D4、D5、F6。
プログラムが戦艦を捕まえるのに急いでいないことがわかります。 24番目の移動までに、「対角」アルゴリズムが保証されたヒットの前に最後の移動を離れた場合、残りの船の位置の数は約240 * 10 9であり、「対角」アルゴリズムの場合は260 * 10 9です。 違いはわずかです。 それがどれほど重要かを知るために、これらのアルゴリズムの間でトーナメントを手配する必要があります。
シーバトルウィーク
海戦 GORKOFF をプレイするための最適なアルゴリズム
「海戦」におけるゲームのアルゴリズム：敵の 非人称 砲撃
古い出版物：
ゲーム「海戦」の理論と実践- 正直に生まれた2フライ
人工知能海戦- 正直ミチュリン