fork(3) download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <list>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. enum state { PLAYING, XWIN, OWIN, DRAW };
  9.  
  10. constexpr const int infinity = 10;
  11.  
  12. state checkWin(const int (&gameBoard)[9])
  13. {
  14.     for (int i = 0; i != 3; ++i) {
  15.         if (gameBoard[0 + 3 * i] + gameBoard[1 + 3 * i] + gameBoard[2 + 3 * i] == 3) {
  16.             return XWIN;
  17.         } else if (gameBoard[0 + 3 * i] + gameBoard[1 + 3 * i] + gameBoard[2 + 3 * i] == -3) {
  18.             return OWIN;
  19.         }
  20.         if (gameBoard[0 + i] + gameBoard[3 + i] + gameBoard[6 + i] == 3) {
  21.             return XWIN;
  22.         } else if (gameBoard[0 + i] + gameBoard[3 + i] + gameBoard[6 + i] == -3) {
  23.             return OWIN;
  24.         }
  25.     }
  26.     if (gameBoard[0] + gameBoard[4] + gameBoard[8] == 3
  27.         || gameBoard[2] + gameBoard[4] + gameBoard[6] == 3) {
  28.         return XWIN;
  29.     }
  30.     if (gameBoard[0] + gameBoard[4] + gameBoard[8] == -3
  31.         || gameBoard[2] + gameBoard[4] + gameBoard[6] == -3) {
  32.         return OWIN;
  33.     }
  34.     if (std::find(gameBoard, gameBoard + 9, 0) != gameBoard + 9) {
  35.         return PLAYING;
  36.     }
  37.     return DRAW;
  38. }
  39.  
  40. void generate_moves(const int (&gameBoard)[9], list<int> &moves)
  41. {
  42.     for (int i = 0; i < 9; i++) {
  43.         if (gameBoard[i] == 0) {
  44.             moves.push_back(i);
  45.         }
  46.     }
  47. }
  48.  
  49. int evaluate_position(const int (&gameBoard)[9], int playerTurn)
  50. {
  51.     state currentGameState = checkWin(gameBoard);
  52.     if (currentGameState != PLAYING) {
  53.         if ((playerTurn == 1 && currentGameState == XWIN) || (playerTurn == -1 && currentGameState == OWIN))
  54.             return +infinity;
  55.         else if ((playerTurn == -1 && currentGameState == XWIN) || (playerTurn == 1 && currentGameState == OWIN))
  56.             return -infinity;
  57.         else if (currentGameState == DRAW)
  58.             return 0;
  59.     }
  60.     return -1;
  61. }
  62.  
  63. int MaxMove(int (&gameBoard)[9], int playerTurn)
  64. {
  65.     int pos_val = evaluate_position(gameBoard, playerTurn);
  66.     if (pos_val != -1) return pos_val;
  67.  
  68.     int bestScore = -infinity;
  69.     list<int> movesList;
  70.     generate_moves(gameBoard, movesList);
  71.  
  72.     while (!movesList.empty()) {
  73.         gameBoard[movesList.front()] = playerTurn;
  74.         int score = -MaxMove(gameBoard, -playerTurn);
  75.         if (score > bestScore) {
  76.             bestScore = score;
  77.         }
  78.         gameBoard[movesList.front()] = 0;
  79.         movesList.pop_front();
  80.     }
  81.     return bestScore;
  82. }
  83.  
  84. int MiniMax(int (&gameBoard)[9], int playerTurn)
  85. {
  86.     int bestScore = -infinity;
  87.     list<int> movesList;
  88.     vector<int> bestMoves;
  89.     generate_moves(gameBoard, movesList);
  90.  
  91.     while (!movesList.empty()) {
  92.         gameBoard[movesList.front()] = playerTurn;
  93.         int score = -MaxMove(gameBoard, -playerTurn);
  94.         if (score > bestScore) {
  95.             bestScore = score;
  96.             bestMoves.clear();
  97.             bestMoves.push_back(movesList.front());
  98.         } else if (score == bestScore) {
  99.             bestMoves.push_back(movesList.front());
  100.         }
  101.         gameBoard[movesList.front()] = 0;
  102.         movesList.pop_front();
  103.     }
  104.  
  105. #if 0
  106.     int index = bestMoves.size();
  107.     if (index > 0) {
  108.         time_t secs;
  109.         time(&secs);
  110.         srand((uint32_t)secs);
  111.         index = rand() % index;
  112.     }
  113.     return bestMoves[index];
  114. #else
  115.     return bestMoves.front();
  116. #endif
  117. }
  118.  
  119. void print(const int (&gameBoard)[9])
  120. {
  121.     const char cs[] = {'O', '.', 'X'};
  122.  
  123.     std::cout << "--------" << std::endl;
  124.     for (int i = 0; i != 3; ++i) {
  125.         for (int j = 0; j != 3; ++j) {
  126.             std::cout << cs[1 + gameBoard[3 * i + j]];
  127.         }
  128.         std::cout << std::endl;
  129.     }
  130. }
  131.  
  132. int main()
  133. {
  134.     int gameBoard[9] {};
  135.  
  136.     int player = 1;
  137.     while (checkWin(gameBoard) == PLAYING) {
  138.         gameBoard[MiniMax(gameBoard, player)] = player;
  139.         print(gameBoard);
  140.         player *= -1;
  141.     }
  142.     return 0;
  143. }
  144.  
Success #stdin #stdout 0.08s 3432KB
comments ()
stdin 
Standard input is empty
stdout 
--------
X..
...
...
--------
X..
.O.
...
--------
XX.
.O.
...
--------
XXO
.O.
...
--------
XXO
.O.
X..
--------
XXO
OO.
X..
--------
XXO
OOX
X..
--------
XXO
OOX
XO.
--------
XXO
OOX
XOX
https://ideone.com/Ihy1SR
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!