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?
-- Android Development Center
-- Cloud Development Project Center
-- HTML5 Development Center
-- Windows Mobile Development Center