public static int Evalc(int board[], boolean turn)
{
int player = 0;
int eval = 0;
int points = 0;
int row;
int sq;
int column;
int posn[][] = new int[6][7];
for (sq = 0; sq < 42; sq++)
{
posn[sq / 7][sq % 7] = board[sq];
}
if (turn == true)
{
player = 1;
} else
{
player = 2;
}
for (row = 0; row < rows; row++)
{
for (column = 0; column < cols - 3; column++)
{
if (posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] &&
posn[row][column] == posn[row][column + 3])
{
eval = -1000;
}
}
}
// check for a vertical win
for (row = 0; row < rows - 3; row++)
{
for (column = 0; column < cols; column++)
{
if (posn[row][column] != 0 &&
posn[row][column] == posn[row + 1][column] &&
posn[row][column] == posn[row + 2][column] &&
posn[row][column] == posn[row + 3][column])
{
eval = -1000;
}
}
}
// check for a diagonal win (positive slope)
for (row = 0; row < rows - 3; row++)
{
for (column = 0; column < cols - 3; column++)
{
if (posn[row][column] != 0 &&
posn[row][column] == posn[row + 1][column + 1] &&
posn[row][column] == posn[row + 2][column + 2] &&
posn[row][column] == posn[row + 3][column + 3])
{
eval = -1000;
}
}
}
// check for a diagonal win (negative slope)
for (row = rows - 3; row < rows; row++)
{
for (column = 0; column < cols - 3; column++)
{
if (posn[row][column] != 0 &&
posn[row][column] == posn[row - 1][column + 1] &&
posn[row][column] == posn[row - 2][column + 2] &&
posn[row][column] == posn[row - 3][column + 3])
{
eval = -1000;
}
}
}
// System.out.print(eval);
if (player == 1)
{
for (column = 0; column < cols - 2; column++)
{
for (row = 0; row < rows; row++)
{
if (row % 2 != 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 1)
{
points = -5000;
}
if (row % 2 == 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 2)
{
points = 5000;
}
}
}
}
// check for a vertical win
for (row = 1; row <= rows - 2; row++)
{
for (column = 0; column < cols - 2; column++)
{
if (row % 2 != 0 && posn[row - 1][column] != 0 &&
posn[row - 1][column] == posn[row - 1][column + 1] &&
posn[row - 1][column] == posn[row - 1][column + 2] && posn[row - 1][column] == 1)
{
points = -5000;
}
if (row % 2 == 0 && posn[row - 1][column] != 0 &&
posn[row - 1][column] == posn[row - 1][column + 1] &&
posn[row - 1][column] == posn[row - 1][column + 2] && posn[row - 1][column] == 2)
{
points = 5000;
}
}
}
// check for a diagonal win (positive slope)
for (row = 0; row < rows - 2; row++)
{
for (column = 0; column < cols - 2; column++)
{
if (row % 2 != 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 1)
{
points = -5000;
}
if (row % 2 == 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 2)
{
points = 5000;
}
}
}
// check for a diagonal win (negative slope)
for (row = rows - 3; row < rows && row % 2 != 0; row++)
{
for (column = 0; column < cols - 2; column++)
{
if (row % 2 != 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 1)
{
points = -5000;
}
if (row % 2 == 0 && posn[row][column] != 0 &&
posn[row][column] == posn[row][column + 1] &&
posn[row][column] == posn[row][column + 2] && posn[row][column] == 2)
{
points = 5000;
}
}
}
if (eval == -1000)
{
return eval;
}
else
{
return points;
}
Perfect Evaluation for Connect four.
April 06, 2010 02:11 PM
Hello every one.
This thread is started to discuss about writing evaluation method for connect four.
Currently my evaluation contains only winning condition and odd and even move threats, but my program does not win even if it plays first(i.e perfect play).
here is the code for the same.
This game is solved by Mr.Allis and hence would like to implement the same techniques which he did, but not able to do it.
kindly help.
540
April 06, 2010 02:23 PM
Well one thing that comes to mind is that you only do one level of evaluation. You only check the next possible move and have the computer take a winning move if it can.
Have you verified that the computer correctly takes the winning move when one is presented to it?
If you have, i think the issue is just that you need to do like chess AI's do and recursively search a couple moves ahead.
Basically, make a list for every possible move the computer has and score them on how good of a position they are in.
Then, for every one of those possible moves, make a child list of nodes for every possible move the human player could make and score them on how good of a positon the AI is in.
Then, for each of those, make a child list for every possible move the AI could do in response and score how good of a position they are in.
You would do this to some number of levels (however many you wanted... or you could make it go through all posibilities down to the bottom of the tree if you wanted!)
Then, you use some heuristic to decide which possible move is best, like maybe based on the average score of the games of the tree underneath each move.
This isn't a "perfect" solution in that you still have to come up with a way to score a board, and you have to come up with a heuristic for choosing what move is best based on your evaluations, but this should give you better results than you have now (:
Have you verified that the computer correctly takes the winning move when one is presented to it?
If you have, i think the issue is just that you need to do like chess AI's do and recursively search a couple moves ahead.
Basically, make a list for every possible move the computer has and score them on how good of a position they are in.
Then, for every one of those possible moves, make a child list of nodes for every possible move the human player could make and score them on how good of a positon the AI is in.
Then, for each of those, make a child list for every possible move the AI could do in response and score how good of a position they are in.
You would do this to some number of levels (however many you wanted... or you could make it go through all posibilities down to the bottom of the tree if you wanted!)
Then, you use some heuristic to decide which possible move is best, like maybe based on the average score of the games of the tree underneath each move.
This isn't a "perfect" solution in that you still have to come up with a way to score a board, and you have to come up with a heuristic for choosing what move is best based on your evaluations, but this should give you better results than you have now (:
21,604
April 06, 2010 02:29 PM
If you want to make a player that plays perfectly, you don't need an evaluation function at all: What you need is a fast alpha-beta searcher that can go to the end of the tree, and some clever move-ordering technique to make it practical.
John Tromp's page on connect 4 has a lot of useful information.
John Tromp's page on connect 4 has a lot of useful information.
April 07, 2010 03:55 AM
@ Atrix256
I programed this game in java and used Negamax+alpha-beta pruning to search the the tree.
Currently it takes between 1-2 secs to search at depth of 10plys, and about 15-20 secs to search at depth of 14plys after 12 moves.
However for winning games in connect four, one has to implement odd and even row threats for the same.Odd row threats is what player 1 should look for and even move threats. I have named the method which evaluates the board position as Evalc(). Some how I am not able to implement these odd and even rows threats.
I have used simple board logic (programed using arrays) and not bit board logic.
I think that it is possible to program connect4 using this method also, but not able to find the correct way some how.
@ alvaro
Thanks for the link.
However I don't think that it is possible to implement a alpha beta search that is fast enough to evaluate 42 plys ahead(maximum number of moves in connect4.)to see a win. I have made move order such that the center moves will be given the highest preference if no winning move is found till the end of search depth,because they seem to be important in general game. How ever this is not enough as my program might miss the important moves due to horizon effect.
What should I do in this case?
I programed this game in java and used Negamax+alpha-beta pruning to search the the tree.
Currently it takes between 1-2 secs to search at depth of 10plys, and about 15-20 secs to search at depth of 14plys after 12 moves.
However for winning games in connect four, one has to implement odd and even row threats for the same.Odd row threats is what player 1 should look for and even move threats. I have named the method which evaluates the board position as Evalc(). Some how I am not able to implement these odd and even rows threats.
I have used simple board logic (programed using arrays) and not bit board logic.
I think that it is possible to program connect4 using this method also, but not able to find the correct way some how.
@ alvaro
Thanks for the link.
However I don't think that it is possible to implement a alpha beta search that is fast enough to evaluate 42 plys ahead(maximum number of moves in connect4.)to see a win. I have made move order such that the center moves will be given the highest preference if no winning move is found till the end of search depth,because they seem to be important in general game. How ever this is not enough as my program might miss the important moves due to horizon effect.
What should I do in this case?
21,604
April 07, 2010 06:05 AM
Quote: Original post by mandar9589
Thanks for the link.
However I don't think that it is possible to implement a alpha beta search that is fast enough to evaluate 42 plys ahead(maximum number of moves in connect4.)to see a win.
You should check out the Fhourstones benchmark, which does precisely that (in about 5 minutes). In order to play perfectly at a more reasonable pace, John Tromp computed the game value of all positions after 8 moves have been played on the board, so a program can look it up to play the first few moves perfectly. After 8 moves, you should be able to search the whole tree in a few seconds at most.
The link to the database seems to be down, but you can send John an email and I am sure he'll fix it.
Quote: I have made move order such that the center moves will be given the highest preference if no winning move is found till the end of search depth,because they seem to be important in general game. How ever this is not enough as my program might miss the important moves due to horizon effect.
What should I do in this case?
I believe Fhourstones uses one number in the range [-128,128) per square to indicate the urgency of moving there. Moves are sorted according to that value. If alpha-beta determines that the best move is playing at a certain square, one is removed from urgency for each of the other moves available and those points are added to the urgency of the best move (it's good enough if the move generated a beta cutoff, but in that case I think only the moves that had been explored are penalized).
John said this trick sped up the search enormously. You should look at the source code for details.
April 09, 2010 11:02 AM
@alavaro
Having a tough time analyzing his code, first of all he implemented it in bit boards(I know they are faster than simple programing but some how not able to understand that. It will take some time from my side to really program using bit boards.)
However I tried it you using simple like to see connect three in one line or block opponents three in one line etc. using many if and for loops.
This has increased program strength but now it takes much more time to evaluate the position even at smaller depths, still odd row and even row threats are yet to be managed. eg. at depth of 6 it takes about 16 secs to play the first move.
Having a tough time analyzing his code, first of all he implemented it in bit boards(I know they are faster than simple programing but some how not able to understand that. It will take some time from my side to really program using bit boards.)
However I tried it you using simple like to see connect three in one line or block opponents three in one line etc. using many if and for loops.
This has increased program strength but now it takes much more time to evaluate the position even at smaller depths, still odd row and even row threats are yet to be managed. eg. at depth of 6 it takes about 16 secs to play the first move.
21,604
April 09, 2010 10:30 PM
Well, in 1995 I made a connect-4 program that looked at depth 12 or so in 10 seconds, and it didn't use bitboards. It did detect odd and even threats, as well as measuring the number of odd-row spaces where there was still the possibility of eventually making a threat.
If there is a specific part of John's code that you need help with, I can give it a try. And if I don't understand it, I'll ask him tomorrow when I go over to his house to try his jumping stilts. :)
If there is a specific part of John's code that you need help with, I can give it a try. And if I don't understand it, I'll ask him tomorrow when I go over to his house to try his jumping stilts. :)
April 10, 2010 04:36 AM
Here is the code for evaluation in which I am using methods of weights in order to determine the moves.
I am writing this type of eval, is it a correct way, by looking at john's code, i get a feeling that I am just copying his work, and secondly, I would like to go step by step and so wanted to implement odd row threats for player1.
Is the above way correct way to implement?
for (row = 0; row < rows&&row%2==0; row++) { for (column = 0; column < cols - 5; column++) { //_XXX_ if (posn[row][column] == 0 && posn[row][column+1]==1 && posn[row][column + 1]==posn[row][column + 2]&& posn[row][column + 2]==posn[row][column + 3] && posn[row][column+4]==0 ) { eval = -999; } //X_XX_ if (posn[row][column] == 1 && posn[row][column+1]==0 && posn[row][column ]==posn[row][column + 2]&& posn[row][column ]==posn[row][column + 3] && posn[row][column+4]==0 ) { eval = -900; } //XX_X_ if (posn[row][column] == 1 && posn[row][column+1]==1 && posn[row][column + 2]==0&& posn[row][column]==posn[row][column + 3] && posn[row][column+4]==0 ) { eval = -900; } } } I am writing this type of eval, is it a correct way, by looking at john's code, i get a feeling that I am just copying his work, and secondly, I would like to go step by step and so wanted to implement odd row threats for player1.
Is the above way correct way to implement?
21,604
April 10, 2010 10:34 AM
The loop only runs for row=0, so it's probably wrong... Do you know how to step through your code with a debugger?
Odd threats are also important for player 2, for instance to protect against one of player 1's odd threats.
Odd threats are also important for player 2, for instance to protect against one of player 1's odd threats.
April 10, 2010 02:44 PM
Quote: Original post by alvaro
The loop only runs for row=0, so it's probably wrong... Do you know how to step through your code with a debugger?
Odd threats are also important for player 2, for instance to protect against one of player 1's odd threats.
I dont know why are you telling that it will only run for row=0?
First of all I think my post was not clear and also the variables used here were not quiet programer friendly.
in my program, the variable rows(note 's') is the number of total rows(which are 6) and total number of columns which are 7.
Now the rows proceed from 0 to 5(total 6). The first row on board for human is 0 row for computer. and that is why I have put row%2==0 because all odd rows will have this value as 0 for the computer.
Right now I am testing the evals only for player one, so that I can keep a track on smaller number of moves than going for both at this time when I dont know whether my evaluation method would return a proper value or not.
I know I have not implemented even row threats because I wan to know whether the path I am using is correct or not before proceeding and digging further.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
