ボードゲームAIをブラウザで動かす！C++とJavascriptを組み合わせたシステム開発

初めに

最近、AtCoder Heuristic Contestに何回か出場するようになり、「ゲームAI」「探索アルゴリズム」というものを学び始めました。

その中で、「学んだゲームAIの知識を、本物のボードゲームで使ってみたい！」、「せっかくなら作ったAIをブラウザに出して、手軽に遊べるようにしたい！」と考えるようになりました。

思い立ったが吉日ということで、実際に、ボードゲームAIを作り、かつそのAIとブラウザ上で対局できるシステムも作ってみました。 本記事では、その軌跡を共有したいと思います。

ゲームAIに興味のある方でも、複数言語を組み合わせたシステムに興味のある方でも、ただTech記事を読みたい方でも、どなたか一人でもお役に立てば幸いです。

ゲームの説明

今回題材にしたゲームはこちら、2007年に学研から発売された「mattix」というボードゲームです。

4×4または6×6の盤面に、数字が書かれた駒と、X印のクロスチップ1枚が敷き詰められています。なお、駒の色に区別はありません。(※ベーシックルールでは白だけ使いますが、今回は関係無し)

(1) 先手は、クロスチップのある「行」の駒を一つ選びます。例では、-2、2、7が選べます。

(2) 選んだ駒を盤上から取り、クロスチップをその位置に移動させます。その時、取った駒の数字がスコアに加算されます。例では、7を取ったので、先手のスコアが+7されます。負の数を取った場合は当然スコアが減ります。

(3) 後手は、クロスチップのある「列」の駒を一つ選びます。例では、8、6、4が選べます。

(4) 同様に選んだ駒を盤上から取り、クロスチップをその位置に移動させます。取った駒の数字がスコアに加算されます。例では、8を取ったので、後手のスコアが+8されます。

これを繰り返し、最終的にクロスチップが動かせなくなったらゲーム終了で、その時点でのスコアが高い方が勝利です。ゲームの進行によっては、盤上に駒が残っていてもゲーム終了になることもあります。

今回は、このボードゲームおよびその思考AIを一からブラウザに実装しました。

完成品 「WebMattix」

本文が長いので、まずは完成品を貼ります。
https://t-rakko.github.io/mattix/

宣言通りブラウザ上で手軽に遊べるようになっているので、ぜひ遊んでみてください。スマホでも動作します (Galaxy S20で動作確認済)。

CPU vs CPUの対局を観戦することもできます。

システム構成＆登場人物

ゲームAIをブラウザ上で動かすということで、せっかくなので、バックエンドとフロントエンドを分けてシステム開発としての体裁を取ってみました。

全体図

ユーザからの入力、およびフロントエンド・バックエンドのやり取りの処理の流れを、図示しました。
今回は、フロントエンドをJavaScript、バックエンドをC++で実装しています。

ゲームAI / バックエンド：C++

本記事の初めに「ブラウザで手軽に遊べる」という要件を定めましたが、その「手軽さ」の中には、「 十分にAIが強く、かつCPUの思考時間が十分に短い 」という要望も含まれています。(欲張り)

ゲームAIのロジックを組めるくらいに手に馴染んでいる＋実行速度が速い言語、という観点から、今回はバックエンドにC++を選定しました。

UI / フロントエンド：JavaScript

「Webブラウザで動かす」という目的から見れば、UnityのWebGLなども選択肢に入りそうです。

ただ、「手軽さ」の要件の中には、「 アクセスしたときにほぼ待ち時間が無い 」という要望も含まれており(欲張り)、読み込みが重いとスマホでのプレイ体験を損ねそうです。

そこで、今回フロントエンドは、軽量さを求めて、HTMLとJavaScriptを直打ちすることにしました。

コンパイラ： Emscripten

欲張りな要望セットのおかげで、C++とJavascriptを繋ぐ必要が出てきました。

しかし、世の中にはすでに「C++をブラウザで動かす」というニーズがあったようで、C++のコードをJavascriptと互換のあるWebAssemblyに変換できるコンパイラ「Emscripten」が存在していました。今回はこれを活用することにします。

システムテスト / ビジュアライズ： Python

ゲームAIが完成した後は、ただ作って終わりではなく、例えば 作ったAI同士を大量に対局させて勝率などのデータを検証したい 、また、 その際にはグラフなどで分かりやすく図示したい ですね (欲張り)。

手軽に条件を変えながら実行ファイルを呼び出せ、かつビジュアライザも兼ねられる言語と言えば、Pythonが筆頭でしょう。システムテスト役にPythonを選定します。

ホスティング：GitHub Pages

「ブラウザでゲームAIを動かす」目標のためには、HTML・JavaScript・(C++をコンパイルした)WebAssemblyをどこかのサーバーに置いてドメインを得る必要があります。

今回は、無料でWebページを静的ホスティングできるGitHub Pagesというサービスを使用しました。

具体的な実装の詳細

完成品のソースコードはこちらです。
https://github.com/t-rakko/mattix

この記事では、実装の詳細の一部と、実装に当たって気にしていたことを説明していきます。

バックエンドの実装：NegaAlpha法+Iterative Deepeningによる交互着手ゲームの先読み

Mattixは、二人零和有限確定完全情報ゲーム (Wikipedia)に属するボードゲームです。

そのため、適切な盤面評価関数を作ることで、古典的なゲームAIアルゴリズムであるMiniMax法やAlphaBeta法が適用可能です。

今回は、評価関数を「(先手のスコア) - (後手のスコア)」とした NegaAlpha法 (AlphaBeta法の実装を少し単純化した手法)を実装しました。

ただし、Mattixは理論上完全読みが可能とはいえ、6×6の盤面では探索時間がかなり長くなってしまいました。「手軽に遊べる」要件として、できれば「 CPUの思考時間は1秒以内 」としたいと思います(欲張り)。
そのための手法として、 Iterative Deepening (Wikipedia) という、徐々に探索深さを深くしていくアルゴリズムを採用しました。

NegaAlpha法およびIterative Deepeningの実装に当たっては、こちらのサイトをとても参考にしました。この場を借りてお礼申し上げます。
https://qiita.com/thun-c/items/058743a25c37c87b8aa4

「思考時間を1秒に制限する」という制約の中で、AlphaBeta法の枝刈りが意味を発揮していました。
今回のケースの初期盤面からは、MiniMax法(NegaMax法)だと7手先しか読めませんが、 AlphaBeta法(NegaAlpha法)で枝刈りをすることで12手先が読めるようになっていました 。高速化は強さに直結するということを実感できますね。

実装の一部を以下に抜粋します。

// スコア計算
Score negaAlphaScore(const GameState &state, Score alpha, Score beta, const int depth, const TimeKeeper &time_keeper) {
    if (time_keeper.isTimeOver()) return 0;
    if (depth == 0 || state.isFinished() || state.getValidActions().empty()) {
        return state.getScoreFromCurrentPlayerView();
    }

    for (const auto &action : state.getValidActions()) {
        GameState next_state = state;
        next_state.advance(action);
        Score score = -negaAlphaScore(next_state, -beta, -alpha, depth - 1, time_keeper);
        if (time_keeper.isTimeOver()) return 0;

        if (score > alpha) {
            alpha = score;
        }
        if (alpha >= beta) {
            //常に手番プレイヤー視点で探索することで、βカットのみ考えれば良くなる
            return alpha;
        }
    }
    return alpha;
}

// 深さ制限と制限時間(ms)を指定してNegaAlpha法で行動を決定する
Action negaAlphaActionWithTimeThreshold(const GameState &state, const int depth, const TimeKeeper &time_keeper) {
    Action best_action = { -1, -1 };
    Score alpha = -INF; // [memo]INT_MINを使わないこと。-INT_MINがオーバーフローする。
    Score beta = INF;
    for (const auto &action : state.getValidActions()) {
        GameState next_state = state;
        next_state.advance(action);
        Score score = -negaAlphaScore(next_state, -beta, -alpha, depth - 1, time_keeper);

        if (time_keeper.isTimeOver()) return ACTION_ERR;
        if (score > alpha) {
            best_action = action;
            alpha = score;
        }
    }
    return best_action;
}

// CPUの行動決定エンジン。制限時間(ms)を指定して、反復深化で行動を決定する
Action iterativeDeepeningAction(const GameState &state, const int64_t time_threshold) {
    auto time_keeper = TimeKeeper(time_threshold);
    const int depthlimit = state.players[state.currentPlayerID].cpuStrength;

    Action best_action = { -1, -1 };
    for (int depth = 1; depth <= depthlimit; depth++) {
        if (depth > state.boardSize * state.boardSize) break;

        Action action = negaAlphaActionWithTimeThreshold(state, depth, time_keeper);

        if (time_keeper.isTimeOver()) {
            break;
        }
        else {
            best_action = action;
        }
    }
    return best_action;
}

// CPUの行動を、NegaMax法＋IterativeDeepeningによって探索する。探索時間は1秒。
Action calculateAction(const GameState &state) {
    return iterativeDeepeningAction(state, CPUMaxThinkTimeInMs);
}

コンパイラ(周辺)の実装：Emscripten用の関数ラッピング

上記の思考AIをEmscriptenでコンパイルすることで、「WebAssembly」というJavaScriptから呼び出せるバイナリに変換してくれます。

Emscriptenの記法にはいくつか作法があるようですが、おそらく最新と思われる embind を使ったところ、ほとんどトラブルなくC++をWebAssemblyに変換することができました。
https://emscripten.org/docs/porting/connecting_cpp_and_javascript/embind.html

まず、下のような簡単なラッピング用の関数を用意します。

#ifdef __EMSCRIPTEN__
#include <emscripten/bind.h>
GameState JS_state;

//ラッパー関数群
//初期化
void JS_initializeGame(int boardsize, bool player1_isCPU, int player1_CPUstrength, bool player2_isCPU, int player2_CPUstrength) {
    GameSetup setup;
    setup.boardSize = boardsize;
    setup.player1_isCPU = player1_isCPU;
    setup.player1_CPUstrength = player1_CPUstrength;
    setup.player2_isCPU = player2_isCPU;
    setup.player2_CPUstrength = player2_CPUstrength;
    JS_state.initializeGame(setup);
}
//終了判定
bool JS_isFinished() { return JS_state.isFinished(); }
//思考
int JS_calculateAction() { return action2idx(calculateAction(JS_state)); }
//実行
void JS_advance(int chipIndex) { JS_state.advance(idx2action(chipIndex)); }

EMSCRIPTEN_BINDINGS(myModule)
{
    emscripten::function("JS_initializeGame", &JS_initializeGame);
    emscripten::function("JS_isFinished", &JS_isFinished);
    emscripten::function("JS_calculateAction", &JS_calculateAction);
    emscripten::function("JS_advance", &JS_advance);
}
#endif

そして、下のコマンドを打つだけです。

em++ --bind -O2 Algorithm.cpp -o Algorithm_JS.js

<fstream>や<chrono>など色々ライブラリを使っているのに、何も修正不要で普通に動いてくれたので、かなりお手軽でした。

【脱線】LLVM

Emscriptenは、内部的には LLVM という任意のプログラミング言語に対応できるコンパイラ基盤を用いているようです。LLVMに関してはこちらの記事が詳細で分かりやすかったです。
https://qiita.com/Anko_9801/items/df4475fecbddd0d91ccc

フロントエンドの実装１：JavaScriptには可能な限り情報を持たせない

閑話休題。
フロントエンド側の設計指針としては、「 JavaScriptに情報を持たせない 」ことを心がけていて、実装も全体図のとおり、事あるごとにC++に問い合わせを出す構成にしています。

これには理由があります。

一番初めにフロントエンドの実装をChatGPTに考えてもらったところ、ゲームの進行も盤面管理も表示する情報の加工もすべてフロントエンドが行う形のコードが出力されました。

が、今回のゲームAIの主体はあくまでC++側です。情報を管理する場所が複数できてしまうと、どちらを見ればよいのか、どのタイミングでどちらが正しい情報なのか？というのを考慮しないといけなくなり、設計が複雑になりそうでした。また、情報の導線がもつれて「C++層からJavaScript層に最新のデータを取りに行く」羽目になった日には、どちらが主体か分からなくなってしまいます。

そこで今回は、C++にのみデータを置き、JavaScriptは毎回C++に問い合わせを出すようにすることで、データの整合性を保てるようにしました。

欠点として、画面更新のたびに毎回C++層に盤面情報の問い合わせを走らせているので、オーバーヘッドが大きくなってしまっている可能性は高そうです。

function handleCellClick(cell) {
    if (!isGameActive) return;
    if (isCPUThinkLocking) return;
    // 有効な処理か判定
    const chipIndex = parseInt(cell.dataset.index);
    if (!Module.JS_isValidAction(chipIndex)) return;
    // 実行
    Module.JS_advance(chipIndex);
    // ボード更新
    updateBoardAndInfo()
    // ゲーム終了していたら終了
    if (Module.JS_isFinished()) {
        endGame();
    }
    // CPUの手番に移行
    processCPUIfNeeded();
}

embindで出力したC++の関数は、グローバル変数Module配下の関数として呼び出せています。JavaScript側でも特殊な処理は不要で、ここでもEmscriptenの便利さを実感できました。

【発展】Presentation-Domain Separation

「C++とJavaScriptでデータをどちらが管理するか切り分ける」という方針ですが、より一般的な概念として、 Presentation-Domain Separation (PDS) という概念があるそうです。
https://docs.nextdesign.app/extension/docs/design-practice/presentation-domain-separation

UI層とそれ以外の層を切り分けるという話では、MVVMパターンなどのアプリケーションのデザインパターンとも共通点がありそうでした。
MVVMパターンの意味については、以下のページのスライドが分かりやすかったです。
https://ugaya40.hateblo.jp/entry/model-mistake

フロントエンドの実装２：ゲームAIは非同期処理に投げてUIが固まらないようにする(失敗)

今回、ゲームAIをIterative Deepeningで1秒間考えるようにした都合で、ゲームAIの呼び出し元関数は1秒間ブロッキングします。

つまり、 CPUのターンになるたびに、毎回ページの応答が1秒間止まってしまう ということです。これはあまりよろしくないですね。

そこで、CPUの思考開始を asyncで非同期処理に投げる とともに1秒後のコールバックを出し、「CPUの思考が完了した」＆「1秒のタイムアウトが過ぎた」のであれば、画面更新することで、CPUの処理を別のスレッドに回して画面のロックを防ぎました。

、、、、、、防いだつもりでした。

async function processCPU() {
    isCPUThinkLocking = true;
    const promise1 = new Promise(resolve => {
        setTimeout(resolve, 1000);
    });
    const promise2 = new Promise(resolve => {
        const nextMove = Module.JS_calculateAction();
        resolve(nextMove);
    });
    const [_1, nextMove] = await Promise.all([promise1, promise2]);
    isCPUThinkLocking = false;

    Module.JS_advance(nextMove);
    updateBoardAndInfo();
}

しかし、今回のWebMattixで「6×6」「CPU(さいきょう)」でプレイしてもらえるとすぐに分かるのですが、実際には、CPU(さいきょう)の思考時間中、画面が固まってしまっていて、UIのボタンが反応しなくなってしまっています。なぜでしょうか？

調べたところ、 JavaScriptはもともとシングルスレッドで動いている こと、 ここでの「非同期処理」は実行の順番をずらすだけである こと、そして、 setTimeOutなどのいわゆる「非同期関数」は、JavaScript上で別スレッドを作っているわけではなく、WebAPIを介してブラウザに処理を任せているだけである こと、などを初めて知りました。
https://qiita.com/UTDoi/items/d49ea919818d9b519f93

そのため、外部のWebAPIを使えない通常のユーザ関数の場合は、asyncを書いたところで結局メインスレッドで処理されており、結果としてUIがブロックされている、、、という状態になっていそうです。

無念！

【追記】Web Worker

2019年に策定された最新のHTML規格「HTML Living Standard」にて、Web Workerというものが定義されたようです。
https://developer.mozilla.org/ja/docs/Web/API/Web_Workers_API

どうやらJavaScript上で複数のワーカースレッドを立てられる仕組みが整備されたようで、これを使えば、今回実現したかった「CPUの思考中に画面をブロックさせない」ことが実現できそうですね。

システムテストの実装：実行ファイル呼出＆ビジュアライズをまとめて実行

最後に、完成したAI同士で対局を行い、AIの強さを測ってみることにしました。

コマンドライン引数でテスト条件を指定しながら、繰り返し実行ファイルを呼び出し、結果をビジュアライズするところまでまとめて実施できるようにしました。

def execTestAndVisualize(boardsize, CPUstrength1, CPUstrength2, testcount, output_totalresult_name=None, changeTurn=False):
    result = execTestAndLoad(boardsize, CPUstrength1, CPUstrength2, testcount)

    output_base_string = out_path + "output_" + str(boardsize) + "_" + str(CPUstrength1) + "_" + str(CPUstrength2) + "_" + str(testcount)
    output_figname = output_base_string + "_visualize.png"
    visualize(result, output_figname, CPUstrength1, CPUstrength2, needDisplay=False)

    print("single test execution completed")

def conductAllTests():
    testcount = 500
    output_totalresult_name = out_path + "output_"  + str(testcount) + ".csv"

    boardsize_candidate = [4, 6]
    for boardsize in boardsize_candidate:
        CPUstrength_candidate = range(1, boardsize*boardsize + 1)
        for CPUstrength1 in CPUstrength_candidate:
            for CPUstrength2 in CPUstrength_candidate:
                execTestAndVisualize(boardsize, CPUstrength1, CPUstrength2, testcount, output_totalresult_name)

C++の実行ファイルを呼び出すに当たっては、 subprocess モジュールが便利でした。
https://docs.python.org/ja/3/library/subprocess.html

通常は、C++の呼び出し中はPython側がブロッキングされてしまいますが、subprocess.Popen を使うことで、Pythonをブロックせず別プロセスとしてC++を起動することができました。

「子プロセスが完了するまで無限ループして待機しつつ、子プロセスの標準出力を監視してprintに流す」ことで、今テストがどのくらいまで進んでいるのかを表示できるようになり、簡易的なプログレスバーとしても有効に機能してくれました。

def execTest(cmd_string, testcount):
    proc = subprocess.Popen(cmd_string, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT)

    while proc.poll() is None: #まだ実行中ならNone
        line = proc.stdout.readline().decode('utf8', 'replace')
        if line:
            dispstr = "case " + line.replace('\n', '').replace('\r', '') + " / " + str(testcount) 
            print("\r" + dispstr, end="", flush=True)
    print("")
    print("test completed")

システムテスト結果の考察２つ

考察１：「究極的には、初期配置の運ゲーかも」

今回のWebMattixでは、Iterative Deepening の探索制限深さをそのままCPUのレベルにしています。「ふつう」は探索深さ=1、即ち貪欲に1手先だけを見ます。「つよい」では3手先、「さいきょう」では99手先まで読みます。
ただ、手数がそもそも15手か35手が上限で、かつ1秒間の探索時間制限に引っ掛かるため、「さいきょう」の探索は、1秒の制限で行けるところまで読む、という探索になります。

実際に、AI同士を500局対局させてみました。
このゲームは、駒の数が奇数個である都合上先手が有利なため、先手後手を250局で入れ替えつつ実施しました。

「ふつう」レベル1と、「ふつう」レベル1で対局した場合は、当然50%の勝率でした。

「さいきょう」レベル99と「ふつう」レベル1で対局した場合には、「さいきょう」側が約80.6%の勝率でした。

「さいきょう」でも8割？という気もしましたが、これはおそらく、初期盤面の配置の差を取り返せないケースがある、即ち Matixは究極的には初期配置の運ゲーである ということを指していると考えられます。

探索時間の制限もあって「全読み」ができていないため、はっきりとした結論にはなりませんが、人間同士で対局していた時にはこのような発想はなかった (=しっかり読み切れば必ず勝てると思っていた) ので、なかなか面白い結果になったと思います。

考察２：「奇数手の先読みは、実は評価関数として不適当かも」

また、別の考察として、「ふつう」レベル1のCPUと、レベル1~10のCPUを1000局ずつ先手後手を入れ替えながら対局して、その勝率を集計してみました。

こちらのグラフを見ると、全体として探索深さが上がるほど勝率が上がっていること、そして最終的なレベル99の勝率である80.6%に近づいていることが分かりますが、それに加えて、 「2N手先読みするよりも、2N+1手先読みする方が勝率が悪い」 という傾向がありました。

これは、今回のMattixのような交互二人着手ゲームでは、「先手⇒後手」までを１セットで考えるのが望ましく、 「先手⇒後手⇒先手」のような奇数手読みでのスコア差は、MiniMax法に使う評価関数としては不適切かもしれない 、という可能性を示していそうです。

評価関数の設計が難しい場合には、MiniMax法ではなく「モンテカルロ木探索」と呼ばれるランダムサンプリングに基づいたゲームAIの設計が有効になるそうです。今回のケースでは偶数手読みになるように深さ制限を設定するだけで良さそうですが、別の思考ルーチンを導入してみるというのも面白いかもしれません。

最後に

ひとつの事例ですが、C++でゲームAIを実装したうえで、Javascriptと統合してブラウザ上で遊べるようにするまでの開発記録を紹介しました。

ゲームAIのアルゴリズムを実感を持って理解できただけでなく、Emscriptenというツールの使い方の把握や、JavaScriptの動作原理の理解、Mattixというゲーム自体の性質についての考察も行えるなど、 フルスクラッチでゲームを作ったことで、非常に幅の広い学びを得られた と感じました。

皆さんもぜひ、自作ゲームAIを作ってガンガン公開してください！とても面白いです！

「この記事を追ってみて分からないことがあった」「もっと良いアイデアがあると思う」など、コメントをつけてくださるのも大歓迎です。

宣伝

そもそも「ゲームAI」「探索アルゴリズム」「ヒューリスティック」という言葉になじみがない？

AtCoder Heuristic Contest、出よう！

AHCの解説記事も投稿しています。ご興味があればこちらもどうぞ。
https://zenn.dev/tori_rakko/articles/98bca3b55e93a8
https://zenn.dev/tori_rakko/articles/0affbd5a5d5ef7

先行研究

最後に、ボードゲームAIを自作してWebで動かされている先行研究をいくつかご紹介します。
ほかに載せてほしいものがある場合や、あるいは「この記事を見てボードゲームAI作った」という場合など、お声がけください。

オセロ / NegaScout法 (MiniMax法の系列)
https://www.egaroucid.nyanyan.dev/ja/
https://qiita.com/Nyanyan_Cube/items/1839732d7bdf74caff21
Quoridor / アルファベータ法
https://www.irrrrr.cc/quoridor-AI/dist/
SEPARO / モンテカルロ木探索
https://toruniina.github.io/ja/posts/writing-board-game-ai/
テトリス / Q学習
https://zenn.dev/through/articles/ebe77ac5d02f2d
March / Q学習
https://qiita.com/KazukiOta/items/9f80d389475afcbf3142

---

それでは皆様、良いゲームAIライフを！