👩‍💻
#101　三目並べの盤面の探索と評価

2025/05/27に公開
 三目並べの盤面の探索と評価今回の記事は三目並べの探索の評価(=つまり、三目並べAIの作成)をしてみようと思います


この記事は前回の続きです

 実装方針以下の2つの機能を実装していきます
勝敗判定
探索関数
任意の深さまでの探索を行います


 勝敗判定前回の記事と同じ要領で、3つの石が並んだパターンをコンストラクタ内で生成します
constructor(/*省略*/){

//略

    this.judgeBoards = [];

    for (let i = 0n; i < 6n; i++) {
        for (let j = 0n; j < 6n; j++) {
            //横
            this.judgeBoards.push(0x07n << (i + j * BigInt(BOARD_SIZE)));
            console.log(this.judgeBoards[this.judgeBoards.length - 1]);

            //縦
            this.judgeBoards.push(0x010101n << (i + j * BigInt(BOARD_SIZE)));
            console.log(this.judgeBoards[this.judgeBoards.length - 1]);

            //斜め
            this.judgeBoards.push(0x040201n << (i + j * BigInt(BOARD_SIZE)));
            console.log(this.judgeBoards[this.judgeBoards.length - 1]);

            //斜め
            this.judgeBoards.push(0x010204n << (i + j * BigInt(BOARD_SIZE)));
            console.log(this.judgeBoards[this.judgeBoards.length - 1]);
        }
    }

 探索関数以前も完全読み切りで探索関数を実装しましたが、今回は探索を途中で打ち切る(任意の深さまで探索する)ため、実装に大きな修正を加えます
ここで重要なポイントは以下のとおりです
最大探索深さに到達した場合に、その盤面の評価値を返す

field.evaluate()から返却される値は⭕️が有利な場合は正の値に、❌が有利の場合は負の値になる
候補の手から評価値が一番高い手を選択する
内部的に初期値の候補として指し手が範囲外でスコアが限りなく低い手を登録しておく(実装上はNumber.NEGATIVE_INFINITYを指定している)

function search(field: Field, maxDepth: number, depth = 0): { position: { x: number, y: number }, result: Color, score: number } {
    //勝敗判定
    const judge = field.judge();
    if (judge != undefined) {
        return { position: { x: -1, y: -1 }, result: judge == Color.SPACE ? Color.SPACE : judge, score: 0 };
    }
    if (depth == maxDepth) {
        return { position: { x: -1, y: -1 }, result: Color.SPACE, score: field.evaluate() };
    }

    //空白の盤面を取得する
    const space = field.getFieldTypeBitBoard().space;

    if (Color.BLACK == field.getTurn()) {
        let score = Number.NEGATIVE_INFINITY;
        let color = Color.SPACE;
        let position = { x: -1, y: -1 };
        //おけるマスに置いていく
        for (let i = 0; i < 64; i++) {
            if (((space >> BigInt(i)) & 0x01n) == 0x01n) {
                const x = i % BOARD_SIZE;
                const y = Math.floor(i / BOARD_SIZE);

                //親盤面をクローンして石を置く
                const cloneField = field.clone();
                cloneField.putStone(i);

                //再帰的に探索関数を呼び出す
                const result = search(cloneField, maxDepth, depth + 1);

                if (result.score > score) {
                    score = result.score;
                    position = { x: x, y: y };
                }
                else if (result.score == score) {
                    if (Math.floor(Math.random() * 64) % 64 == 0) {
                        position = { x: x, y: y };
                    }
                }
                if (result.result == field.getTurn()) {
                    score = Number.MAX_SAFE_INTEGER;
                    position = { x: x, y: y };
                    color = result.result;
                    break;
                }
            }
        }

        return { position: position, result: color, score: score };
    }
    if (Color.WHITE == field.getTurn()) {
        let score = Number.POSITIVE_INFINITY;
        let color = Color.SPACE;
        let position = { x: -1, y: -1 };
        //おけるマスに置いていく
        for (let i = 0; i < 64; i++) {
            if (((space >> BigInt(i)) & 0x01n) == 0x01n) {
                const x = i % BOARD_SIZE;
                const y = Math.floor(i / BOARD_SIZE);

                //親盤面をクローンして石を置く
                const cloneField = field.clone();
                cloneField.putStone(i);

                //再帰的に探索関数を呼び出す
                const result = search(cloneField, maxDepth, depth + 1);

                if (result.score < score) {
                    score = result.score;
                    position = { x: x, y: y };
                }
                else if (result.score == score) {
                    if (Math.floor(Math.random() * 64) % 64 == 0) {
                        position = { x: x, y: y };
                    }
                }
                if (result.result == field.getTurn()) {
                    score = Number.MAX_SAFE_INTEGER - 1;
                    position = { x: x, y: y };
                    color = result.result;
                    break;
                }
            }
        }

        return { position: position, result: color, score: score };
    }

    throw new Error("");

}

 動かしてみる以下のようにmain関数を記述し、探索関数を適宜呼び出すことでコンピュータ対コンピュータの対戦を行うことができます
TypeScript
function main() {
    const field = new Field();
    while (true) {
        console.log('-----')
        let x: number, y: number;
        let r = search(field, 3);
        console.log(r);
        x = r.position.x;
        y = r.position.y;
        console.log(`score: ${r.score}`);

        field.putStoneXY(x, y);
        field.draw();
        console.log(`x: ${x}, y: ${y}`);

        const judge = field.judge();
        if (judge != undefined) {
            if (judge == Color.SPACE) {
                console.log("draw");
            }
            else {
                console.log(judge == Color.BLACK ? "⭕️ win" : "❌ win");
            }
            break;
        }
    }
}

main();

 まとめ今回は三目並べのAIのようなものを作成してみました
オセロの探索部を作ったことがあるのでそれを思い出して作ってみたのですが、三目並べではオセロに比べて一つの盤面あたりの着手可能数がかなり多い(初手で64通り、2手目で63通り…)ので、思ったより探索が遅く、動作確認に手間取ってしまいました。高速化のために枝刈りができるような探索方法を採用したり、効率的に枝刈りができるように探索順序を並び替えたり工夫の余地がありそうです
三目並べの盤面の探索と評価

実装方針

勝敗判定

探索関数

動かしてみる

まとめ

Discussion
