• Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!

We're also offering banner ads on our site from just \$5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.

# Experimenting with killer moves and history heuristic,and a question

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.

18 replies to this topic

### #1patishi  Members   -  Reputation: 212

Like
0Likes
Like

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.    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, 13 July 2013 - 05:09 AM.

### #2Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 13 July 2013 - 05:31 AM

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".

### #3patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 July 2013 - 07:34 AM

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    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, 13 July 2013 - 10:07 AM.

### #4Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 13 July 2013 - 11:48 AM

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.

### #5patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 July 2013 - 11:59 AM

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, 13 July 2013 - 12:00 PM.

### #6Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 13 July 2013 - 12:47 PM

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.

### #7patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 July 2013 - 01:49 PM

no..i was just kidding saying that 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

Edited by patishi, 13 July 2013 - 01:54 PM.

### #8patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 13 July 2013 - 08:14 PM

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, 13 July 2013 - 08:23 PM.

### #9Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 13 July 2013 - 08:59 PM

That's the kind of question that can only be answered by testing.

### #10patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 17 July 2013 - 03:46 PM

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

### #11Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 18 July 2013 - 04:53 AM

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

### #12patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 18 July 2013 - 05:01 AM

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.

### #13Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 18 July 2013 - 05:45 AM

You can always use the history heuristic for moves that are not killers. That's what we typically do in chess.

### #14patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 18 July 2013 - 09:04 AM

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, 18 July 2013 - 09:04 AM.

### #15Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 18 July 2013 - 12:06 PM

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.

### #16patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 18 July 2013 - 05:03 PM

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  )

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

Edited by patishi, 18 July 2013 - 05:06 PM.

### #17Álvaro  Crossbones+   -  Reputation: 13645

Like
0Likes
Like

Posted 18 July 2013 - 09:34 PM

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.

### #18patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 18 July 2013 - 10:27 PM

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

### #19patishi  Members   -  Reputation: 212

Like
0Likes
Like

Posted 18 July 2013 - 11:40 PM

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, 18 July 2013 - 11:45 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