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

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

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)

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.

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.

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.

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

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)

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

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