五目並べの変種であるゲームを書いています。基本的に、巨大なボード上の三目並べ。
誰かがゲームの優れたAI戦略を知っているかどうか疑問に思います。私の現在の実装は非常に愚かで、長い時間がかかります（O（n ^ 3）、移動するのに約1〜2秒）：
-(void) moveAI {
//check if the enemy is trying to make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkEnemies];
//check if we can make a line horizontally, vertically, or diagonally
//O(n^3 * 3)
[self checkIfWeCanMakeALine];
//otherwise just put the piece randomly
[self put randomly];
}
五目並べについては、勝利戦略はすでに見つかっています。この論文を参照してください：L。ビクターアリス、HJファンデンヘリク、MPH Huntjens、1993年。五目並べと脅威空間検索。私が自分のプログラムを書いているとき、それは私を大いに助けました。このようにして、対戦相手を攻撃し、勝利の組み合わせを見つけるのに非常に優れたプログラムを書くことができます。
このようなゲームのAIを作成するための従来のかなり効果的な戦略は、典型的なツリー検索戦略です。つまり、各ボードの状態はグラフ内のノードを形成し、有向エッジは各ノードと状態の間に配置され、1回の移動で発生する可能性があります。このようにして、ルートボードが空のノードであるツリーが構築されます。次に、ツリーを巧妙な方法でトラバースして、「良好な」状態のように見えるものを見つけます。「良好な」状態は通常、いくつかの巧妙なヒューリスティックを使用する評価関数によって測定されます。明らかに、ツリー内のすべてのノードにアクセスする必要はありません。これは大変な作業です。あなたはただ何か賢いものが欲しいだけです。
事前に計算されたアーリーゲームとエンドゲームを追加して、これらのシナリオをスピードアップし、ミッドゲームで十分に最適化されたツリートラバーサルヒューリスティックに依存することができます。
このようなツリートラバーサルアルゴリズムの実際の名前は、「ミニマックス」アルゴリズムです。ウィキペディアでそれを探すと、かなりまともな資料がたくさん表示されます。アルゴリズムの効率を高める方法はいくつかありますが、その中で最も注目すべきものはアルファベータ法です。必ずそれを確認してください。コネクトフォーのヒューリスティックを見て、それらをゲームに適用する方法を決定することをお勧めします。たとえば、ボードの状態を評価するための適切なヒューリスティックは、継続可能な2ラン、3ラン、および4ランの数をカウントし、それらをスコアに重み付けすることです。（たとえば、各2ランは1ポイントの価値があり、各3ランは10ポイントの価値があり、各4ランは1000ポイントの価値があります）
別の最適化戦略は、ミニマックスアルゴリズムがより多くを検索する必要がある場所を優先するヒューリスティックを開発することです。通常、ボード評価関数のある種の確実性を推定します。
この戦略を使用すると、同じ時間でそれほど愚かではないAIを取得できるはずです。ただし、実際には、このような「単純な」ゲームであっても、本当に優れたAIの構築には多大な労力が必要であり、スマートな動きを邪魔するのに10秒以上かかる場合があります。一方、人間の対戦相手が忙しく考えている間にツリーをトラバースする前に計算するなど、巧妙なプログラミングのトリックがいくつかあります。ねえ、人間はコンピューターがそうしている間に考えるようになる。フェアはフェアです！
私はしばらくの間、同じプログラムのアルゴリズムを作成しようとしています。
もちろん、あなたのプログラムが最初にすべきことは、5を形成して勝つ方法があるかどうかを確認することです。ない場合は、次に、対戦相手がそれを実行できるかどうかを確認し、実行できる場合は防御します。
五目並べを自分でプレイしたことはありますか？あなたは基本をどれだけよく理解していますか？
さて、次のステップは考えることです：私たちが勝つことができる位置にどのように到達することができますか？明らかに、勝つためには4つ続けて持っている必要があります。しかし、次のように4つ続けて形成します。
__________
____XOOOO_
__________
その後、対戦相手はそれを閉じることができます。
しかし、次のように「オープンフォー」を形成すると、次のようになります。
__________
____OOOO__
__________
そうすれば、対戦相手は両側を閉じることができず、あなたは勝つことができます。したがって、オープン4を形成することは、勝つための1つの方法です。さて、質問が来ます：どうすればオープンフォーを形成できますか？確かに、次のように「オープンスリー」を形成すると、次のようになります。
__________
____OOO___
__________
その後、対戦相手は私たちをブロックすることができます：
___________
____XOOO___
___________
そして、私たちは最初に戻っています。
勝つために、同時に2つのオープンスリーを形成することができます。
____________
____OOO_____
_____O______
____O_______
これで、対戦相手がそれらの1つをブロックした場合、もう1つを使用してオープン4を形成できます。
____________
_______O____
___XOOO_____
_____O______
____O_______
____________
そして勝つ：
________O___
_______O____
___XOOO_____
_____O______
____O_______
___X________
五目並べでは、2つのオープンスリーを同時に作成する場合、これは3x3と呼ばれます。
3つ両方が開いている必要があることに注意してください。理由を理解できますか？
勝つ方法は他にもあります。
4x3：勝利の動きと、なぜそれが勝利しているのかわかりますか？
____________
__XOOO______
__XXXO______
____OX______
____________
4x4：勝利の動きを見ますか？
____________
__XOOO______
__XXXO______
__OXOX______
___O________
__X_________
これらはゲームの基本にすぎません。戦術を知っていると、AIの構築方法を考えるのに役立ち、原則をハードコーディングできます。
当然、これはほんの始まりに過ぎません。これを実装して、フィードバックをいただければ幸いです。
私はJavaでプログラムを書こうとしています。あなたがプレイテストできるように私が行ったコードを見たいですか？まだあまり良くありませんが、そこから新しいアイデアを得ることができます。コメントと変数名はエストニア語で書かれていますが、理解するのは非常に難しいかもしれません。:(
私は一度五目並べプレーヤーを作成しましたが、アルファベータ法を使用し、各プレーヤーの2秒、3秒、4秒のハーフオープンとフルオープンの数に応じて、各ポジションにスコアを付けることで非常に成功しました。
これを計算することはn^3ではありません。最新の動きが対戦相手のラインのいずれかを閉じるかどうかを確認し、それがあなたのラインの一部を延長するかどうかを確認し、それに応じてスコアを変更します。
さらに上手にプレイする必要がある場合は、チェスコンピューターのテクニックをいくつか調べます。たとえば、検索時に最初に「キラームーブ」（どのムーブがハイスコアを出したか、他のポジションで完全に勝ったかを覚えている）を試すと、ツリー検索の効率が大幅に向上します。アルファベータ法で最初に想定される最良の動きを試すことが重要です。
プレーヤーがいる場合は、さまざまなバージョンを相互にプレイして、さまざまな要素（2、3、4、オープン、ハーフオープンなど）のスコアが最適かどうかを確認する必要があります。
私も五目並べプレーヤーを作成しました。それは完璧ではありませんが、それはかなりまともなゲームをプレイし、それは確かに私よりも優れたプレーヤーです。とにかく、私はそれを見つけました：
したがって、私の五目並べプレーヤーは、深さ検索なしですべてのボード位置を評価します。水平、垂直、斜めのボードラインを文字列に分割します。次に、テーブルでそれらの文字列のパターンを検索します。黒人プレイヤーの場合、いくつかのパターンは次のとおりです。
Xは黒のプレーヤーの石をマークし、Oは白のプレーヤーの石をマークし、「-」は空の位置をマークします。プレーヤーは見つかったすべてのパターンを合計し、見つかった最高スコアの動きをします。