このリンクを参照してください: http://en.wikipedia.org/wiki/Hex_(board_game)
Hex ゲームを作成していますが、特定のゲームが終了したことを確認する方法がわかりません。
では、与えられたゲームが終了したことを確認する優れたアルゴリズムは何でしょうか?
ここでのエンディングとは、ちょうど一人の人が線を完全につなぐことを意味します。
質問: 与えられた 2 人のプレーヤーの駒の位置から、「ゲームを終了させる完全なラインがあるかどうか」を判断するための適切なアルゴリズムは何ですか?
「ユニオン検索」構造とも呼ばれる等価クラスのデータ構造が必要です: http://en.wikipedia.org/wiki/Disjoint-set_data_structure
各石が配置されると、新しい等価クラスが与えられます。次に、その石と同じ色のすべての隣接石の等価クラスがマージされます。ボードの各端に沿って各色の「仮想石」を配置します。反対側の同じ色の端石が同じ同値クラスにある場合、接続が確立され、ゲームオーバーになります。
お役に立てれば。
各ピースには、接続されている側 (または側がない) があり、すべてが接続されている小さなサイクルの一部です。ピースが配置されると、隣接するピースがサイドに接続されているかどうかを確認し、隣接するすべてのピースのサイクルをリンクし、必要に応じて「サイド」を調整します。両面が見えたらゲームオーバーです。
これは、グループがキャプチャされたかどうかを判断するために go で使用されるアルゴリズムと非常によく似ています。
A* はあなたにぴったりのアルゴリズムだと思いますが、
単純すぎますが、コンピューターは非常に退屈なプレイをします。
A* チュートリアルを見る
か、実装で遊ぶことができます