What wkiffer just described is pretty much minimax.
Quote:
you could, if you wanted to here put in more in depth AI to try and "trap" the opponent by getting in one of those situations where you can win two different ways but for the sake of simplicity I'm going to just pick the best move available.
It would be easier to "trap" the opponent, as you put it, since the AI doesn't know anything about how many moves away from the root we are. If we search 3 moves ahead and there happens to be a win on the third move, the AI will return that move, regardless of whether or not we can win on this turn. If we do take the move number into account, you can force the AI to pick the "immediate win" move.
Here is a simple Tic-Tac-Toe engine I wrote about 10 months ago or so (maybe it will help, I don't know):
#ifndef _TTT_H_#define _TTT_H_enum Player{ O=1, X=2, empty=4};enum{ PLAYING=1, C_WIN=2, H_WIN=4, DRAW=8};static const int lines[24]={ 0,1,2, 3,4,5, 6,7,8, 0,3,6, 1,4,7, 2,5,8, 0,4,8, 2,4,6};struct Board{ Player board[9]; Board(){ for(int i=0;i<9;++i) board=empty; } bool check_for_win(Player p){ for(int i=1,d=0;i<=24;++i){ if(board[lines[i-1]]&p){ if(!(++d%3)) return true; } else d=0; if(!(i%3)) d=0; } return false; } int state(){ if(check_for_win(X)) return C_WIN; if(check_for_win(O)) return H_WIN; for(int i=0;i<9;++i) if(board∅) return PLAYING; return DRAW; } int think(int depth,Player p){ int best=-100,alpha=-100,beta=+100,eval=-100,m; for(int i=0;i<9;++i){ if(board∅){ board=p; eval=-alphabeta(-beta,-alpha,depth-1,p&O?X:O); board=empty; if(alpha<eval){ alpha=eval; m=i; } } } return m; } int alphabeta(int alpha,int beta,int depth,Player p){ switch(state()){ case C_WIN: return p&O?-100:+100; case H_WIN: return p&O?+100:-100; case DRAW: return 0; } if(depth<=0) return 0; int best=-100,eval=-100; for(int i=0;i<9;++i){ if(board∅){ board=p; eval=-alphabeta(-beta,-alpha,depth-1,p&O?X:O); board=empty; if(alpha<eval){ alpha=eval; if(alpha>=beta) break; } } } return alpha; }};#endif
[edit]: Ooops! That is not a good example, since it uses a variation of the minimax algorithm called AlphaBeta. Here is another example that actually uses minimax (it also makes use of bitboards, so just ask if there is something needed explaining):
ttt.h#ifndef _TTT_H_#define _TTT_H_#include <iostream>using namespace std;#define O 0#define X 1#define HWIN 1#define CWIN 2#define DRAW 4#define PLAYING 8struct Board{ short m_bits[2]; unsigned move_number; Board():move_number(0){clear_board();} void clear_board(){m_bits[O]=m_bits[X]=0;} void place(int s,int c){ m_bits[c]|=1<<s; ++move_number; } void remove(int s,int c){ m_bits[c]^=1<<s; --move_number; } int state();};ostream& operator<<(ostream &o,Board const &b);#endif
#include "ttt.h"int Board::state(){ static const short wins[]={ 0x007,0x038,0x1C0,0x049, 0x092,0x124,0x111,0x054 }; for(int i=0;i<8;++i){ if((m_bits[O]&wins) == wins) return HWIN; if((m_bits[X]&wins) == wins) return CWIN; } if((m_bits[O]|m_bits[X]) == 0x1FF) return DRAW; return PLAYING;}ostream& operator<<(ostream &o,Board const &b){ for(int i=0;i<9;++i){ if(b.m_bits[X] & 1<<i) o<<'x'; else if(b.m_bits[O] & 1<<i) o<<'o'; else o<<'-'; if((i+1)%3==0) o<<"\n"; } return o;}
#ifndef _SEARCH_H_#define _SEARCH_H_#include "ttt.h"int think(Board&,int,int);int minimax(Board&,int,int);#endif
#include "search.h"int think(Board &b,int stm,int depth){ int best=-100,val; int best_move=-1; for(int i=0;i<9;++i){ if((b.m_bits[O]|b.m_bits[X]) & 1<<i) continue; b.place(i,stm); val=-minimax(b,stm^1,depth-1); b.remove(i,stm); if(val>best){ best=val; best_move=i; } } return best_move;}int minimax(Board &b,int stm,int depth){ switch(b.state()){ case HWIN: return stm?-100+b.move_number:+100-b.move_number; case CWIN: return stm?+100-b.move_number:-100+b.move_number; case DRAW: return 0; } if(depth<=0) return 0; int best=-100,val; for(int i=0;i<9;++i){ if((b.m_bits[O]|b.m_bits[X]) & 1<<i) continue; b.place(i,stm); val=-minimax(b,stm^1,depth-1); b.remove(i,stm); if(val>best) best=val; } return best;}
#include "search.h"#define INFO_AUTHOR "Tic Tac Toe - Bitboard Version, by Tom Cant\n\n"int main(){ Board b; cout<<INFO_AUTHOR; cout<<b<<endl; int s; while(b.state()&PLAYING){ cin>>s; b.place(s-1,O); cout<<b<<endl; b.place(think(b,X,9),X); cout<<b<<endl; } cin.ignore(); cin.get();}
