Nim Minimax

//Minimax principle implemented for the Nim game (1 row)
//by Marc Burns (C) 2009
#include <iostream>
#include <cstdlib>
#include <string>
#include <cmath>

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;	
}