Search Algorithm

[Joost Buijs]

I've been trying various changes, but everything tests around 48% against the baseline version that has the qsearch integrated into the main search. Instead of extending all the moves when there is a non-side capture, I tried extending only the ones that actually do lead to a capture position. This makes more sense to me and eliminated some of the explosion of qsearch nodes, but it tested the same as extending all the moves. Of course I might have a bug, but qsearch is pretty simple, and hard to imagine what could be wrong. I'm playing around 2500 games at 0.5sec increment for each test.

The moves that I search in quiescence are captures, promotions and moves that trigger a non losing exchange and maybe I will add moves with the foremost man when it is free to move (like moves with an advanced passed pawn in chess).

How do you test that a move triggers a non-losing exchange without actually making the move and reply captures (to test the non-losing)? I don't extend moves that lead to a capture if the static eval is already outside a window of 200 (2 men) from alpha or beta. I'm looking at English checkers now, but I also do something similar in 10x10.

-- Ed

I check the surrounding of the square where the disc moves to very carefully to see when it gets captured if I can recapture the non-side disc immediately, this static test is not watertight though, there are always exceptions to the rule, but in most cases it prevents me from doing a move that gives away a disc for free and would be a waste of time. Since it is a bit difficult to check due to edge effects I divided the board in several regions, the center and a few rings around it which I treat differently, a move to the edge does not have to be checked at all, I only check whether an edge move threats to capture a non-side disc.

Your suggestion to terminate qsearch when the static eval lays far outside the a-b window seems like a good one and is something I'm going to try to keep my qsearch from exploding too much.

Joost

[Joost Buijs]

I don't extend moves that lead to a capture if the static eval is already outside a window of 200 (2 men) from alpha or beta. I'm looking at English checkers now, but I also do something similar in 10x10.
-- Ed

I gave your suggestion a quick try and most of the time it works fine, sometimes it shoots out to a very great depth though and the search hangs, I don't think it crashes but it looks like it is busy at depths of 70 plies or more. I have to examine what exactly happens and how it can be solved. Tomorrow I will take another look at it.

Joost

[Rein Halbersma]

I don't extend moves that lead to a capture if the static eval is already outside a window of 200 (2 men) from alpha or beta. I'm looking at English checkers now, but I also do something similar in 10x10.
-- Ed

I gave your suggestion a quick try and most of the time it works fine, sometimes it shoots out to a very great depth though and the search hangs, I don't think it crashes but it looks like it is busy at depths of 70 plies or more. I have to examine what exactly happens and how it can be solved. Tomorrow I will take another look at it.

Joost

These type of positions can be particularly nasty. With wtm there is a threatened capture by black, and you can get into an infinite loop by 28-23 18-22 23-28 22-18 etc., each time there is only a threatened capture, but not a direct capture.

[Joost Buijs]

I don't extend moves that lead to a capture if the static eval is already outside a window of 200 (2 men) from alpha or beta. I'm looking at English checkers now, but I also do something similar in 10x10.
-- Ed

I gave your suggestion a quick try and most of the time it works fine, sometimes it shoots out to a very great depth though and the search hangs, I don't think it crashes but it looks like it is busy at depths of 70 plies or more. I have to examine what exactly happens and how it can be solved. Tomorrow I will take another look at it.

Joost

These type of positions can be particularly nasty. With wtm there is a threatened capture by black, and you can get into an infinite loop by 28-23 18-22 23-28 22-18 etc., each time there is only a threatened capture, but not a direct capture.

Rein thanks!

I expect it can be something like this because it is only one processor that keeps busy and seems to be looping. An easy way to check or prevent this is to disable extending on non-side captures when there are kings on the board.

Another option I will try is to enable repetition detection in quiescence, I removed this some time ago because it seemed not useful but it is still in place so I just have to enable it.

Joost

Edit:

I re enabled repetition detection in quiescence and the hanging/looping problem is gone, en passant by looking at the code I found another bug that crept in a couple of days ago. I started a new match against Kingsrow (currently the only way I can check my program) and it seems to be doing fine, only one loss till now.

After running 50 games I can clearly see that my program scores somewhat less (~42% compared to the old 46%), I know 50 games is statistically unsound but it is enough to see large differences. It does not seem to win anymore, maybe a lack of depth or playing too defensively.

Everything is pretty well mistuned, I will start working on a self-play module that will enable me to run tests like these a 100 times faster.

[Fabien Letouzey]

Instead of extending all the moves when there is a non-side capture, I tried extending only the ones that actually do lead to a capture position. This makes more sense to me and eliminated some of the explosion of qsearch nodes, but it tested the same as extending all the moves.

Extending all moves makes sense too, with a different interpretation: "my opponent is threatening me, so I am not allowed to stand pat". Furthermore I expect that most moves leave the capture anyway.

[Joost Buijs]

Instead of extending all the moves when there is a non-side capture, I tried extending only the ones that actually do lead to a capture position. This makes more sense to me and eliminated some of the explosion of qsearch nodes, but it tested the same as extending all the moves.

Extending all moves makes sense too, with a different interpretation: "my opponent is threatening me, so I am not allowed to stand pat". Furthermore I expect that most moves leave the capture anyway.

Well, this is exactly what I'm doing right now, when there are non-side captures the program is not allowed to stand pat and tries all non-capture moves. It still costs some (or too much) depth, it needs to be tuned better before I'll decide to leave it in or throw it out.

[TAILLE]

Hi,

My view of the qsearch seems a little different from yours but perhaps we have not the same answer to the basic question: "why do you need a qsearch ?"
Let's take a first basic example.
Take us a branch of the main search in which the following scheme appears for a long time.

You may evaluate here a advantage for white because four black men are blocked by only three white men. But it is black to move and it remains just one move to reach a leaf of the main search.
If black plays 12-17 a static evaluation of the position may now give black an advantage due to white men inactive on the side. 12-17 is probably a bad move but you have to discover the response 21-17 etc.
How can you solve the problem?
You can of course improve your eval function to take care of such basic tactic issue but if you take a slightly more difficult example you will not be able to solve the problem will you?
For me the very basic idea behind the qsearch is to solve this specific issue: detecting a bad last move which changes some bad position in an apparently good position.

Let's take a second basic example

Here it is white to play the last move of the main search and consider the move 30-24.
The situation is very different: the last move 30-24 appears as an agressive attacking move instead of a probably bad move. You have here to define clearly what you want exactly because the situation is quite difficult: with 30-24 white gives black a tempo and it is a typical situation in which a complex combinaison may occur for black, but on the other hand, if no combinaison exists white may win a man.
In order to avoid endless qsearch due to a long serie of unstable positions you may have to accept here a rather bad evaluation. In such situation my choice in the qsearch is only to look for a small combinaison for black in order to prove that 30-24 may be a bad move.

To summarize, the only goal of my qsearch is to try to prove that the last move may be a bad move. I do not look for proving that the last move may be a good move against it no good answer exists.

[Joost Buijs]

Hi Gerard,

You are right in saying that the standard way of doing qsearch is a very dumb and costly way to tackle these problems and that there must be smarter ways to accomplish the same. Maybe there is something like the concept of connected moves, for instance in the examples above the only replies you have to consider is moving to the square the opponent just left.

For the moment my goal is to get my engine running without going into great detail and to leave all kinds of enhancements for the future.

Joost

[Joost Buijs]

I've been examining the losses of my engine against Kingsrow and several of them were caused by doing Probcut at capture nodes which made the engine blind for some tactics, after fixing this the score went up and is now >47% or <21 Elo. This probably is as good as it gets without having a means to automatically tune the engine.

Edit:

After fixing the above I tried again to do all non-capture moves when there are non-side captures in quiescence, doing this performs a lot better now, the score went up to 48% or roughly -14 Elo, which is not so bad considering the fact that the engine is still badly tuned.

The next thing I will add is singular extensions, I expect this to work very well with draughts because most lines seem to be forced and very narrow.

Edit:

After fixing a small data-race in the transposition table update code my engine scores now roughly on par with Kingsrow, the last result from Kingsrows perspective is 6 wins 4 losses 89 draws and 1 unknown, after 80 games the score was equal, kingsrow scored 2 wins the last 20 games so I really need more games to determine the exact strength but it is clear that it is very close.

[CheckersGuy]

Hey guys,
I am currently working on my search algrotihm. I have implemented history heuristic, countermove-heurstic and killer-moves for moveOrdering silent (no jumps) moves. I wonder what techniques you guys are using and what I could do to order jump-moves because I think that could improve my engine by quite a bit.

Thanks

[Joost Buijs]

Hey guys,
I am currently working on my search algrotihm. I have implemented history heuristic, countermove-heurstic and killer-moves for moveOrdering silent (no jumps) moves. I wonder what techniques you guys are using and what I could do to order jump-moves because I think that could improve my engine by quite a bit.

Thanks

In my Draughts engine I do basically the same as you do, the only difference is that I don't distinguish between silent and jump moves for move ordering.

I use the following order: hash-move, 2 killers, countermove and history and I try to move with the most advanced disc first (sorted based on rank). All these techniques seem to be less efficient compared to Chess, I guess the on average 4 times lower number of available moves has to do with this.

Somehow countermove and history do very little in my engine (other people have better results with this), the hash-move, the 2 killers and trying to move with the most advanced disc first is already very efficient. This is with 10x10 Draughts, maybe Checkers behaves differently.

[Ed Gilbert]

I wonder what techniques you guys are using and what I could do to order jump-moves because I think that could improve my engine by quite a bit.

In checkers, in addition to the things already mentioned, I decrease the move ordering priority of a move that leads to a capture position for the opponent, and I increase the priority of a move that leads to a non-side capture position.

-- Ed

[CheckersGuy]

Hey guys,
I am currently working on my search algrotihm. I have implemented history heuristic, countermove-heurstic and killer-moves for moveOrdering silent (no jumps) moves. I wonder what techniques you guys are using and what I could do to order jump-moves because I think that could improve my engine by quite a bit.

Thanks

In my Draughts engine I do basically the same as you do, the only difference is that I don't distinguish between silent and jump moves for move ordering.

I use the following order: hash-move, 2 killers, countermove and history and I try to move with the most advanced disc first (sorted based on rank). All these techniques seem to be less efficient compared to Chess, I guess the on average 4 times lower number of available moves has to do with this.

Somehow countermove and history do very little in my engine (other people have better results with this), the hash-move, the 2 killers and trying to move with the most advanced disc first is already very efficient. This is with 10x10 Draughts, maybe Checkers behaves differently.

History and killer moves work very well . However, countermoves don't seem to add much, nor do they hurt . I should probably work on other parts of my search algorithm like getting some more plies from search reductions (LMR, ProbCut). I tried to implement LMR once but it didnt really work that well at all. I am going to take a look at LMR again and if that still doesnt work I implement ProbCut.

[Joost Buijs]

Hey guys,
I am currently working on my search algrotihm. I have implemented history heuristic, countermove-heurstic and killer-moves for moveOrdering silent (no jumps) moves. I wonder what techniques you guys are using and what I could do to order jump-moves because I think that could improve my engine by quite a bit.

Thanks

In my Draughts engine I do basically the same as you do, the only difference is that I don't distinguish between silent and jump moves for move ordering.

I use the following order: hash-move, 2 killers, countermove and history and I try to move with the most advanced disc first (sorted based on rank). All these techniques seem to be less efficient compared to Chess, I guess the on average 4 times lower number of available moves has to do with this.

Somehow countermove and history do very little in my engine (other people have better results with this), the hash-move, the 2 killers and trying to move with the most advanced disc first is already very efficient. This is with 10x10 Draughts, maybe Checkers behaves differently.

History and killer moves work very well . However, countermoves don't seem to add much, nor do they hurt . I should probably work on other parts of my search algorithm like getting some more plies from search reductions (LMR, ProbCut). I tried to implement LMR once but it didnt really work that well at all. I am going to take a look at LMR again and if that still doesnt work I implement ProbCut.

For LMR I have 2 different reduction tables, the one for the PV is less aggressive as the non-PV one, unfortunately they are not very well tuned yet, I still have to do this. I have a very simple implementation of ProbCut which gives a few plies extra depth, like LMR this feature still has to be tuned before I can say anything about it's performance.

Right now I'm working on my SMP search, I'm still not satisfied with it. The biggest problem is stopping all the processors working on a splitpoint after one of them has found a beta cutoff. At the moment I set an abort flag for each thread working on the splitpoint and when that flag is set I throw an exception, it works fine but it still takes too much time, I want to terminate these threads instantly, atm. it takes roughly 35 to 70 nsec. to stop a thread this is a lot of overhead when you search >100 mnps. Maybe setjmp/longjmp performs better because throw() unwinds the whole stack (which I don't need), this is something I still have to try.

Edit:

It is not so easy to get the SMP search 100% free of data-races, while I was looking for a better way to stop the slave-threads I found another problem. Since I don't want to have my threads polling for work all the time (this to keep the processor cooler and my system more responsive) I use condition variables to kick the slaves when there is work to do. Condition variables have a nasty habit, sometimes they trigger spontaneously, I know this but due to an oversight it happened occasionally that a slave was kicked before it was properly initialized which of course messed things up. After fixing this the Elo went up by approximately 28 points.

[Joost Buijs]

After fixing tens of small issues in the search and spending many hours on tuning probcut and the LMR tables the results of my engine are now getting better at hyper bullet as well. The last 158 games from Kingsrows perspective ended with 11 wins, 13 losses, 132 draws, 2 unknowns, so very close to each other. I used Fisher clock with 3 seconds initial time and 0.1 seconds increment per move.

I will leave the search for what it is right now and start working on a simple console interface and implementing pondering.

Edit:

Out of curiosity I ran another match with 1 minute and 90 moves per game (dxpgames7). The score for Kingsrow is: 8 wins, 7 losses, 139 draws and 4 unknowns, again very close. Now I will take a sabbatical just like Bert.

Joost