AOJ - TICTACTOE

AOJ - TICTACTOE

단순한 완전탐색 문제이고, 게임이론 문제의 기본이다.

현재 보드판을 보고 누구의 턴인지 알 수 있다.

• 1 N-position
• 0 Draw
• -1 P-position

으로 두고 풀면, 게임이 3줄이 만들어져 끝난 상태엔 -1을 반환하면 된다. 왜냐면 마지막으로 둔 사람이 이겼을 것이기 때문에 지금 둘 사람은 항상 지기 때문이다.

이제 더 못둔다면 0을 반환하면 된다.

그렇지 않다면 모든 둘 수 있는 곳에 둬보고

1. -1(P-position)을 반환하는 자리가 있으면 거기에 둬서 항상 이길 수 있으므로 1을 반환
2. -1이 하나도 없지만 0을 하나라도 반환하면 적어도 비길 수 있다는 뜻이므로 0을 반환
3. 그 외엔 1(N-position)을 반환한다.

void solve() {  
   vs b(3);  
   fv(b);  
  
   auto who = [&]() {  
      int s = 0;  
      for (int y = 0; y < 3; y++) for (int x = 0; x < 3; x++) if (b[y][x] == '.')s++;  
      if (s == 0)return 0;  
      if (s & 1) return 1;  
      return -1;  
   };  
  
   function<int()> fn = [&]() -> int {  
      int w = who();  
  
      for (int y = 0; y < 3; y++) {  
         if (b[y][0] != '.' && b[y][0] == b[y][1] && b[y][1] == b[y][2]) return -1;  
         if (b[0][y] != '.' && b[0][y] == b[1][y] && b[1][y] == b[2][y]) return -1;  
      }  
      if (b[0][0] != '.' && b[0][0] == b[1][1] && b[1][1] == b[2][2]) return -1;  
      if (b[0][2] != '.' && b[0][2] == b[1][1] && b[1][1] == b[2][0]) return -1;  
  
      if (!w) {  
         return 0;  
      }  
  
      int win = 0;  
      int lose = 0;  
      int draw = 0;  
      for (int y = 0; y < 3; y++)  
         for (int x = 0; x < 3; x++)  
            if (b[y][x] == '.') {  
               b[y][x] = w == 1 ? 'x' : 'o';  
               int r = fn();  
               if (r == 0) draw++;  
               if (r == 1) win++;  
               if (r == -1) lose++;  
               b[y][x] = '.';  
            }  
      if (lose) return 1;  
      if (!draw) return -1;  
      return 0;  
   };  
   int ret = fn();  
   int w = who();  
   if (!w || ret == 0) cout << "TIE\n";  
   else if (ret == 1 && w == 1) cout << "x\n";  
   else cout << "o\n";  
}