#83 ⭕️❌ゲームで学ぶ探索

⭕️❌ゲームで学ぶ探索

今回の記事は⭕️❌ゲームの完全読みについて解析してみようと思います

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

探索とは

今回はMinMax法という探索手法を用います

MinMax法とは自分の手番では自分にとって最善な手を、相手にとっては相手にとって最善な手を指すことを前提とした探索アルゴリズムです

実装例

⭕️❌ゲームに必要なクラスとして前回の記事で作成したFieldクラスに、勝敗の判定を行うjudge()を追加作成します

勝敗判定

勝敗判定はjudgeBoardsにあるように縦・横・斜めの8通りのパターンのビットボードを事前に計算(※)しておき、パターンに一致した場合は勝利とし、すべてのマスが埋まっていた場合は引き分けとします。着手可能なマスが存在する場合はundefinedを返却します

※今回は8通りなので手計算しましたが、他のゲームにビットボードを応用する場合は事前に計算すべきパターンが膨大になることも考えられますので場合によって手段を使い分けるべきでしょう。とはいえビット演算を扱う際にはマジックナンバーを使用する場合があることも覚えておくべきです

//判定
judge() {
    const judgeBoards: number[] = [
        0x07, //横
        0x38, //横
        0x1C0, //横
        0x49, //縦
        0x92, //縦
        0x124, //縦
        0x111, //斜め
        0x54 //斜め
    ];

    for (const board of judgeBoards) {
        if ((board & this.blackStones) == board) {
            return Color.BLACK;
        }
        if ((board & this.whiteStones) == board) {
            return Color.WHITE;
        }
    }

    return (this.blackStones | this.whiteStones) == 0x1FF ? Color.SPACE : undefined;
}

以下に探索の実装例を示します

流れとしては以下のとおりです

• 勝敗を判定する
  • 勝敗が決している場合、勝敗を返す
• 着手可能位置を取得する
• 着手可能位置においてゆく
• 探索関数を再帰呼び出しする
• 探索した局面が勝ちであればすぐに返す
• そうでない場合は、勝ちの局面が見つかるもしくは着手可能位置がなくなるまでを探索する
• 引き分けor負けを返す

これらを再帰的に呼び出すことで完全に読むことができます

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

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

    let isdraw = false;
    let islose = false;
    let positionArray: {x: number, y: number}[] = new Array();
    let losePositionArray: {x: number, y: number}[] = new Array();

    //おけるマスに置いていく
    for (let i = 0; i < 9; i++) {
        if (((space >> i) & 0x01) == 0x01) {
            const x = i % 3;
            const y = Math.floor(i / 3);

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

            //再帰的に探索関数を呼び出す
            const result = search(cloneField).result;

            //もし現在の手番で勝ちならばおいた位置を結果を格納
            if (result == field.getTurn()) {
                return { position: { x: x, y: y }, result: field.getTurn() };
            }
            //もし引き分けなら引き分けフラグを立てて
            else if (result == Color.SPACE) {
                isdraw = true;

                //引き分けのときのリストに追加
                positionArray.push({x: x, y: y});
            }
            //もし負けなら負けフラグを立てて
            else{
                islose = true;
                //負けのときのリストに追加
                losePositionArray.push({x: x, y: y});
            }
        }
    }

    //引き分けもしくは負けのリストから一つ抜き出し
    const position = isdraw  ? 
        positionArray[Math.floor(Math.random() * positionArray.length)] : 
        losePositionArray[Math.floor(Math.random() * losePositionArray.length)] ;

    //結果
    const result = isdraw ? Color.SPACE : field.getTurn() == Color.BLACK ? Color.WHITE : Color.BLACK;
    return { position: position, result: result };
}

まとめ

初期盤面で探索を呼び出したところ、引き分けという結果が得られました。手元で確認できるのはとてもおもしろいので試してみてください
今回は9マスしかなく、ルールがシンプルだったので完全読みを行えましたが、オセロなど複雑なものでは探索ではなく評価が必要になってきますので、次回は評価についての記事を投稿したいと思います
読んでくださってありがとうございました