I'm trying to write an AI that plays a game perfectly. The game is real simple. Players take turns adding 1 or 2. The player to reach 10 wins. I read about Minimax and I understand it perfectly well. Unfortunately I'm an inexperienced programmer and am having real trouble implementing this. I want a function that returns 1 or 2 (refering to which move to make). My function has basically zero functionality. I'm sure this is filled with huge gaping logic errors. Any help would be appreciated. I am probably doing some parts of it too complicated and other parts not complicated enough. I am probably returning bad data types and sending the wrong datatypes to functions.. and I'm probably visualizing the way the recursion flows totally wrong. If anyone can give me some tips on how to fix this code, I would appreciate it greatly. (Note: the current score is stored in a session variable) (and $move is a bool that goes back between 0 and 1 at each stage of min, max, etc. to keep track of who's move it is at that point in the game tree.. again probably something unecessary or if necessary, implemented completely wrong) $x = new game; $x->best_move=0; $x->sum=$_SESSION['score']; $x->move=1; $_SESSION['score'] += MinMax($x)->best_move; class game { var $sum; var $move; var $bestmove; } function MinMax (game $x) { return Maxx($x); } function Maxx (game $x) { if ($x->sum==10) return $x; else { $x->move = 1 - $x->move; $x->sum += 1; $value1 = Value(Minn($x)); $x->sum += 1; $value2 = Value(Minn($x)); if($value1>=$value2) { $x->best_move=1; $x->sum -= 1; } else $x->best_move=2; return $x; } } function Minn (game $x) { if ($x->sum==10) return $x; else { $x->move = 1 - $x->move; $x->sum += 1; $value1 = Value(Maxx($x)); $x->sum += 1; $value2 = Value(Maxx($x)); if($value1>=$value2) { $x->best_move=1; $x->sum -= 1; } else $x->best_move=2; return $x; } } function Value(game $x) { if ($x->move) return 1; if (!$x->move) return -1; } NOTE: sorry for the PHP code, i can retype it in c style if anybody needs. this is a web-based game.. i omited some of the php code.. like the form that takes the user's move, and the display of the current score and the win messages

think() below is the function you asked for.

int negamax(int p){  if(p>=10)    return -1000;  int best_score=-2000;  for(int m=1;m<3;++m){    int v=-negamax(p+m);    if(best_score<v)      best_score=v;  }  return best_score;}int think(int p){  int best_score=-2000;  int best_move=0;  for(int m=1;m<3;++m){    int v=-negamax(p+m);    if(best_score<v){      best_score=v;      best_move=m;    }  }  return best_move;}

It worked perfectly. Though I'm bummed I couldn't get it working myself but I'm hoping to analyze yours enough so i can modify it to minimax (just slightly different from negamax).

Not because I care if it's minimax or negamax.. just so I can know I understood your solution and exactly why mine didn't work.

Thanks a million for the quick reply and the awesome help.

Bottom line is, I can easily convert this to do analysis for other games too. My ultimate goal is to make a chess engine but I want to do some expirimenting with simpler games first.

My next step is to find or invent some game that is slightly more complex than this... Hopefully a given position will have a variable amount of moves and the end position wont' be so easy to score.. and there will be a cutof depth.

After that I plan to bump it up to alpha-beta pruning, then move even further to negascout and mtd(f). Etc.

I also will be on the lookout for some algorithms for testing if positions are equivelant to other positions on a board given some rotation, translation, reflection etc.

Thanks again!

I would recommend you tackle Connect four next. It needs a meaningful evaluation function (look for threats on odd-numbered rows is probably a good start), the game can end early, the number of moves is variable, and it is fun to play too!

Post again if you need help with anything.