Perfect Evaluation for Connect four.

Artificial Intelligence Programming

Started by mandar9589 April 06, 2010 02:11 PM

40 comments, last by mandar9589 14 years, 6 months ago

alvaro

21,607

April 10, 2010 04:28 PM

Quote: Original post by mandar9589
I dont know why are you telling that it will only run for row=0?

Because it will.

#include <iostream>int main() {  int rows = 6, row;    for (row = 0; row < rows&&row%2==0; row++)    {      std::cout << row << '\n';    }}

mandar9589

Author

100

April 11, 2010 05:54 AM

@alvaro

I apologize, it was my mistake in putting up the code
Actually I meant to write something like this

  for (row = 0; row < rows; row++)          {            for (column = 0; column < cols - 5; column++)              {                if (row % 2 == 0)                  //_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;                      }                  }              }          }        return eval;      }

mandar9589

Author

100

April 12, 2010 12:08 PM

Is implementing self learning any good in this game?
Also, When I test my evaluation at depth of 10, after the following moves are played
1.4-4
2.4-4
3.4-4
4.5-3
5.5??

Now this is a losing move by force for the program, how to explain or to be technical, how to program this kind of situation so that my engine will play the best possible move? in the case of my game, the best possible move is 5)3(Play in third column)

alvaro

21,607

April 12, 2010 06:42 PM

Quote: Original post by mandar9589
Is implementing self learning any good in this game?
Also, When I test my evaluation at depth of 10, after the following moves are played
1.4-4
2.4-4
3.4-4
4.5-3
5.5??

Now this is a losing move by force for the program, how to explain or to be technical, how to program this kind of situation so that my engine will play the best possible move? in the case of my game, the best possible move is 5)3(Play in third column)

Your search should be able to figure out that 5 is a losing move. It turns out that 6 is also a winner.

mandar9589

Author

100

April 13, 2010 02:57 AM

@alvaro

I know if my searching would have seen that it loses after that badly played move in next 10 plys, then it would not have played that move.
But this win for the second player is coming towards the end.
My program is not able to search the best possible move or the bad move due to horizon effect.

I believe that a good evaluation should have more return value for odd threats of player 1 than even threats of player2 and player 1 should play aggressively as well as positionally. But then seeing this type of result in the test game I made,I made it equal for both odd and even threats for respective players.

As far as I know, Mr Allis and Mr Allen(independently) solved the game by using set of nine rules.
Does any one have pseudo code for the same?

I program in java, and don't have in depth knowledge of pointer as it is managed by the Java(they seem to be confusing at least for me, however the expert programmers make use of them as a very powerful tool).

Since there are no captures here, I cannot make use of LVA/MVV.
then at depth of 10 how to code for the program to see that a move is good or bad, using evaluation?

It will be a great help if pseudo code is available on those nine rules which Allis made as just seeing odd and even threats are not enough for a program to win.

alvaro

21,607

April 13, 2010 08:20 PM

Quote: Original post by mandar9589
@alvaro

I know if my searching would have seen that it loses after that badly played move in next 10 plys, then it would not have played that move.
But this win for the second player is coming towards the end.
My program is not able to search the best possible move or the bad move due to horizon effect.

Well, if you improve your program, it will be able to look further. Extending forced moves would also improve the tactical ability of your program.

Quote: I believe that a good evaluation should have more return value for odd threats of player 1 than even threats of player2 and player 1 should play aggressively as well as positionally. But then seeing this type of result in the test game I made,I made it equal for both odd and even threats for respective players.

A good evaluation function would look at the difference of odd threats between the two players, and know that first_player.odd()>second_player.odd() means that the first player is likely to win and that first_player.odd()<=(second_player.odd()-2) means that the second player is likely to win. In the middle, it matters how many columns have a shared odd threat, and things of that type. The details are starting to fade from my memory, since it's been 14 years since I spent time studying this game.

It is also important to be more confident on the result if the opponent has fewer odd places where a threat is still possible.

Quote: As far as I know, Mr Allis and Mr Allen(independently) solved the game by using set of nine rules.
Does any one have pseudo code for the same?

I don't know how they did it exactly. I believe one of them used rote learning (in a series of self-play games, when you find the theoretical value of a position, save it in a table that you'll use during the search in future games).

Quote: I program in java, and don't have in depth knowledge of pointer as it is managed by the Java(they seem to be confusing at least for me, however the expert programmers make use of them as a very powerful tool).

The programming language shouldn't be much of an issue.

Quote: Since there are no captures here, I cannot make use of LVA/MVV.
then at depth of 10 how to code for the program to see that a move is good or bad, using evaluation?

LVA/MVV is a technique for capture search in chess, which isn't relevant here. You just need a good evaluation function, and perhaps not stop if the next move is forced.

Alternatively, you can explore the game tree to the end and have no horizon effect. John Tromp's Java applet does it after 8 moves, so it's definitely achievable.

[Edited by - alvaro on April 14, 2010 5:20:04 AM]

mandar9589

Author

100

April 14, 2010 03:08 PM

Quote: Extending forced moves would also improve the tactical ability of your program.

I didn't get you, can you be more elaborate this?

Quote: A good evaluation function would look at the difference of odd threats between the two players, and know that first_player.odd()>second_player.odd() means that the first player is likely to win and that first_player.odd()<=(second_player.odd()-2) means that the second player is likely to win. In the middle, it matters how many columns have a shared odd threat, and things of that type. The details are starting to fade from my memory, since it's been 14 years since I spent time studying this game.

It is also important to be more confident on the result if the opponent has fewer odd places where a threat is still possible.

But I have heard that player1 strives for odd rows and player2 for even rows

Quote: John Tromp's Java applet does it after 8 moves, so it's definitely achievable.

Well John Tromp used bit-boards for the game and as we know, bit-boards are way faster than normal array data types,and since I want it to play from scratch, so it must play perfect game even before 8 moves.
like in my previous example I gave, my program playing first
played the following moves:
1]4-4
2]4-4
3]4-4
4]5-3
5]5??-5
6]5-3
7]5-3
8]3-6
9]3-6// odd row threat.
10]7-6
11]6-6
12]5-3
13]6-1
14]7-1
15]7-7
16]7-1
17]1-1
18]7-1
19]2-2 // player 2 wins.
Now even if I choose to play at depth of 15 plys still my program wont recognize that there is a win for player2 as he gets odd row threat in row 5, while player 2 gets even row 2 diagonal threat.

Also I tried to implement the following logic of make 3 in a row,else if possible block three in a row,get two connected else block 2. in their decreasing order.
However, there are tricky stuffs in this game that require much more than that.
I can see that from move number 5 of the above mentioned game, it connects 2 in a row,but then loses.

alvaro

21,607

April 14, 2010 03:59 PM

Quote: Original post by mandar9589
Quote: Extending forced moves would also improve the tactical ability of your program.

I didn't get you, can you be more elaborate this?

When you call something like `NegaMax(position, depth)', the function will recursively call `NegaMax(other_position, depth-1)'. What I mean is that in cases where there is an immediate threat that must be answered, you probably shouldn't do `depth-1' and instead use `depth' again, and only consider the forced move. This effectively will search that branch one step further.

Quote: But I have heard that player1 strives for odd rows and player2 for even rows

Well, what you heard is only the beginning of the story. If player 1 has an odd threat and player 2 has 3 even threats, player 2 loses. It is mostly the case that only odd threats matter. Then if it turns out that both players have the exact same number of odd threats or 2 has 1 more, and there isn't a spot that is a shared odd threat, the result will be win for 2 or a draw, depending on whether 2 has an even threat or not.

Quote:
Quote: John Tromp's Java applet does it after 8 moves, so it's definitely achievable.

Well John Tromp used bit-boards for the game and as we know, bit-boards are way faster than normal array data types,and since I want it to play from scratch, so it must play perfect game even before 8 moves.

That's a poor excuse. You can do pretty well with arrays. And, if bitboards are such a big win, maybe you should look into using them... John's solution for playing perfectly before 8 moves is having a database of the value of all positions after 8 moves.

Quote: like in my previous example I gave, my program playing first
played the following moves:
1]4-4
2]4-4
3]4-4
4]5-3
5]5??-5
6]5-3
7]5-3
8]3-6
9]3-6// odd row threat.
10]7-6
11]6-6
12]5-3
13]6-1
14]7-1
15]7-7
16]7-1
17]1-1
18]7-1
19]2-2 // player 2 wins.
Now even if I choose to play at depth of 15 plys still my program wont recognize that there is a win for player2 as he gets odd row threat in row 5, while player 2 gets even row 2 diagonal threat.

No, player 1 doesn't really get an odd threat. If the opponent has a lower threat of different parity in the same column, that's not a threat.

Quote: Also I tried to implement the following logic of make 3 in a row,else if possible block three in a row,get two connected else block 2. in their decreasing order.
However, there are tricky stuffs in this game that require much more than that.
I can see that from move number 5 of the above mentioned game, it connects 2 in a row,but then loses.

That type of approach is too simplistic for most games, and definitely for connect 4.

mandar9589

Author

100

April 15, 2010 10:51 AM

 public static int Eval2(int board1[], boolean turn)      {        int points = 0;        int eval = 0;        int row;        int sq;        int column;        int posn[][] = new int[6][7];        for (sq = 0; sq < 42; sq++)          {            posn[sq / 7][sq % 7] = board1[sq];          }        int type = 0;        if (turn == true)          {            type = 1;          } else          {            type = 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;                  }              }          }        int points1 = 0;        int points2 = 0;        for (row = rows - 2; row >= 1; row--)          {            for (column = 0; column < cols - 4; column++)              {                if (posn[row][column] == 0 && posn[row][column + 1] == type &&//_XXX_ from row 4onwards.                        posn[row][column + 2] == type && posn[row][column + 3] == type && posn[row][column + 4] == 0)                  {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 1)                      {                        points2 =  -1*points1;                      }                  }              }          }        for (row = 0; row < rows - 4; row++)          {            for (column = 0; column < cols - 6; column++)              {                if (posn[row][column] == 0 &&                        posn[row + 1][column + 1]==type &&                        posn[row + 2][column + 2]==type &&                         posn[row + 3][column + 3]==type &&posn[row+4][column+4]==0)                   {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 1)                      {                        points2 =  -1*points1;                      }                  }              }          }  for (row = 0; row < rows - 3; row++)          {            for (column = 0; column < cols - 5; column++)              {                if (posn[row][column] == type &&                        posn[row + 1][column + 1]==0&&                        posn[row + 2][column + 2]==type &&posn[row + 3][column + 3]==type                         )                   {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 1)                      {                       points2 =  -1*points1;                      }                  }                 if (posn[row][column] == type &&                        posn[row + 1][column + 1]==type&&                        posn[row + 2][column + 2]==0 &&posn[row + 3][column + 3]==type                         )                   {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 1)                      {                       points2 =  -1*points1;                      }                  }                 if (posn[row][column] == type &&                        posn[row + 1][column + 1]==type&&                        posn[row + 2][column + 2]==type &&posn[row + 3][column + 3]==0                         )                   {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 2)                      {                        points2 = -1 * points1;                      }                  }              }             if (posn[row][column] == 0 &&                        posn[row + 1][column + 1]==type&&                        posn[row + 2][column + 2]==type &&posn[row + 3][column + 3]==type                         )                   {                    if (row % 2 != 0)                      {                        points1 = points1 + 10;                      }                    if (type == 2)                      {                       points2 = -1*points1;                      }                  }              }                        for (row = rows - 2; row >= 1; row--)          {            for (column = 0; column < cols - 4; column++)              {                //_XXX                if (posn[row][column] == 0 && posn[row][column + 1] == type &&                        posn[row][column + 2] == type && posn[row][column + 3] == type)                  {                    if (row % 2 != 0)                      {                        points1 = points1 + 1;                      }                    if (type == 1)                      {                        points2 =  -1*points1;                      }                  }                //XXX_                if (posn[row][column] == type && posn[row][column + 1] == type &&                        posn[row][column + 2] == type && posn[row][column + 3] == 0)                  {                    if (row % 2 != 0)                      {                       points1 = points1 + 1;                      }                    if (type == 1)                      {                       points2 = -1*points1;                      }                  }                //XX_X                if (posn[row][column] == type && posn[row][column + 1] == type &&                        posn[row][column + 2] == 0 && posn[row][column + 3] == type)                  {                    if (row % 2 != 0)                      {                        points1 = points1 + 1;                      }                    if (type == 1){                points2 = -1*points1;                      }                  }//X_XX                 if (posn[row][column] == type && posn[row][column + 1] == 0 &&                        posn[row][column + 2] == 0 && posn[row][column + 3] == type)                  {                    if (row % 2 != 0)                      {                        points1 = points1 + 1;                      }                    if (type == 1)                      {                        points2 = -1*points1;                      }                  }              }          }        points = points1 + points2;        if (eval == -1000)          {            return eval;          } else          {            return points;          }      }

Am I proceeding in correct direction?

alvaro

21,607

April 15, 2010 08:03 PM

Quote: Original post by mandar9589
*** Source Snippet Removed ***

Am I proceeding in correct direction?

I am not familiar with the programming language you are using, but dynamic memory allocation is generally not needed for this type of thing.

You can make your code loop through all the columns and within each column start from the bottom trying to identify threats. Once a threat has been identified, you can eliminate threats of the opponent that are higher and have different parity.

Keep a counter of how many columns have odd threats for each player, and to first order make that the evaluation function. That's probably a good beginning. You should also identify if there are any points that are odd threats for both players simultaneously. I can try to remember the exact rules for who wins under what combination of threats, but it may take some time. I think John remembers the details better than I do, so I'll ask him tomorrow.

Perfect Evaluation for Connect four.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Perfect Evaluation for Connect four.

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines