(Added 7/10) I’ve placed an AI that uses the complete analysis results at dobutsu-shogi.jar (17MB). Please try playing against it.
It’s a bit late, but I performed a complete analysis of Dobutsu Shogi. The method has already been published, so please refer to that for unclear points (“Complete Analysis of Dobutsu Shogi”, Tetsuro Tanaka). My implementation also references that.
The goal of the analysis is to complete an AI that, when playing as the second player, wins in exactly 78 moves, and when playing as the first player, plays moves that are hardest to lose (moves that maximize the number of moves until defeat).
The complete analysis is achieved through the following two steps:
The first step is to start from the initial position and expand all possible positions. The method is simple: just expand all legal moves from a given position. The computation takes several tens of minutes, but uses a lot of memory. Therefore, we treat positions as the same even when pieces are swapped left-right (since all piece movements are left-right symmetric), reducing the number of positions. The analysis result all-state should be sorted for future use. all-state becomes about 1 position 64bit x 246,803,167 = 1.9 GB. Code is here.
//
// q: Queue of unanalyzed positions, initial value is a queue containing only the initial position
// h: Map of analyzed positions, initial value is an empty map
// all_state: Vector of analyzed positions, initial value is an empty vector
//
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++;
// Don't analyze from finished positions
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++) {
// Properly normalize and match the player to move before saving
b = get_reverse(next_boards[j]);
b = regulate(b);
q.push_back(b);
}
}
}
}
The second step is to classify all positions in all-state as either win/loss/draw. First, classify into three types: positions that are certain wins (can definitely capture the opponent’s Lion in the next move), positions that are certain losses (not a winning position, and the opponent’s Lion is positioned in your territory with a Try determined), and all other positions. Then, analyze winning/losing positions according to the following policy. When both stop increasing, treat the remainder as draw positions and terminate the program.
- If at least one of the next positions is a losing position, then that position is a winning position
- You can win by making a move that transitions to a losing position for the opponent
- If all next positions are winning positions, then that position is a losing position
- No matter what move you make, the next position is a certain win, so the opponent wins
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) {
// Determine the win/loss of the current position from positions one move ahead
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 no more winning or losing positions increase,
// the rest are all draw positions
if (win_add_num == 0 && lose_add_num == 0) {
break;
}
}
As a result, this AI created with perfect calculations can definitely win when playing as the second player. Even when playing as the first player, it will almost never lose.