help with recursion (connect 4)
In my programming class at school, I'm in a group and our assignment is to create a Connect 4 program. I'm in charge of handling computer AI. I did some research and found out that a MINMAX search would be best for figuring out the next move. (For the rules of Connect 4, try a Google search on it- basically you win by having four of your pieces in a row) The following is the pseudocode for the Connect 4 AI search, with credit to http://personal.vsnl.com/erwin/connect4.htm.
int Goodness(player, depth)
max = -200
for i = 1 to 7
if column i is not full
drop coin into column i
value = -Goodness(-player,depth-1) / 2
remove coin from column i
if value > max
max = value
First, let me explain it as I see it. This way, if I'm wrong, then please let me know so I can understand this search algorithm better.
The parameters are the current player (computer) and the depth of the search (so that it doesn't run for 2 weeks). For each column, it drops (temporarily) a coin into it. Then it calls itself with the parameters being the other player (the human) and depth-1. Now, the program is acting as the human and recognizes that the computer dropped a coin into every slot so it will now act on that and drop a coin into every slot (as the human), then the method recurses. The sign of "value" is flipped every time because a good move for the human is a bad move for the computer, and vice versa.
Now, here are my questions:
1. Why is "value" divided by two each time?
2. I'm thinking that this is a helper method to the real AI method. This returns the value of the best move available. But how do I know where to move? I could have a
int bestValue=Goodness(computer, 3);
but that would return some high number representing the value of the best move (I think) whereas I need a number between 0-7 so I can put a coin there (in my array). In other words, how can I use this method to figure out where the computer needs to move?
Top DevX Stories
Easy Web Services with SQL Server 2005 HTTP Endpoints
JavaOne 2005: Java Platform Roadmap Focuses on Ease of Development, Sun Focuses on the "Free" in F.O.S.S.
Wed Yourself to UML with the Power of Associations
Microsoft to Add AJAX Capabilities to ASP.NET
IBM's Cloudscape Versus MySQL