Jump to content

  • Log In with Google      Sign In   
  • Create Account

#Actualpatishi

Posted 13 July 2013 - 05:09 AM

Hi all.  as some of you already know, i am right in the middle of writing my connect 4 program  so far i have a very nice bit board representation together  with alpha beta algorithm to solve the game.  ofcourse my goal is to make it play perfect and see to the end of game tree.   

But in order to optimize the speed of the engine, i am now using an evaluation function for the first 4 moves (for each player) and after that trying to brute force the game to the end.   if i see  that it complete solving the rest of the game in a reasonable time, i will maybe use a database for the first 8 plies to make it perfect (who knows,maybe the eval' function can make good enough first 4 moves smile.png )     The killler moves gave me a HUGE boost (!) and also the transposition table.     when trying the History heuristic instead of the killer moves,the improvement was there but not like with the killer moves.    perhaps my implementation of the history was not good enough

my question regarding this is:    if i want to continue using the killer moves when i am searching the game to the end,  and the killer moves is a DEPTH dependent scheme (watching for a killer for each depth).   but when i am searching to the end i don't exactly have a depth, cause i just search until i find a win,loss or tie.   that how should i implement it?       should i just change the depth to 40 or something like this ? (so it will reach to the end of the tree anyway)  but still keeping track of the depth parameter of the killer moves?   
And what about the transpositioh table,   is there a point in checking the depth of the retrieved position from the table comparing to the gameBoard?  ( e.g  TTEntry.depth > = currentDepth ) ??  when searching to the end of the tree, the score must be always based on the final result,so my logic tells me that the depth parameter is no longer important in this case     

 

And also..do i even need the alpha beta bounds at all when searching through a whole tree??


#4patishi

Posted 13 July 2013 - 02:06 AM

Hi all.  as some of you already know, i am right in the middle of writing my connect 4 program  so far i have a very nice bit board representation together  with alpha beta algorithm to solve the game.  ofcourse my goal is to make it play perfect and see to the end of game tree.   

But in order to optimize the speed of the engine, i am now using an evaluation function for the first 4 moves (for each player) and after that trying to brute force the game to the end.   if i see  that it complete solving the rest of the game in a reasonable time, i will maybe use a database for the first 8 plies to make it perfect (who knows,maybe the eval' function can make good enough first 4 moves smile.png )     The killler moves gave me a HUGE boost (!) and also the transposition table.     when trying the History heuristic instead of the killer moves,the improvement was there but not like with the killer moves.    perhaps my implementation of the history was not good enough

my question regarding this is:    if i want to continue using the killer moves when i am searching the game to the end,  and the killer moves is a DEPTH dependent scheme (watching for a killer for each depth).   but when i am searching to the end i don't exactly have a depth, cause i just search until i find a win,loss or tie.   that how should i implement it?       should i just change the depth to 40 or something like this ? (so it will reach to the end of the tree anyway)  but still keeping track of the depth parameter of the killer moves?   
And what about the transpositioh table,   is there a point in checking the depth of the retrieved position from the table comparing to the gameBoard?  ( e.g  TTEntry.depth > = currentDepth ) ??  when searching to the end of the tree, the score must be always based on the final result,so my logic tells me that the depth parameter is no longer important in this case


#3patishi

Posted 13 July 2013 - 02:06 AM

Hi all.  as some of you already know, i am right in the middle of writing my connect 4 program  so far i have a very nice bit board representation together  with alpha beta algorithm to solve the game.  ofcourse my goal is to make it play perfect and see to the end of game tree.   

But in order to optimize the speed of the engine, i am now using an evaluation function for the first 4 moves (for each player) and after that trying to brute force the game to the end.   if i see  that it complete solving the rest of the game in a reasonable time, i will maybe use a database for the first 8 plies to make it perfect (who knows,maybe the eval' function can make good enough first 4 moves smile.png )     The killler moves gave me a HUGE boost (!) and also the transposition table.     when trying the History heuristic instead of the killer moves,the improvement was there but not like with the killer moves.    perhaps my implementation of the history was not good enough

my question regarding this is:    if i want to continue using the killer moves when i am searching the game to the end,  and the killer moves is a DEPTH dependent scheme (watching for a killer for each depth).   but when i am searching to the end i don't exactly have a depth, cause i just search until i find a win,loss or tie.   that how should i implement it?       should i just change the depth to 40 or something like this ? (so it will reach to the end of the tree anyway)  but still keeping track of the depth parameter of the killer moves?   
And what about the transpositioh table,   is there a point in checking the depth of the retrieved position from the table comparing to the gameBoard?  ( e.g  TTEntry.depth > = currentDepth ) ??  when searching to t he end of the tree, the score must be always based on the final result,so my logic tells me that the depth parameter is no longer important in this case


#2patishi

Posted 13 July 2013 - 02:04 AM

Hi all.  as some of you already know, i am right in the middle of writing my connect 4 program  so far i have a very nice bit board representation together  with alpha beta algorithm to solve the game.  ofcourse my goal is to make it play perfect and see to the end of game tree.   

But in order to optimize the speed of the engine, i am now using an evaluation function for the first 4 moves (for each player) and after that trying to brute force the game to the end.   if i see  that it complete solving the rest of the game in a reasonable time, i will maybe use a database for the first 8 plies to make it perfect (who knows,maybe the eval' function can make good enough first 4 moves smile.png )     The killler moves gave me a HUGE boost (!) and also the transposition table.     when trying the History heuristic instead of the killer moves,the improvement was there but not like with the killer moves.    perhaps my implementation of the history was not good enough

my question regarding this is:    if i want to continue using the killer moves when i am searching the game to the end,  and the killer moves is a DEPTH dependent scheme (watching for a killer for each depth).   but when i am searching to the end i don't exactly have a depth, cause i just search until i find a win,loss or tie.   that how should i implement it?       should i just change the depth to 40 or something like this ? (so it will reach to the end of the tree anyway)  but still keeping track of the depth parameter of the killer moves?   
And what about the transpositioh table,   is there a point in checking the depth of the retrieved position from the table comparing to the gameBoard?  ( e.g  TTEntry.depth > = currentDepth ) ??


#1patishi

Posted 13 July 2013 - 02:03 AM

Hi all.  as some of you already know, i am right in the middle of writing my connect 4 program  so far i have a very nice bit board representation together  with alpha beta algorithm to solve the game.  ofcourse my goal is to make it play perfect and see to the end of game tree.   

But in order to optimize the speed of the engine, i am now using an evaluation function for the first 4 moves (for each player) and after that trying to brute force the game to the end.   if i see  that it complete solving the rest of the game in a reasonable time, i will maybe use a database for the first 8 plies to make it perfect (who knows,maybe the eval' function can make good enough first 4 moves :) )     The killler moves gave me a HUGE boost (!) and also the transposition table.     when trying the History heuristic instead of the killer moves,the improvement was there but not like with the killer moves.    

my question regarding this is:    if i want to continue using the killer moves when i am searching the game to the end,  and the killer moves is a DEPTH dependent scheme (watching for a killer for each depth).   but when i am searching to the end i don't exactly have a depth, cause i just search until i find a win,loss or tie.   that how should i implement it?       should i just change the depth to 40 or something like this ? (so it will reach to the end of the tree anyway)  but still keeping track of the depth parameter of the killer moves?   
And what about the transpositioh table,   is there a point in checking the depth of the retrieved position from the table comparing to the gameBoard?  ( e.g  TTEntry.depth > = currentDepth ) ??


PARTNERS