Hey everyone, I just have a quick, rather generic question. But I'm working on a simple connect 4 game. It will have a 2 player mode, but I would also like to make it a little more challenging for me, and add a 1 player mode in which the computer can play the game fairly 'intelligently.' My question is, I've heard of the MiniMax algorithm(haven't looked much into it) and was wondering if this was my best option for a simple game like this, or if there is something else that I might want to look into? I am using this project as a learning experience, and to add some 'tools' to my skills, so I was just hoping for some helpful advice to get started with, from someone who knows a little more than I do about this area of gaming. Thanks!

It's a pretty good choice for that game.

You'll need to limit the depth of your search, both for compute time issues and to keep the game reasonably difficult against a human.

If you generally find a winning solution 10 or so moves out, the human will stop playing because the AI is too smart.

Even better would be to match the human's skill in terms of the probability of their moves as found by your own algorithm. ... but that's more for tuning your AI.

frob.

I second Frob. Space-search methods such as minimax are ideal for turn-based games where:

-There is a limited number of possible moves

and

-It is easy to compute a 'score' for a given game state.

Plus, if you are interested into AI, that category is the first you should learn, and it is definetly a tool you should have. Good luck, and have fun!

Look into alphabeta search (it's a refinement of minimax). If you want the program to be strong, you need a good evaluation function, and you need to really know how to play the game to write one. This is a good place to start: http://homepages.cwi.nl/~tromp/c4.html

I also wrote some description of an endgame evaluation in these forums, but I can't find it.

You can also use most of the refinements of alphabeta that chess programs use: iterative deepening, history heuristic, transposition tables, depth extensions, quiescence search... But this might be too much work and your program might end up being too strong. At least you should implement iterative deepening, because it allows you to do time control.

Awesome!

Thank you guys so much. From what I had already gathered, it seemed like minimax was the way to go, I just thought that I'd get a couple opinions before digging into it.