fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. map<int,pair<int,int> > Mp;
  5. map<int,int> nex;
  6. // -1 for O, 1 for x, 0 for empty
  7.  
  8. bool winning(int a[3][3], int type){
  9.     //check hor rows
  10.     for (int i=0; i<3; i++){
  11.         bool res = true;
  12.         for (int j=0; j<3; j++){
  13.             if (a[i][j]!=type){
  14.                 res = false; break;
  15.             }
  16.         }
  17.         if (res) {return true;}
  18.     }
  19.     //check ver cols
  20.     for (int i=0; i<3; i++){
  21.         bool res = true;
  22.         for (int j=0; j<3; j++){
  23.             if (a[j][i]!=type){
  24.                 res = false; break;
  25.             }
  26.         }
  27.         if (res) {return true;}
  28.     }
  29.     //check two dias
  30.     bool left = true;
  31.     bool right = true;
  32.     for (int i=0; i<3; i++){
  33.         if (a[i][i]!=type){left = false;}
  34.         if (a[i][2-i]!=type){right = false;}
  35.     }
  36.     return (left|right);
  37. }
  38.  
  39. bool draw(int a[3][3], int type){
  40.     for (int i=0; i<3; i++){
  41.         for (int j=0; j<3; j++){
  42.             if (a[i][j]==0){return false;}
  43.         }
  44.     }
  45.     return (!winning(a,type));
  46. }
  47.  
  48. bool losing(int a[3][3], int type){
  49.     return winning(a,nex[type]);
  50. }
  51.  
  52. int getnew(int a[3][3], int na[3][3], int tomove, int id){
  53.     for (int i=0; i<3; i++){
  54.         for (int j=0; j<3; j++){
  55.             na[i][j] = a[i][j];
  56.         }
  57.     }
  58.     pair<int,int> xy = Mp[id];
  59.     int xi = xy.first, yj = xy.second;
  60.     if (na[xi][yj]!=0){return false;}
  61.     na[xi][yj] = tomove;
  62.     return true;
  63. }
  64.  
  65. bool print(int a[3][3]){
  66.     for (int i=0; i<3; i++){
  67.         for (int j=0; j<3; j++){
  68.             cout<<a[i][j]<<" ";
  69.         }
  70.         cout<<"\n";
  71.     }
  72.     return true;
  73. }
  74.  
  75. ///1 for win, 0 for draw, -1 for loss
  76. int nodes;
  77.  
  78. pair<int,int> findmove(int a[3][3], int tomove){
  79.     nodes++;
  80.     if (winning(a,-1)){
  81.         return make_pair(1,-1);
  82.     }
  83.     if (losing(a,-1)){
  84.         return make_pair(-1,-1);
  85.     }
  86.     if (draw(a,-1)){
  87.         return make_pair(0,-1);
  88.     }
  89.  
  90.     int best = -1;
  91.     int nbest = -1;
  92.     int gstat = -1;
  93.     if (tomove==1){
  94.         gstat = 1;
  95.     }
  96.     for (int i=0; i<9; i++){
  97.         int na[3][3];
  98.         int flag = getnew(a,na,tomove,i);
  99.         if (flag==0){continue;}
  100.         pair<int,int> getstatus = findmove(na, nex[tomove]);
  101.         int status = getstatus.first;
  102.  
  103.         if (status==1){
  104.             if (tomove==-1){
  105.                 best = i;
  106.                 gstat = 1;
  107.             }
  108.             continue;
  109.         }
  110.         if (status==0){
  111.             if (tomove==-1){
  112.                 if (nbest==-1){
  113.                     nbest = i;
  114.                 }
  115.                 if (gstat<0){
  116.                     gstat = 0;
  117.                 }
  118.             }
  119.             if (tomove==1){
  120.                 if (gstat>0){
  121.                     gstat = 0;
  122.                 }
  123.             }
  124.             continue;
  125.         }
  126.         if (status==-1){
  127.             if (tomove==1){
  128.                 gstat = -1;
  129.             }
  130.             continue;
  131.         }
  132.     }
  133.     if (gstat==1){
  134.         return make_pair(1,best);
  135.     }
  136.     if (gstat==0){
  137.         if (best!=-1){
  138.             nbest = best;
  139.         }
  140.         return make_pair(0,nbest);
  141.     }
  142.     return make_pair(-1,-1);
  143. }
  144.  
  145. int main(){
  146.     //freopen("in.txt","r",stdin);
  147.     //freopen("out.txt","w",stdout);
  148.     nex[-1] = 1;
  149.     nex[1] = -1;
  150.     pair<int,int> p;
  151.     for (int i=0; i<9; i++){
  152.         p.first = i/3;
  153.         p.second = i%3;
  154.         Mp[i] = p;
  155.     }
  156.     int a[3][3];
  157.     for (int i=0; i<3; i++){
  158.         for (int j=0; j<3; j++){
  159.             cin>>a[i][j];
  160.         }
  161.     }
  162.     cout<<"Current board\n";
  163.     print(a);
  164.     p = findmove(a,-1);
  165.     cout<<"Minimax returns "<<p.first<<" "<<p.second<<endl;
  166.     if (p.first==-1){cout<<"AI resigns, all moves are losing\n"; return 0;}
  167.     if (p.first==1){cout<<"AI thinks that it will win\n";}
  168.     if (p.first==0){cout<<"AI thinks that it will be draw if played optimally\n";}
  169.     p = Mp[p.second];
  170.     a[p.first][p.second] = -1;
  171.     cout<<"Nodes scanned = "<<nodes<<"\n";
  172.     nodes = 0;
  173.     cout<<"Board after AI move\n";
  174.     print(a);
  175. }
  176.  
Success #stdin #stdout 0s 3284KB
comments (?)
stdin
copy 
1 1 0
0 -1 0 
0 0 0
stdout
copy 
Current board
1 1 0 
0 -1 0 
0 0 0 
Minimax returns 0 2
AI thinks that it will be draw if played optimally
Nodes scanned = 935
Board after AI move
1 1 -1 
0 -1 0 
0 0 0
https://ideone.com/mgSE5s
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!