Jump to content

  • Log In with Google      Sign In   
  • Create Account


Connect 4 evaluation function,need some guide


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 18 June 2013 - 08:19 PM

Hi everybody.  I am trying for a few months now to write a fast and basic (but good) evaluation function for my connect 4 engine.  (wriiten in JAVA with Minimax/Alpha Beta)
I am following the simple idea of : 1 in a row*1 +2 in a row*4 +3 in a row (odd)*16 +three in a row(even)*32.   but still the engine is playing relatively weak when testing it with some other engines.       

I also tried other tweaks to "help" the engine to control the Zugzwang of the game but with no luck,  so i came back to the basic and simple weights function.     when changing the weights values of the eval' function,the engine changes it's play a little bit ( i have no idea why is that..) but still not strong enought.      

can anybody give me some advice on this?  maybe i am setting the wrong values (maybe too low?)    I will appreaciate any guide you guys can give me.      this is a rather simple game (not chess..)  and i am getting really upset that i am not succeeding in making a normal playing engine.  

even at depth 10 or 12 there is no remarkable improvement... this is why i think that there is a problem with the evaluation function and not a depth issue.   

I  am not trying to make a perfect engine, only one that plays a relatively strong game.    thx!

 

 

EDIT: well, here is an update, i added adjacent pieces (neighbors) checking for the two in a row combinations. I am adding some points to two adjacent tokens and seems to help a little.     But i wonder,what it takes to make the engine play sharper and attack more..  


Edited by patishi, 18 June 2013 - 10:45 PM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 11861

Like
0Likes
Like

Posted 19 June 2013 - 07:36 AM

I hope when you say "k in a row" you only consider situations where the remaining 4-k squares are empty. It's good that you know about the difference between even and odd threats. However, this is a game where it is critical to know who wins in every combination of threats possible. For instance, if both players get a threat at the same spot, player 1 will win if the threat is odd and player 2 will win if it's even. A simplistic evaluation function of the type you described can't tell those apart.

 

You should probably learn to play the game really well first. I recommend James Allen's book. Once you know what to look for in a position, you'll be able to translate that into code and get a solid evaluation function.

 

I should point out that for the 7x6 game it is possible to have perfect play. See John Tromp's page on Connect 4 for more info.



#3 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 19 June 2013 - 07:50 AM

Thank you for the reply.    yes,ofcourse i check that the remaining squares are empty,  and in fact, i even wrote a function that gives more points to the AI if he have a threat without any theat from the opponent below in the same column...   and although that DID changed the play a little, it was not necessaraly stronger.      

Actually,I don't get why the Engine can't see this stuff (even and odd threats)  on his own,  i mean...it is LOOKING A HEAD isn't it??      
The way i see it,even if i give him the most basic evaluation without even/odd recognition,it suuposed to see it on his own if the depth is deep enough,but i suppose that depth 12 is not enough to see that far?  
and from reading the james allen's thesis i came to the conclusion that i can't implement all this rules (it is also not so AI the way he is doing it), i was interested to know if there is any way to make a strong engine without getting into all this mess.

 

By the way, can you please explaing to me how ican use the database from the john tromps link you posted?    did i understand correctly?  does it contains all the position of the first 8 plys of the game?    if that so,   does that mean that the Engine should start thinking afterwards?  


Edited by patishi, 19 June 2013 - 08:01 AM.


#4 Álvaro   Crossbones+   -  Reputation: 11861

Like
0Likes
Like

Posted 19 June 2013 - 09:00 AM

The database is used during the first eight moves, by searching a small tree whose leaves are in the database. After the eighth move it is possible to use exhaustive alpha-beta search in at most a few seconds.



#5 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 20 June 2013 - 07:10 PM

well,I like to share my findings and progression with you.   I am now using a basic evaluation that scan all 69 possible winning lines on the board,and checks how much pieces of each player (engine or opponent or none) there is in each line.  when summing all up , this is the basic score of the board.   
Ofcourse that's not enough (or else i would not be here smile.png )  so it took me some time to improve my evaluation function and in the same time keep it simple and fast.  so after months of experiments with many functions,depths settings etc.  i have found something in the right direction (at least it looks like it).    I just added a function that looks for "good threats" for one player.  A   "good threat"  is odd threat for the first player with no even threat of the second player beneath it in the same column,  and the opposite for the second player -(an even threat with no odd threat of the first player beneath it).   and i multiple this estimate by 100 and added it to the basic board evaluation.  And MAGIC!      And i search down to depth 11 in a reasonable time (only a few seconds max for the first moves)
 

I had this simple idea for some time now,but haven't succeeded in implementing it right,    so right now it looks promising and IN FACT,  my engine is beeting my android AI factory four in a row app in level 10 (the highest) both in red(first) and yellow (second).       
I even tested it against the perfect play JAVA applet posted above by Alvaro, and it even wins sometimes playing first and draws (that means that it still doesn't play perfect).    but ofcourse,playing second it always loses smile.png

maybe increasing the depth by a margin will make it play stronger/more solid and not losing when playing first.    I will keep investigating and improving it,but so far i am very satisfied with the results.     
 


Edited by patishi, 20 June 2013 - 07:32 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS