以前の記事で、○×ゲームを学習するAIくんを作りました。
ただ機械学習のモデルみたいなものを作って満足するのはもったいないので、これを応用してあるボードゲームで遊んでみたいと思います。
今回使わせて頂くのは2022秋のゲムマで出会った、トラペーツというゲームです。
これは（少なくとも見た目は）かなりシンプルなアブストラクトゲームなので、強化学習させるのにはかなり向いているゲームだと思います。
ちなみに、製作者の方も先後どちらが有利かはっきりとはわかっていないらしいです。じゃあ突き止めてやろうじゃないの。
Contents
ルールのおさらい
基本ルールはレビュー記事にも書いていますが今一度おさらいしておきます。
- 直径5マスの六角形のボード、マスは19個。中央に1枚のタイルが置かれた状態で開始。
- 交互にタイルを1枚ずつ、好きな場所・好きな向きで配置する。
- 周囲を完全に囲まれたタイルは60度回転させる。
- 自分の色を7個以上つなげたら勝ち。ただし、同時に相手の色も7個以上つながったら負け。
- 最後までどちらも7個以上つながらなければ、繋がっているタイルの個数の最大値が大きい方が勝ち。それも同じなら先手勝ち。
コーディングする
前回作ったAIくんはかしこいことに強化学習の部分とゲームの構造の部分を分けて記述しているので、ゲームの構造を理解させてあげれば上手いこと学習してくれるはずです。そこで、今回はトラペーツのルールをコーディングします。
え？ プログラミングそこそこわかる方？ またまた～そんな簡単に行くわけないじゃん～www って？ 言いたいことはわかるのでとりあえずまずは黙って見といてください。
ゲーム構造のインターフェース
ゲーム構造はこのインターフェースを継承します。
using System;
namespace TicTacToeLearning.mainsource.gamestructure.template {
interface IStructure {
int IsWin(int board);
int[] ListingLegalMove(int board, bool first);
int Initialize();
string DecodeBoard(int board) {
return board.ToString();
}
int EncodeBoard(string str) => throw new NotImplementedException();
}
}
必要なのは以下の情報（関数）です。
int IsWin(int board): 現在の盤面がどちらかの勝利条件を満たしているかどうかを判定する。int[] ListingLegalMove(int board, bool first): 現在の盤面から可能な次の手を列挙した配列を返す。int Initialize(): 盤面の初期値を返す。
盤面の表し方
戻り値が全部int型なのは、盤面の状態をビットボードで記述しているためです。
ビットボード
ゲームの盤面を全て0と1のみのバイナリデータで表現したもの。文字列型や配列等を使うより各種演算が高速にできるという利点がある。チェスや将棋、囲碁などのAIで実際に使用されている。
○×ゲームだと、空マスを00、○を10、×を01で表し、それが９マスあるので、ただ並べるだけで、盤面の状況を表せました。１マスの状態を表すのに2桁しか使わないので最長でも18bitで表せます。
たとえばこの盤面は、0b010001011000100010 = 71202です（盤面を右下から左上に向かって読みます）。
さて、トラペーツでは話はそう簡単ではありません。マスの状態は7種類あり、それを表すこと自体には3bitしか使いません(\(2^3=8\)なので)が、それが19マスもあるので、必要なbit数は3×19=57bitです(もうちょっと上手く考えると減らせはしますが、どっちみち32bit以下にするのは無理です)。int型は32bitですので入り切りません。64bit対応のlong型を使うことになりそうです。
JavaとかCを触っている人ならわかると思いますが、そうですね、このインターフェースはint型で書いてるので対応できてません。とりあえず全部longに書き換えてきます。くそぅ。
マスの対応のさせ方
空マスを000で表すのは良いとして、他の6種類をどう表すかですが、000と111を除く6種類を1対1対応させることになります。
(i % 6) + 1とかやれば６回回すと元に戻りますが、それだと19マスのタイルを全て回転させる操作を考えた時にforループを19回回す必要があります。単に「６回計算すると戻る」だけでは不十分で、可能ならば19マスをいっぺんに操作できる式にしたいです。
そこでこのような対応にしました。ベクトル合成みたいなイメージですね。
これだと以下の式を6回回すことで元に戻り、かつ for や if などの式不要で何枚でも同時に回転させられます。
(~i << 1 & ~i >> 2) & 0b111
long[] ListingLegalMove(long board, bool first)
引数のうち真偽値firstは先手後手を区別するためのものですが、このゲームでは先手も後手も打てる手は同じ（○×ゲームは先手は○、後手は×しか置けなかったがトラペーツにはそれがない）ですので今回は無視します。
ただ配置するだけなら実装はそこまで難しくありません。以下のような手順を経れば配列が得られます。
- １マス毎にそこが空きマスかどうかを判定する
- 空きマスと判定されたマス毎に、そのマスにタイルを6通りの向きで1枚加えた、6通りの盤面を配列に追加する
ただし、このゲームには「周囲を完全に囲まれたタイルを1枚選んで60度回転させる」というルールがあります。そこで、さらに……
- 配列に盤面を追加する前に、最後の配置で囲まれたタイルがないかどうかを判定する
- なければ、追加しようとしている盤面をそのまま追加
- あれば、追加しようとしている盤面の代わりに、囲まれたタイルを60度回転させた盤面を追加
という操作を追加しなくてはなりません。配列長は初期盤面で18×6=108、高々200程度でしょう。
public long[] ListingLegalMove(long board, bool first) {
List<long> legalMove = new List<long>();
long checkTag = 0b111;
for (int i = 0; i < 19; i++) {
if ((board & checkTag) == 0) {
List<int> list = new List<int>();
for (int j = 1; j <= 6; j++) { //置いたタイルの周囲6マスに回転対象のタイルがあるかどうかを調べる
int adj = AdjacentTileNum(i, j);
if (adj == -1) {
continue;
}
if ((board & ((long)0b111 << (adj * 3))) == 0) {
continue; //空白タイルは調べない
}
int count = 0;
for (int k = 1; k <= 6; k++) {
int adj2 = AdjacentTileNum(adj, k);
if (adj2 == -1 || i == adj2) {
count++;
continue;
}
if ((board & ((long)0b111 << (adj2 * 3))) == 0) {
break; //空白タイルがある場合
}
count++;
}
if (count == 6) {
list.Add(adj);
}
}
for (long move = 1; move <= 6; move++) {
long key = TrapezUtil.OptimizeBoardKey(board | move << i * 3);
if (list.Count != 0) {
foreach(int spin in list) {
long cw = TrapezUtil.SpinTile(key, new int[1] { spin }, true);
if (!legalMove.Contains(cw)) {
legalMove.Add(cw);
}
long ccw = TrapezUtil.SpinTile(key, new int[1] { spin }, false);
if (!legalMove.Contains(ccw)) {
legalMove.Add(ccw);
}
}
} else {
if (!legalMove.Contains(key)) {
legalMove.Add(key);
}
}
}
}
checkTag <<= 3;
}
return legalMove.ToArray();
}何書いてるかわからないけどこれで動くのでこれでいいことにします。
int IsWin(long board)
これを考えるのにしばらく眠れない日々が続いていたんですが、愚直に実装するしかなさそうです。もっとスマートで動作も軽いのが思いついたら更新しますが、ひとまずは以下のような形で行きます。正直、数オリとか競プロとか強い人に考えてほしい。
- long型で表された盤面を受け取り、19×19の隣接行列にする（白黒それぞれについて行列を作る）
- 深さ優先探索で全てのノードに対して接続しているノードの数を数え、最大値を取る
- 白か黒の接続数の最大値が7を超えていたら勝利判定をする
- 両方が7を超えていたらどちらの手番かを盤面から逆算する
- 19マス全てが埋まっていたら接続数の最大値が大きい方が勝利とする
- 19マス全て埋まり接続数の最大値が同じなら先手勝ちとする
public int IsWin(long board) {
int tilePlayed = TrapezUtil.CountTilePlayed(board);
if (tilePlayed < 7) {
return 0;
}
bool[][][] adjMatrix = AdjMatrix(board);
bool[][] checks = new bool[2][] { new bool[19], new bool[19] };
int[] adjLong = new int[2];
for (int i = 0; i < adjMatrix.Length; i++) {
for (int j = 0; j < 19; j++) {
if (!checks[i][j]) {
int tmp = 0;
DFS(adjMatrix[i], j, ref checks[i], ref tmp);
if (tmp > adjLong[i]) {
adjLong[i] = tmp;
}
}
}
}
if (tilePlayed == 19) {
if (adjLong[0] > 6 && adjLong[1] > 6) {
return tilePlayed % 2 == 1 ? 1 : -1;
} else if (adjLong[0] > adjLong[1]) {
return 1;
} else if (adjLong[1] > adjLong[0]) {
return -1;
}
return 1;
} else {
if (adjLong[0] > 6 && adjLong[1] > 6) {
return tilePlayed % 2 == 1 ? 1 : -1;
} else if (adjLong[0] > 6) {
return 1;
} else if (adjLong[1] > 6) {
return -1;
}
}
return 0;
}一旦走らせてみよう
初期配置から探索させるのは状態量が多すぎ、現状の実装では明らかに”やり過ぎ”です。
そこでとりあえず途中の盤面から学習させてみます（テキトーに1000001の盤面を生成したらこれが出てきただけです）。以下の盤面は人間同士なら明らかに勝敗が確定している盤面です。後手(黒)からで必勝形のはずです。
100万回学習を走らせてみた結果がこちら。実行時間はおよそ6分でした。
勝利確定の盤面に対して評価値10をつけるようにしているので、後手の手番で-9.86…というのはほぼ後手勝ち確定であると見なしていると言えます。上手く行っていますね！
盤面のUIを作る部分を完全に流していますが、とても時間がかかっています。これ大変だったよ。
何かがおかしい？
この盤面から黒先だと黒は割と何をやっても勝てそうに思えますが、実際に勝ち確定に近い評価を出している手は１つしかありません。そんなはずはないような気がするのですが、これはどういうことなのでしょうか？
このコードでは軽量化のため、勝ち確定の手が見つかるとその他の手は探索しても仕方がないので探索しないようになっています。そのためたまたま見つかった勝ち確定に近い手ばかりを集中的に探索してしまうので、このような評価になります。
また、実際に手を進めてみると、白は人間なら絶対にそこには置かないだろうみたいな場所に置いて黒の勝利を座視するだけになってしまいます。
これは勝ち以外の盤面の価値を全てフラットだとみなしている（報酬を与えていないから）ため、自分の色をとりあえず最低限繋げておくような、いわゆる「形作り」のような手にAIが価値を感じていないためです。負けは負け、というわけですね。
AIを作っている人の間では有名な話ですが、よく「ただ強いAIを作るのは簡単だが、接待して自然に負けるAIを作るのは難しい」ということが聞かれます。将棋のAIなんかで、終盤負けが確定したところから無意味な王手を繰り返すようなのが例としてわかりやすいでしょう。人間味のある手を指させるのは結構難しいのです。
変化が少なく短手数の形ならこの程度の時間で読ませることができますが、変化が多かったり、勝ちになるまでの手数が多かったりすると、実行時間がどんどん伸びていき、また評価も全然定まらなくなってきます。
しばらくはこのAIを改良してみて、どこまで読ませることができるか、あるいは結論を出すことが可能かどうか、試行錯誤してみたいと思います。また何かアップデートがあれば更新しますので、お楽しみに。
