Jason Robers

Great- I really appreciate all the help, it's starting to turn the wheels in my head. A question popped up though: how do I keep from getting multiple entries of the same solution? For example, using Corey's output, let's say queen #1 is at (7,0), queen #2 is at (1,4), etc. What stops me from printing the solution queen #1 at (1,4), queen #2 at (7,0), and all the rest the same?

Jeff- yes and no: this is an undergrad assignment but there's no lab with it; it was just thrown out there as a project that we need to do ourselves. There really isn't a "set" algorithm I was looking for, just wondering if there is one that I can use.

Corey- so far that's the only thing I can come up with. I just don't know how long that would take...

Before I start, I have to say that last time I came here for help, I received LOTS of useful information that helped me solve my recursion problems and earn a great grade on my group project. This time I'm back with another recursion problem that is a spin-off of the non-attacking queens problem.

You all might be familiar with the non-attacking queens in which you use recursion to place N queens on an NxN board. The trick is the queens can't be attacking each other. Well, my problem is similiar yet different. In the project specs, it says the number of queens I will have in my solution is 5. Also, I will be using a fixed 8 x 8 board. I have to use recursion to place my 5 queens so that ALL the spaces are covered. By this, it means that between the 5 queens, each space on the board is either occupied or can be attacked. The project specs also say that there are 728 total solutions, which include rotating the board, and that equals out to 182 solutions per side.

Here's what I have so far: I will use a double-scripted array of ints to represent the board and queens. The board starts off as all 0's, each queen is a 2, and any space that can be attacked gets set to a 1. In the end, if the whole board doesn't have a 0 in it, then I print the coordinates of each queen and reset for the next solution. The representation details are ok; it's just the implementation that I'm having trouble with. Is there an algorithm that I should use to place queens?

Any help/contribution on this topic is greatly appreciated.

David-

Ah, it all makes sense now. I did some println statements with value and max changing and I'm able to understand it better now.

As for returning the move, I kinda took the easy way out and added a global int initialized to -1. Whenever value>max, max=value and said int changes to x (the counter of columns). It works fine, I just found one problem with it. The teacher showed me his grading algorithm and it goes like this:

Start 1 player game.
Set recursion depth to 4.
Human drops coin into column 4. (columns 0-6)
Computer drops into column 0. //column 0's value is greater than max so the global int is changed to 0, no other columns' value can beat it so it stays 0
Human drops into column 3.
This should register with the AI that I can win in two more moves so it should begin to block me. The problem is, his algorithm has the computer drop into column 2 (block), whereas mine drops into column 5 (same block). I looked again at my code and noticed that column 2 and column 5 should have the same value. Do you know what could be wrong here?

edit: should be (columns 0-6)
[ November 10, 2004: Message edited by: Jason Robers ]

David-

I looked at your code and it makes a little bit more sense than what I posted. I rewrote the pseudocode below using the requirements of the teacher that were handed out today (he says that everybody's AI algorithm must be the same so he can test fairly). This is what I got.

public int goodValue(int player, int depth) { if (isWinner(getOtherPlayer(player)) return -128; if(depth==0) return 0; //the above two if statements are what's in the teacher's AI pseudocode int max=-200; for(int c=0; c<7; c++) //all columns { if(!isColumnFull(c)) { makeMove(c); int value= -goodValue(getOtherPlayer(player), depth-1)/2 //the above line seems to me like he wants the opposite sign of goodValue, divided by 2, also required takeBackMove(c); if(value>max) max=value; } } return max; }

I can understand your code, but something about his doesn't quite click with me. Can you help me with that? For example, in your code, you send player to an evaluation method whereas in his code, the evaluation process is somewhat fuzzy to me.
[ November 08, 2004: Message edited by: Jason Robers ]

Hello all-

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)
{
if CheckWin(-player)
return -128
if depth=0
return 0

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
}
return max
}

First, I'll try to 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?