まず第一に、これは、プログラムで Five in a Row を再生する方法に関する問題ではありません。そこに行って、それをしました。
導入説明
私は、遺伝的に改善する AI を実験するためのフレームワークとして、5 列連続ゲームを作成しました (ああ、それはひどく大げさなように聞こえます)。ほとんどのターンベースのゲームと同様に、可能なすべての動きにスコアを割り当て、最高スコアの動きをプレイすることによって、最良の動きが決定されます。スコアを移動 (正方形) に割り当てる関数は次のようになります。
マスにすでにトークンがある場合、そのマスに新しいトークンを配置することは違法であるため、スコアは 0 です。
各正方形は、最大 20 の異なる勝利行 (横 5 行、縦 5 行、斜め 10 行) の一部になることができます。正方形のスコアは、これらの各行のスコアの合計です。
行のスコアは、その行に既にある味方トークンと敵トークンの数によって異なります。例:
- 味方のトークンが 4 つ並んでいる行には無限のスコアが必要です。これは、そこにトークンを配置するとゲームに勝つためです。
- 4 つの敵トークンがある行のスコアは非常に高くなるはずです。なぜなら、そこにトークンを置かないと、対戦相手は次のターンに勝つからです。
- 味方トークンと敵トークンの両方を含む列はスコア 0 になります。これは、この列が勝利列の一部になることは決してないためです。
このアルゴリズムを考慮して、TBrain という型を宣言しました。
type
TBrain = array[cFriendly..cEnemy , 0..4] of integer;
配列内の値は、味方トークンが N 個で敵トークンが 0 個の行、または味方トークンが 0 個で敵トークンが N 個の行のスコアを示します。行に 5 つのトークンがある場合、行がいっぱいであるため、スコアはありません。
実際、どの値を配列に入れるかを決定するのは非常に簡単です。Brain[0,4] (4 つの友好的なトークン) は「無限」である必要があります。これを 1.000.000 と呼びましょう。vBrain[1,4] は非常に高くする必要がありますが、脳が自分自身に勝つよりも敵の勝利をいくつかブロックすることを好むほど高くしてはいけません
次の (ありそうもない) ボードを考えてみましょう:
0123456789
+----------
0|1...1...12
1|.1..1..1.2
2|..1.1.1..2
3|...111...2
4|1111.1111.
5|...111....
6|..1.1.1...
7|.1..1..1..
8|1...1...1.
プレーヤー 2 はトークンを (9,4) に配置し、(4,4) ではなく、ゲームに勝つ必要があります。ただし、プレーヤー 1 の 8 つの潜在的な勝利行をブロックします。したがって、vBrain[1,4] は (vBrain である必要があります) [0,4]/8)-1. このように作業すると、「脳」の最適値を見つけることができますが、これは私が興味を持っていることではありません。最適な値を見つけるアルゴリズムが必要です。
私はこのフレームワークを完全に決定論的に実装しました。スコアに追加されるランダムな値はなく、複数の正方形が同じスコアを持つ場合、左上が選択されます。
実際の問題
紹介はここまでで、次は興味深い部分です (少なくとも私にとっては)。
vBrain1 と vBrain2 という 2 つの「頭脳」があります。これらを繰り返し改善するにはどうすればよいですか？私はこのようなものを想像します：
- vBrain1 と vBrain2 をランダムな値で初期化します。
- それらの間のゲームをシミュレートします。
- 勝者から敗者に値を割り当て、そのうちの 1 つをランダムにわずかに変更します。
これはうまくいかないようです。脳は賢くなることはありません。なんで？
同じ 2 つの頭脳間の 2 つのゲームが異なるように、score-method は結果にいくつかの小さなランダム値を追加する必要がありますか? 反復ごとに値をどのくらい変更する必要がありますか? 「脳」をどのように初期化する必要がありますか? 定数値で？ランダムな値で？
また、これはAI や遺伝的アルゴリズムと関係がありますか?
PS: 質問は Five in a Row とは何の関係もありません。これを選んだのは、非常に単純な "Brain" を実験用に宣言できるからです。