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

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

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

以下２つのステップにより，完全解析を目指します．

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？は，後手の場合確実に勝てるものになりました． 先手の場合でも，ほとんど負けないでしょう．