bobuhiro11's diary

どうぶつしょうぎの完全解析

28 May 2015
[shougi]

(7/10追記) 完全解析の結果を利用するAIをdobutsu-shogi.jar(17MB)に置いておきます.対戦してみてください.

今更な感じですが,どうぶつしょうぎの完全解析をしてみました. やり方はすでに公開されてますので,不明点はそちらを参考にしてください(「どうぶつしょうぎの完全解析」, 田中哲朗). 私の実装もそちらを参考にしています.

解析のゴールは,後手の場合は78手で確実に勝ち,先手の場合は出来るだけ負けにくい手(負けまでの手数が最も長い手)を指すAIを完成させることです.

以下2つのステップにより,完全解析を目指します.

1つ目は,初期局面から開始し,ありうる全ての局面を展開することです. やり方は単純で,ある局面の合法手を全て展開していくだけです. 計算時間は数十分程度ですか,メモリを多く使います. そこで,駒を左右入れ替えて配置し直しても同じ局面と見なし(全ての駒の動きは左右対称であるから),局面数を減らします. 解析結果all-stateは,今後の利用のためソーティングしておくと良いです. all-stateは,1局面64bit x 246,803,167 = 1.9 GBくらいになります. コードはこちら.

    //
    // q: 未解析局面のキュー,初期値は初期局面のみが格納されたキュー
    // h: 解析済み局面のマップ,初期値は空マップ
    // all_state: 解析済み局面のベクタ,初期値は空ベクタ
    //
    while(!q.empty()) {
        if (i>=MAX_BOARD_NUM) {
            break;
        }
        b = q.front(); q.pop_front();
        iter = h.find(b);

        if (iter == h.end()) {
            all_state.push_back(b);
            h.insert(b);
            i++;
            // 終わった盤面からは解析しない
            if (!is_win_state(b) && !is_lose_state(b)) {

                next_boards.clear();
                get_next_board(next_boards, b);
                n = next_boards.size();

                for (j=0; j<n; j++) {
                    // ちゃんと正規化して,手番を合わせて保存
                    b = get_reverse(next_boards[j]);
                    b = regulate(b);
                    q.push_back(b);
                }
            }
        }
    }

2つ目は,全ての局面all-stateを勝ち/負け/引き分けのどれかに分類することです. まず,勝ち確定局面(次の一手で確実に相手のライオンが取れる),負け確定局面(勝ち局面ではなく,相手のライオンが自陣に位置しトライが決まった),それ以外の局面の3種類に分類します. あとは,以下の方針で,勝ち局面/負け局面を解析していきます. どちらも増えなくなれば,残りを引き分け局面とし,プログラムを終了します.

  1. 次の局面の内少なくとも一つが負け局面であれば,その局面は勝ち局面
    • 次の局面が負け局面に移行するように打てば勝てる
  2. 次の局面が全て勝ち局面であれば,その局面は負け局面
    • どのような手を打っても,次の局面は勝ち確定だから相手が勝つことになる

コードはこちら.

for(;;) {
    unsigned int win_add_num = 0;
    unsigned int lose_add_num = 0;

    for (size_t i=0; i<STATE_NUM; i++) {
        board b = all_state[i];
        if (judge[i] == UNKNOWN) {

            // 一手先の局面から現在の局面の勝敗を判定
            unsigned char winorlose = get_winorlose(b, all_state, judge);

            if (winorlose == WIN) {
                judge[i] = WIN;
                judge_count[i] = iter_num;
                win_add_num++;
            } else if(winorlose == LOSE) {
                judge[i] = LOSE;
                judge_count[i] = iter_num;
                lose_add_num++;
            }

        }
    }

    // これ以上勝ち確定も負け局面も増えなければ,
    // 残りは全て引き分け局面
    if (win_add_num == 0 && lose_add_num == 0) {
        break;
    }
}

結果として,カンペキな計算で作られたこのAI?は,後手の場合確実に勝てるものになりました. 先手の場合でも,ほとんど負けないでしょう.


comments powered by Disqus < 4clojureのススメ 5五将棋 AI制作のメモ >