ページ

2014年2月13日木曜日

Ultimate Tic-tac-toe solution

I saw @njern is sharing his editorial("TicTacGo - An AI for Ultimate Tic-tac-toe") how to solve the problem on Ultimate-Tic-Tac-Toe, I think I can also share my experience because I could managed to get the top position in this game.

And, I actually just used simple Minimax, and pseudo code is like:

double is_win(player)
{
   double point = evaluation_function();
   if(point == 1.0 || point == 0.0 || nest_is_deep_enough){
      return point;
   }
   for(move: all possible move){
     move;
     best_move = max(best_move, 1.0 - is_win(!player));
  }
  return best_move;
}


And, for about the evaluation function, at first, I calculated each "small" square's possibility to win, assuming the sequence of player is random(so next player is 'O' with possibility 0.5, and 'X' with possibility 0.5). For about "small" square, there are only 9 spaces to fill.
So, just "int" is enough to save the space. (3^9 is enough(3 means empty, 'O', 'X'), but I used 4^9 to make it simple.). I can simply memo the result not to recalculate every time.
 Pseudo code is like below:

double evaluation_function_small_square(bool current_player, int map)
{
     if(memo[current_player][map].used){
         return memo[current_player][map];
    }
    if(win){
        return {win: 1.0; lose:0.0};
   }else if(lose){
        return {win: 0.0: lose:1.0};
   }else if(even){
       return {win: 0.0, lose:0.0};
   }
   for(player: [current_player, opposite_player]){
     for(move: possible_move){
        move player;
        (win, lost) = evaluation_function_small_square(player, map);
        if(win - lose > max_win_lose){
          max_win_lose = win - lose;
          next_win = win;
          next_lose = lose;
       }
     }
   if(player == current_player){
     win = 0.5 * next_win;
     lose = 0.5 * next_lose;
  }else{
     lose = 0.5 * next_win;
     win = 0.5 * next_lose;
  }
}

Finally, I just calculated evaluate_function() just sum up all the possibility to win(3 vertical lines, 3 horizontal lines, 2 diagonal lines.)

double evaluate_function(int large_map[3][3])
{
   for(each x, y:0..2){
     possible_win[x][y], possible_lose[x][y] = evaluation_function_small_square(player, large_map[x][y]);
   }
  /* sum up all the possibility */
   possible_win_total += possible_win[0][0] * possible_win[0][1] * possible_win[0][2] / 8.0;
   possible_lose_total += possible_lose[0][0] * possible_lose[0][1] * possible_lose[0][2] / 8.0;
   ...;
  /* special case when game is end. */
  if(possible_win[0][0] * possible_win[0][1] * possible_win[0][2] == 1.0){
     possible_win_total = 1.0; possible_lose_total = 0.0;
  }
  if(possible_win[0][0] * possible_win[0][1] * possible_win[0][2] == 0.0){
     possible_win_total = 0.0; possible_lose_total = 1.0;
  }
  ...
}

I could actually use inclusive-exclusive set theory to calculate more accurate possibility. But, it also takes some time(to calculate 2^8 patterns)...

Basically, that's it !
Have fun !