• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
patishi

Experimenting with killer moves and history heuristic,and a question

18 posts in this topic

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??

Edited by patishi
0

Share this post


Link to post
Share on other sites
There are many possible variations of history heuristic. John Tromp says his exhaustive search got much much faster when he started using bounded signed entries in the history-heuristic table, where discovering a beta cutoff on the 4th move gives that move a +3 bonus and the first three moves (the ones that were examined before and did not produce the cutoff) a -1, so the sum stays constant. I don't remember the details of how he capped the values, but they are probably not terribly important.

The killer heuristic should be made dependent on the distance from the root, not the depth left. This number is always well defined, even in an exhaustive search or when using extensions and reductions.

For an exhaustive search you don't need to store a depth parameter in the transposition table. All searches are to the end and the results stored can always be used, if the boundary is useful. Storing a hash move might not be very useful either, but I would have to test that.

Even for exhaustive searches, I would continue to use alpha-beta bounds, particularly if you prefer quick victories. The possible scores are draw, win at the k-th move and lose at the k-th move. Winning at the k-th move can be encoded as being worth +N-k, losing is -(N-k) and a draw is worth 0, where N is a sufficiently large number (at least 43).

John Tromp's program only knows about winning (=1), drawing (=0) and losing (=-1), and doesn't care if it wins immediately or 28 moves later, which gives it a strange style you may not like. Even then, alpha-beta still applies, as in "if I have a move that gives me a draw already, I don't need to distinguish between a draw and losing for the other moves".
0

Share this post


Link to post
Share on other sites

thank you for the reply.    so in general..you are saying that for exhaustive search i can immediately use the score stored from the TT and not check bounds,depth..nothing like that?  

I also don't care so much if the program wins immediately of after 5 moves..as long as it wins!  in fact i already noticed this kind of behaviour in my older engines, i guessed this is because minimax just goes for the first line he sees if the score stays the same (e.g picking the first move).      it actually quite ammusing , like a human player that wants to prove that he can win in other ways too smile.png   twisting  with you mind LOL

For simplicity , right now i would rather go for the simplest approach possible (as few parameters as possible and a less complicated code),  that's why i asked if i can skip the boundaries / depth checking part if i am doing a complete search.

 

So if i want to use the killer moves in an exhaustive search i would still need to use a depth parameter in the alpha beta function (let's say 42..43..to make it get to the end of the tree) ??

 

 

EDIT: By the way, when i am calculating the depth i am starting from  a high number and going down (e.g 8..7..6) until i get to 0.   when saving to the killers table i am using the depth parameter, so it will always be the same ply.  (e.g if the depth was 7 ,it will be 7 also in the killers table.  and only when i am again in that same ply i check for the killer)

Edited by patishi
0

Share this post


Link to post
Share on other sites

so in general..you are saying that for exhaustive search i can immediately use the score stored from the TT and not check bounds,depth..nothing like that?


No, no. I am not saying anything like that. You can only skip checking for depth, since you are effectively doing infinite-depth searches only. You still need to check bounds.

So if i want to use the killer moves in an exhaustive search i would still need to use a depth parameter in the alpha beta function (let's say 42..43..to make it get to the end of the tree) ??


Well, it wouldn't be a "depth left" parameter, which is what I usually mean by "depth" in my alpha-beta code. `distance_from_root' is a much better name for the variable.

EDIT: By the way, when i am calculating the depth i am starting from  a high number and going down (e.g 8..7..6) until i get to 0.   when saving to the killers table i am using the depth parameter, so it will always be the same ply.  (e.g if the depth was 7 ,it will be 7 also in the killers table.  and only when i am again in that same ply i check for the killer)


Yes, that decreasing depth is what I called `depth left', whenever there is confusion. As I said elsewhere in this thread, killers should be indexed by distance from root, not depth left. The other notion seems equivalent until you consider extensions, reductions or iterative deepening. Using distance from root still works in all those cases.
0

Share this post


Link to post
Share on other sites

I switched now to counting from 0 and up  (0..1..2..3) like you said, distance from the root. ( it always seemed more logical to me anyway, i switched to counting down just because i noticed that many programmers are doing so)   and after the 4th move,when i start calclating to the end of the game,i stll keep checking the bounds.    

 

 also, i initiate the transposition table one time in the start of the game, and one more time before i start my exhaustive search.   I afraid that the scores from the shallower search will not be good for the complete search phase.   should i be worry of that?         I initiate thte killer moves table only one time at the start of the game, no more.

Edited by patishi
0

Share this post


Link to post
Share on other sites
I don't understand your motivation for doing something different in the first four moves. John Tromp made a database with the game value of every position after 8 moves, which you could use to play perfectly during that first part too.

Somewhere you mentioned that heuristic search is probably good enough for the first few moves, but I disagree. Some of the early moves are extremely difficult.
0

Share this post


Link to post
Share on other sites

no..i was just kidding saying that smile.png of course that it takes a single wrong move in connect 4 to make the engine lose the game, no matter how perfect it plays afterwards..this is because the zugzwang thing.  connect 4 is one of the most ennoying games i ever encounter LOL     
i am just doing  the evaluation for the first 4 moves to test how fast i can search to the end of the game afterwards  that's all.  when the speed will become optimal i will switch to using some sort of database.  

And besides...if i want to make a program with a level choice, i can use the evaluation function for that.  ( it is a very basic one)    

In fact i already hardcoded a "database"  of my own for the first 4 moves (for white) , by coding all the possible moves for white to any of blacks moves.(taken from a perfect play program ofcourse)  (there is only a single correct white move for every black response so it is not so bad,  although it took me a whole day almost ).   i hardcoded all the moves because i don't know how to use a database file in my program sad.png

Edited by patishi
0

Share this post


Link to post
Share on other sites

By the way,another technical question regarding the history heuristic.    right now i am using a linear array (not multi dimentional) at size 49, which every index represents a move on the board, and than i just increment the specific index when a certain move causes a beta cut-off.   but i don't give attention to the side to move  .  should i??      

   i  can do something like this:  hh [sideToMove] [square].    but i don't know if this is neccesary.    (In the killer moves i also don't give attention to who is to move,but there is a ply parameter to take care of this)

Edited by patishi
0

Share this post


Link to post
Share on other sites

I have something that i didn't get...john tromp writed in his site:  "A move causing a cutoff is rewarded as many points as moves previously tried,"  
did he mean that it gets one point for each?  or maybe it gets all the summary of the points of all the previews moves?    And i assume that by "moves" he talks about the alpha beta main loop (?)

0

Share this post


Link to post
Share on other sites

I think the statement is pretty clear. You are searching some node and you have a list of moves in an array:

move[0] = 17;
move[1] = 5;
move[2] = 11;
//...

 

You explore move 17 and it doesn't produce a beta cutoff, you explore move 5 and it doesn't produce a beta cutoff, you explore move 11 and it does produce a beta cutoff. Then you do

history[17]--;
history[5]--;
history[11]+=2;

 

I gave you a detailed explanation in post #2 in this thread...

0

Share this post


Link to post
Share on other sites

thx, that's what i thought. i tried to implement it just like that but for any reason it still don't cut as much branches as the killer moves do.  so right now i am with the killer moves, although i may give the history another try, maybe try to implement it better.

0

Share this post


Link to post
Share on other sites

And one more thing..i know this is kind of stupid question, but i just want to be sure.   when a move doen not(!) cause a cut off , than he gets only one point right?  

And one correction about the explanation above, isn't it more precise to give the cut off move another point beside the moves that were before it?  for example,in your example alvaro, maybe instead of 2 points it should get 3?    my reasoning is that  the added point is his own actually + the point of all the previews moves tried, and the second and more important reasoning for this is that if it is the first move that has been tried and it causes a cut off than it should at least get one point....      am i mistaken here?

Edited by patishi
0

Share this post


Link to post
Share on other sites

I didn't understand your first question.

 

Why would you want to change anything in the history table if the first move gives you a cutoff? The table seems to be working as intended, so don't touch it. But ultimately, it comes down to testing what works best.

0

Share this post


Link to post
Share on other sites

it seems that i also added points to non-cut off moves, e.g best move after a search, that's the explanation for the first question above.     
But now i switched to only score cut off moves, and there may have been a tiny improvement.     also, it doesn't seem that the hash move is doing anything special..with or without it, the speed is roughly the same.        i am using the two big replacement scheme in the TT , and ordering the moves just like john tromp explains...but still it takes too much time in certain positions.    (by the way, i abandoned the evaluate for one move idea..it's not that good smile.png  )    
 

And most of my code is fast, not so very different for the john tromp bitBoard implementation.      the one thing i think that can contribute to the slowness is my getMoves()  method.   i am creating a java ArrayList in every alpha beta function which hold all the move.   inside this function,   I also sort the moves according to the History table with bubble sort kinda loop..but with java  methods such as :    set(index,element) etc..  which also can be very slow i think.   (not like sorting a normal array).      
The reasin i am using java array list is because i can't know in advance how much available columns i have in a position,  and a normal array is a fixed size structure..while i need a dynamic structure.        

Ofcourse there are ways to increase the array side dynamiacally but it involving recreat new array every time i need to add an element.  (that's actually what the array list is doing in the background + some other bonus stuff that can cause even more slowness).   
I wasn't able to figure out a way to iterate and sort the moves inside the alpha beta without making a hell of a mess in my code smile.png

Edited by patishi
0

Share this post


Link to post
Share on other sites


The reasin i am using java array list is because i can't know in advance how much available columns i have in a position, and a normal array is a fixed size structure..while i need a dynamic structure.

 

7. You need 7 elements in an array, and a variable to tell you how many of the 7 entries are actually being used. Using dynamic memory allocation for this is kind of crazy.

 

I thought you said that your program was as fast as John Tromp's, but now it's obvious that it's not. How many positions per second is it exploring?

 

You should consider spending some time programming in C. That kind of abuse of dynamically allocated memory is something I have seen in many Java programmers, and it's something you should educate yourself against. I think learning C and a bit of assembly would teach you a lot of valuable things. C++ would also do the job, but C is a small language that can be learned in a few weeks, while C++ is a monster that takes years to learn.

0

Share this post


Link to post
Share on other sites

I knew that this getMoves()  function is slow,  but i didn't realize that the java implementation is that bad..but i guess that for this sort of programms, which need absolutely the minimum of operation in the fastest time, this is really too much.   except for this function almost everything is "Bit oriented"  so no especial slowness there... when looking at john tromp's code,  i can see that he is doing the sorting of the moves (by the history table)  "in place"  inside the alpha beta.   I will work on that, and also try to avoid using the array list operations.        This is no tic tac toe AH?...   :)

0

Share this post


Link to post
Share on other sites

This is for me to solve,so don't answer me right now.   but just to explain my "stupidity" by using the java array list:  
I know that the total number columns in the game is 7 right..?     but not all the time all of them is playable (e.g a column can be totally full).   
so what i did is:    ArrayList moves = new ArrayList();      and then pass through all the columns from 0 to 7 (actually i am doing it from the center and outside to improve the move ordering a little bit.   I have an array   columns =  {3,2,4,1,5,0,6} )     and doing      from(i to 7)  { if ! fullColumn, than -  moves.add(i) }      and that's how i get a list that holds all the PLAYABLE columns.   (which in the alpha beta i am just playing one after the other)     

So if i want to create a normal array inside the alpha beta,  and this array has to be declared on some initial size...   let's say for example -    array moves - new int[7];
and than i can do:   from (i to 7)  if !fullColumn,   moves[i] = i;    or something like this..    but than i have an array of size 7  but some indexes can be empty  (or equal to 0, this is the default of int in java).       now,  even in this way i can say that if a columns is full than i put a -1 in the array, that's how i know that i don't need to play this index,   but i can't sort the columns by the HH that way...that's my main problem!                                 so i need to figure out how to initialize this array and how to allocate it.   I read your comment above abouto holding an variable that tells me how many elements i can use, but i didn't understand it (yet).     

If i didn't need to sort this array by the HH, than i could just do  from (i to 7)  if( !fullColumn)  make move... etc'.    but i need to first create an array of all the playable columns and sort it before i can use it.    and i can't just do  moves.add(i)  with a normal array,  only with an arraylist.  
 

I hope i can figure this out on my own..  if not i will come back

Edited by patishi
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0