//Minimax principle implemented for the Nim game (1 row) //by Marc Burns (C) 2009 #include #include #include #include using namespace std; int user_simulate(int remain, int take, int depth=1); //0 is returned on computer loss or invalid move //depth is returned on user loss in a valid move. //Goal is to find the shortest path to a computer win //given the initial remain and take parameters. int comp_simulate(int remain, int take, int depth=1) { if(remain == 1) //computer lost at this point { return 0; } if(take >= remain) //can not play return 0; //return min. path depth return min(user_simulate(remain-take, 1, depth+1), min(user_simulate(remain-take, 2, depth+1), user_simulate(remain-take, 3, depth+1))); } int user_simulate(int remain, int take, int depth) { if(remain == 1) //user lost at this point return depth; //the lowest nonzero value returned is selected by mutual recursion if(take >= remain) //can not play return 0; //effectively return nonzero depth return max(comp_simulate(remain-take, 1, depth+1), max(comp_simulate(remain-take, 2, depth+1), comp_simulate(remain-take, 3, depth+1))); } void compvcomp(int num_matches) { int turn = 1; while(num_matches > 1) { cout << num_matches << " matches remain: "; turn = 1 - turn; int m = 1; int v1 = comp_simulate(num_matches, 1); //returns depth of closest win int v2 = comp_simulate(num_matches, 2); //for each possible choice. int v3 = comp_simulate(num_matches, 3); //choose path with least chance of loss int abmax = max(v1,max(v2,v3))+1; if(v1 == 0) v1 = abmax; //convert 0 paths (no chances win) into if(v2 == 0) v2 = abmax; //paths of greatest depth (least preference). if(v3 == 0) v3 = abmax; if(v3 <= v1 && v3 <= v2) //find path of least depth m = 3; if(v2 <= v1 && v2 <= v3) m = 2; if(v1 <= v2 && v1 <= v3) m = 1; if(m >= num_matches) //this should never happen { cout << "Minimax error: want = " << m << "\n"; continue; } num_matches -= m; cout << "Computer " << ((turn==0)?'A':'B') << " takes " << m << " matches.\n"; } if(turn == 0) cout << "Computer A wins.\n"; else cout << "Computer B wins.\n"; } int main() { string buf; //for various input ops int num_matches = 0; //number of matches to play while(num_matches <= 0) { cout << "How many matches should be used to play? "; getline(cin, buf); num_matches = atoi(buf.c_str()); } cout << "Would you like to play [I]nteractively or [O]bserve? "; getline(cin, buf); if((buf.c_str()[0] | 32) == 'o') { compvcomp(num_matches); return 0; } int turn = 1; //0=user, 1=computer cout << "Should the [U]ser or [C]omputer move first? "; getline(cin, buf); if((buf.c_str()[0] | 32) == 'c') turn = 0; //turn is negated in game loop, so use opposite value. while(num_matches > 1) { turn = 1 - turn; //negate turn if(turn == 0) cout << "User's turn: "; else cout << "Computer's turn: "; cout << num_matches << " matches remain.\n"; if(turn == 0) { int m = 0; while(m <= 0 || m > 3) { cout << "How many matches will you remove? (1-3) "; getline(cin, buf); m = atoi(buf.c_str()); if(m >= num_matches) m = 0; } num_matches -= m; } else { int m = 1; int v1 = comp_simulate(num_matches, 1); //returns depth of closest win int v2 = comp_simulate(num_matches, 2); //for each possible choice. int v3 = comp_simulate(num_matches, 3); //choose path with least chance of loss int abmax = max(v1,max(v2,v3))+1; if(v1 == 0) v1 = abmax; //convert 0 paths (no chances win) into if(v2 == 0) v2 = abmax; //paths of greatest depth (least preference). if(v3 == 0) v3 = abmax; if(v3 <= v1 && v3 <= v2) //find path of least depth m = 3; if(v2 <= v1 && v2 <= v3) m = 2; if(v1 <= v2 && v1 <= v3) m = 1; if(m >= num_matches) //this should never happen { cout << "Minimax error: want = " << m << "\n"; continue; } num_matches -= m; cout << "Computer takes " << m << " matches.\n"; } cout << "\n"; } if(turn == 0) cout << "User wins.\n"; else cout << "Computer wins.\n"; return 0; }