25ミリ秒での海戦

まえがき

数ヶ月前、私はPythonを学ぶことにしました。 テストタスクの1つとして、ゲーム「Sea Battle」を作成する必要がありました。 それから私はこの仕事をしませんでしたが、2つのコンピューターが互いに遊ぶ「海戦」を書くというアイデアが思いつきました。 この考えは私を去りませんでした、そして私はあえて決心しました。 結果は裁判所に提出されます。 建設的な批判に感謝します。

現在の実装の一般的な概念

実際、ゲーム全体は、Playerクラスの2つのインスタンスが互いに船の座標を求め、答えに応じて移動戦略を構築するという事実に要約されます。

船を配置するための戦略は次のとおりです。2-3-4デッキベースの船は、マップの端（2セル）、中央に1デッキ（6x6の正方形）に配置されます。



人と人とのゲームのように、動きの戦略：最初にランダムに動き、ヒットした場合、周囲の4つのセルを処理し、次に再度ヒットした場合、すでにライン上にある2つのセルを処理します（2、最大船長は4セルなので、 2個がすでにヒットしている場合、最大でさらに2個のセルがあります）。

ウィキペディアの記事では、すべてが十分に詳細に説明されているので、特に誰もが議論されていることを大まかに理解しているため、ゲームのロジックについてはあまり触れません。 私はそのような違いだけがあります：各動きのためのスコアリング、0から9までのセル番号

ゲームは、ゲーム、プレーヤー、船の3つのクラスを使用します。 1つのインスタンスのみが使用されるため、現在の実装でGameクラスを使用することは冗長ですが、これは将来の基盤となります（記事の最後にある改善点のリストを参照）。

ゲームは一般的なゲームロジックを担当し、プレイヤーは移動の戦略を担当し、船は船の現在の状態とその座標を保存します。

githubのプロジェクトをリンクします。

開発で生じた主な困難

1. デザイン 。 クラスまたは関数を使用して作成しますか？ 使用するクラスのセットは？
設計の主な問題は、ゲーム内のさまざまな状態を追跡することでした。 たとえば、現在歩いている人、船の状態（ヒット、死亡）、ゲームの終了、勝った人などです。

2. ロジック/アルゴリズム 。 戦略に従って船を配置する方法、移動の座標を選択する方法は？

コードの最も興味深い部分の概要

return_shoot_state-現在の動きの結果に応じて、さらなる戦略を決定します。

def return_shoot_state(self, state, crd): """        """ if state == u'!': self.scores += 1 if not self.recomendation_pool: crd_rec = [[crd[0] - 1, crd[1]], [crd[0] + 1, crd[1]], [crd[0], crd[1] - 1], [crd[0], crd[1] + 1]] crd_rec = filter(lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec) crd_rec = filter(lambda x: x not in self.alien, crd_rec) self.succ_shoots.append(crd) self.recomendation_pool.extend(crd_rec) else: crd_s1 = self.recomendation_pool[0] crd_s2 = self.succ_shoots[0] for ind in range(2): if crd_s1[ind] != crd_s2[ind]: if crd_s1[ind] > crd_s2[ind]: crd_rec = [[crd_s1[ind]+1, crd_s1[ind]+2], [crd_s2[ind]-1, crd_s2[ind]-2]] else: crd_rec = [[crd_s1[ind]-1, crd_s1[ind]-2], [crd_s2[ind]+1, crd_s2[ind]+2]] crd_rec = filter(lambda x: 0 <= x[0] <= 9 and 0 <= x[1] <= 9, crd_rec) crd_rec = filter(lambda x: x not in self.alien, crd_rec) self.recomendation_pool.extend(crd_rec) elif state == u'!': self.scores += 1 self.recomendation_pool = [] self.succ_shoots = [] 

重要な変数：recomendation_pool-将来のショットの座標のリスト、succ_shoots-最後に成功したショット。

船に当たった場合、まず、成功したショット（スコア+ = 1）のためにポイントを獲得する必要があり、次に、次に何をすべきかを理解する必要があります。 recomendation_poolに何かがあるかどうかを確認し、ない場合は、近くの4つの座標を書き留めます（フィールドの境界線と既に撮影した座標のリストに従ってフィルタリングした後）。



recomendation_poolが空でない場合は、2回目にヒットしたことを意味し、周囲の4つの座標ではなく、各エッジから約2つの座標について話します。



船が現在のショットで沈没した場合、タスクが完了したと見なし、推奨事項のプールなどをクリーンアップします。 次のショットはランダムに実行されます。

service.gen_cord-船舶のタイプごとに可能なすべての座標を生成します。 関数の結果は、次の構造を持つ辞書になります：{"S0"：[[[x0、y0]、[x1、y2]、[xN0、yN1]]、[[x3、y3]、[x4、y4]、[xN2] 、yN3]]、...]、 "S1"：...}、Sは船の種類、[[x0、y0]、[x1、y2]、[xN0、yN1]]は船の座標のセットです。

 def gen_cord(): """    """ all_comb = [[x/10, x % 10] for x in range(100)] for_1_ship = filter(lambda x: x[0] in range(2, 8) and x[1] in range(2, 8), all_comb) for_other_ship = filter(lambda x: x not in for_1_ship, all_comb) cord_comb = {1: [[x] for x in for_1_ship], 2: [], 3: [], 4: []} for ship in filter(lambda x: x != 1, cord_comb.keys()): for cord in for_other_ship: hor_direction = [cord] + [[cord[0]+x, cord[1]] for x in range(1, ship)] ver_direction = [cord] + [[cord[0], cord[1]+x] for x in range(1, ship)] for dir_d in [hor_direction, ver_direction]: for cord_d in dir_d: if cord_d not in for_other_ship: break else: cord_comb[ship].append(dir_d) return cord_comb 

重要な変数：all_comb-フィールドの座標を[[x0、y0]、[x1、y1]、...]の形式で保存します。 for_1_ship-シングルデッキと同じ6x6の正方形、for_other_ship-他のすべての船の座標セット。 cord_comb-座標のすべての組み合わせを格納する辞書。

船の手配

Playerクラスのインスタンスの初期化時に、船も配置されます。 クラスでは、create_shipsメソッドがこれを担当し、次のことが行われます。

1.擬似ランダムな方法（random.choice）で利用可能な座標の組み合わせの組み合わせ（組み合わせ）から各船（船）に対して、座標のセットが選択されます。
2.次に、一連の座標に対してハロー（service.set_halo）が生成されます。 ハローは、後で船を置くことができない座標のセットです（規則：船を近くに置かないでください）。



3.次に、船とハローの座標で構成されるリストから組み合わせのリスト（data_cleaner）をクリアします。

ロギングモジュール

開発の最後に、標準ライブラリからロギングモジュールを発見しました。 出力フィールドはカスタマイズ可能（logging.basicConfig）であり、出力の操作は印刷の場合よりも難しくありません。

その他

sevice.rdn_usr_name-0から999までの文字と数字のセットからランダムなプレーヤー名を生成します。

対戦相手がPlayer.ships_defeat = 10を持っている場合、つまりゲームが終了します。 10隻すべてを沈めた。 船が「殺された！」と答えると、カウンターが更新されます。

改善リスト（TO DO）

1.プレイヤー間でトーナメントを行います。たとえば、1000人のプレイヤーが参加します。 理論的には、現在のリードタイムを考慮して、トーナメント全体で約30秒かかります。

2.移動の「基本アルゴリズム」を追加します。たとえば、クロスツークロス、つまり すべてのセルを斜めにパンチしてからさらに押します。 これらのアルゴリズムのいくつかを実装してから、プレーヤーにランダムに作業を割り当てます。 次に、効率を比較します（たとえば、ランダムな動きや「クロストゥクロス」アルゴリズムにより多くの結果をもたらすものは何ですか？）

3.検索エンジンの組み合わせ（service.gen_cord）を最適化します。 明らかに、冗長であり、多くのリソースを消費します。

4.さまざまな船配置戦略を実施し、最も成功した戦略を比較します。

PS興味深いアイデアに感謝します。

ありがとう

更新（2015年1月16日）

トーナメントが実装され、統計の小さなコレクションが作成されました。結果は次のとおりです。

トーナメントには降格​​ゲームがあります。 トレイルで負けた場合。 あなたは一歩を踏み出せません。

トーナメントに妨害がないようにするには、プレーヤーの数は、除算の残りを常に2で除算するように、トーナメントのプレーヤーの数が1（つまり勝者）になる前でなければなりません。 これらの数値には、1024（512、256、128、64、32、16、8、4、2）が含まれます。

以前、トーナメントは約30秒続くと想定していました。 時間はプレーヤーの数に応じて直線的に増加しますが、1024人のプレーヤーのトーナメント全体がわずか17秒だったときの驚きは何でしたか。 なぜ17秒かわからないことがわかったので、おそらくいくつかの最適化メカニズムが機能し始めています。 私の計算は次のとおりです：1022ゲームはトーナメント全体に続きます* 25 ms 1ゲーム= 25.55秒。

トーナメント統計は、次の値内に保持されます。

1.移動の平均数（すべてのプレイヤー）：85.06、
2.勝者の平均移動数：85.95、
3.負け選手の平均移動回数：84.17、
4.敗者が採点した平均ポイント数：17.75

結論は次のように描くことができます。

1.勝者と敗者がほぼ同じ動きをする回数。

2.ポイント数はほぼ18です（勝つには20が必要です）。

ボトムライン：両方のプレイヤーがほぼ同じで非効率にプレイします:) 2ポイントの差は、最後の動きで文字通り勝利が相手のクラッチから抜け出すことを示しています。

結論：以来 各プレイヤーは同じ戦略に導かれ、ゲームに特別な多様性はありません。 もっと面白くするには、船の手配と移動の両方のためのさまざまな戦略を実装する必要があります。これは近い将来、暇なときに行います。

アップデートをお楽しみに。

更新2（2015年1月16日）
船の沈没後の壊れた座標のリストへのハローの追加を実装しました（原則として、すべてが公平です）。 移動数の統計が大幅に改善されました。
1.移動の平均回数（すべてのプレイヤー）：58.91
2.勝者の平均移動数：60.98、
3.負け選手の平均移動回数：56.83、
4.敗者が獲得した平均ポイント数：15.37

アイデアをくれたMeklonに感謝します。

更新3（2015年1月17日）

船を配置するための新しい戦略を実装しました（シングルデッキには60個のセルがあります）。 結果は次のとおりです。各プレイヤーが同じ戦略を使用している場合、敗者と勝者の間に違いはありませんが、各プレイヤーにランダムに割り当てられた割り当て戦略がある場合、私の戦略（中心部に6x6の正方形）がある戦士が多いことは明らかです、つまり 私の戦略が捨てられた場合、誰もがほぼ同じ方法でプレイします。 これも面白くない。 今、私はさまざまな動きの戦略を実装します（おそらく最適なものがあります）。



更新4（2015年1月20日）

移動するためのさまざまなオプションを追加：ランダム-自由なセルからランダム、クロス-クロスからクロス、リニア-1行から4行に直線的に（賞賛記事のように）。 重要なポイント：船を配置するための戦略はトーナメント全体で発行されますが、移動の戦略はゲームごとに発行されます。

統計情報を収集しました（忘れないでください、降格では1024人のプレイヤーが対戦します）。


主な調査結果：
シングルデッキ船random_12（12個のランダムなセルが選択され、そこに船が配置されます）およびfor_1_ship_36（中央の6x6フィールド）を配置する戦略は、明らかに最も効果的ではありません。

均一な分布は、等しい間で等しいことはほぼ同じ結果を与え、そのうちの1つの勝利はランダムな結果にすぎないことを示します。

追加の移動戦略の実装による移動の数は減少していませんが、トーナメント時間は25秒から50秒に増加しています。
1.平均移動回数（全プレイヤー）：61.43、
2.プレイヤーが獲得したムーブの平均数：63.23、
3.負け選手の平均移動数：59.63、
4.敗者が獲得した平均ポイント数：15.93

誰かがGitHubで私のコードを見て、それを改善する方法についての提案をしてくれたら感謝します。

意図された最適化タスクが1つ残っていますが、ご存じのとおり、最適化は無期限に実行できるため、特別な必要なしに記事は近い将来更新されません。

ご清聴ありがとうございました。Pythonの力があなたと共に来ますように！