Search Algorithm

[Joost Buijs]

Although I did not implement move sorting in Dwarf, there is an implicit move ordening.
For both white as black I use (at least for the man moves) a BITSCANFORWARD to occupy the movelist.
When one thinks about it, this is absolutely asymmetrical.

The black moves in the back of the black position are so on the top of the move list, for white the front moves.
So I tested what the effect was in using a forward (F) and reverse (R) scan.
All at ply 25 for the (famous) Woldouby.

Code: Select all

White	Black	Nodes
F		F		150.967.354
R		F		342.237.097
R		R		345.962.328
F		R		160.613.611

So max a factor 2 difference.
In very quiet positions I would expect that it is safe to populate the movelist first with (defending) moves at the back of the position.
So White R and Black F, but here (for whatever reason) most optimal seems to be F F and F R.

Remaining questions, what is the effect for the initial position, and is there an (significant) effect when move sorting (history) is used.....

Bert

Interesting... this has more or less the same effect as a static history-table or a piece-square table for move ordering.
I've been thinking about this as well, resetting the MSB takes more time that is why I didn't try it yet, and it is unclear if there is a measurable effect when you have killers and history in place.
Move sorting depends very much upon the position you're looking at, e.g. at the initial position killers hardly do anything and at the Woldouby they do a terrific job (maybe because the position is more tactical).

Today I tried several different ways to sort the root moves, nothing that I tried improved the current move ordering, maybe because I have no real evaluation function besides material yet, I filled the evaluation table with small random values and that clearly has an effect on the branching factor but the results from the sort algorithms I tried remain about the same as with material only.

I guess I have to add speculative pruning and LMR to get a few additional plies, in practice (if done in the right way) this may help somewhat.

In practice the KISS (keep it simple stupid) principle often works best, this is why I'm very reluctant to use stuff from the C++ libraries, there is so much redundant junk in there, lately I also developed the bad habit to use a lot of OOP, most of the time this works against you though.

Joost

[BertTuyt]

Herewith the same test with the initial position, ply 18

Code: Select all

White	Black	Nodes
F		F		223.367.585
R		F		595.532.398
R		R		163.125.282
F		R		111.267.592

Already at low ply it is evident what the default sorting is.
So (but again maybe totally no effect when combined with history and killers), one could do 4 times a normal search (ply 10 example) to find the best mode, and than continue with that.

See below node count at ply 10

Code: Select all

White	Black	Nodes
F		F		101.387
R		F		130.377
R		R		82.678
F		R		57.613

Bert

[Joost Buijs]

Herewith the same test with the initial position, ply 18

Code: Select all

White	Black	Nodes
F		F		223.367.585
R		F		595.532.398
R		R		163.125.282
F		R		111.267.592

Already at low ply it is evident what the default sorting is.
So (but again maybe totally no effect when combined with history and killers), one could do 4 times a normal search (ply 10 example) to find the best mode, and than continue with that.

See below node count at ply 10

Code: Select all

White	Black	Nodes
F		F		101.387
R		F		130.377
R		R		82.678
F		R		57.613

Bert

Out of curiosity I also reversed the scan order of the black men (sliding) move-generator and even with move sorting in place it still helps a bit.
I checked the initial position at depth 20, single core:

Code: Select all

White	Black		Nodes
F		F		104.791.582
F		R		 80.235.604

To compare with your results, at 18 ply it is:

Code: Select all

White	Black		Nodes
F		F		23.219.091
F		R		19.507.080

There is a great difference between our node numbers, I guess this is due to the 4 tier hash-table, killers and history.
With reversed move-generation the speed goes down somewhat, this is expected but overall it seems to help.
I will add it to the code with a conditional and add it to the king and capture generators as well to find out what it does.

Joost

Edit:

I have the feeling that for captures it won't help because they are forced and for king-moves holds the same because they are not color centric.

[Rein Halbersma]

Today I tried several different ways to sort the root moves, nothing that I tried improved the current move ordering, maybe because I have no real evaluation function besides material yet, I filled the evaluation table with small random values and that clearly has an effect on the branching factor but the results from the sort algorithms I tried remain about the same as with material only.

Have you ever tested the following ordering: after hash/killer/history moves, play moves xxxx-FROM and DEST-yyyy if the 2-ply back move was FROM-DEST? I.e., play another move with the piece that the side to move last moved, or play into the hole that this move created. The idea being to close holes in your position.

[Joost Buijs]

Today I tried several different ways to sort the root moves, nothing that I tried improved the current move ordering, maybe because I have no real evaluation function besides material yet, I filled the evaluation table with small random values and that clearly has an effect on the branching factor but the results from the sort algorithms I tried remain about the same as with material only.

Have you ever tested the following ordering: after hash/killer/history moves, play moves xxxx-FROM and DEST-yyyy if the 2-ply back move was FROM-DEST? I.e., play another move with the piece that the side to move last moved, or play into the hole that this move created. The idea being to close holes in your position.

Rein,

No I never tried, it seems like a good idea and not very difficult to implement, maybe I will try this in the future.
The problem is that I never played draughts myself and that I have no clue what might work or not.

Joost

[Rein Halbersma]

Have you ever tested the following ordering: after hash/killer/history moves, play moves xxxx-FROM and DEST-yyyy if the 2-ply back move was FROM-DEST? I.e., play another move with the piece that the side to move last moved, or play into the hole that this move created. The idea being to close holes in your position.

Rein,

No I never tried, it seems like a good idea and not very difficult to implement, maybe I will try this in the future.
The problem is that I never played draughts myself and that I have no clue what might work or not.

Joost

I learned this heuristic from an old version of Stockfish, see viewtopic.php?t=2349&start=19

[Joost Buijs]

I haven't been looking at Stockfish code for ages, do they still use this heuristic in later versions?

Many things that work with chess seem to behave entirely different with draughts, at least that is my experience till now.
I don't think null-move will work because the nature of the game is totally different, one thing I still want to try though is singular extensions but I first have to make a reasonable evaluation function and get the program to play.

Joost

[BertTuyt]

I tried to get some statistiscs related to the (implicit) Move ordening (so based upon the way the moves are stored by the Movegenerator).
A number of parameters were added:

Code: Select all

if (iScore >= iBeta) {
				++iXCutoff;
				iXAMCutoff += i;
				if (i == 0) ++iXFMCutoff;
				break;
			}

So I count the number of Cutoffs (iXCutoff), the Number of Cutoffs for the first Move (iXFMCutoff), and the total movenumber for all cutoffs (iXAMCutoff).
For a perfect ordening I assume iXCutoff == iXFMCutoff and iXAMCutoff == 0 (always cutoff on the first move).

Based upon the initial position, ply 18, I get these numbers (I separated the PVS and Q-Search phase).
Average branchingfactor (BF) is calculated as 1 + iXAMCutoff/iXCutoff

Code: Select all

Phase	iXCutoff	iXFMCutoff	%	Average BF
PVS		 42.510.817	38.933.341	92%	1.2545
Q			34.846.862	34.498.455	99%	1.01048
PVS + Q	77.357.679	73.431.796	95%	1.14457

So far no conclusions, but interesting to look inside the engine, and measure what sorting is doing.
Maybe I made an error somewhere ,as I have no base to compare against.
Curious to see your results Joost...

Bert

[Rein Halbersma]

I haven't been looking at Stockfish code for ages, do they still use this heuristic in later versions?

Many things that work with chess seem to behave entirely different with draughts, at least that is my experience till now.
I don't think null-move will work because the nature of the game is totally different, one thing I still want to try though is singular extensions but I first have to make a reasonable evaluation function and get the program to play.

Joost

I haven't checked Stockfish either for a long time. What I learned from it was not specifically related to LMR or null-moves (and as you can read from the linked thread, I do think that null moves can be effective in draughts!).

It's just the observation that if you have moved A-B, then it's a logical continuation to play B-C or C-A on the next move. Moves like B-C could represent breakthroughs or simple tactics (if they give away a piece, or threaten to capture an opponent piece). Moves like C-A might also be tactics (if they give away a piece) or simply filling the "hole" left on square A during the previous move (making you statistically less vulnerable to counter-tactics).

E.g. in the opening position, you typically move entire diagonals by one square, in move sequences like 32-28 37-32 41-37 46-41. It's actually a 4-step "super move" 46-28. You typically don't play only 32-28 and then an unrelated move at the other side of the board (unless you have nothing useful to do, have to find a tempo to let your opponent capture, or if there is an immediate threat).

I think it was Ed who once wrote that draughts gives you much less information to go on during move ordering. Ordering moves by "distance" with respect to the previous move might be a general principle worthwhile investigating.

[Joost Buijs]

I tried to get some statistiscs related to the (implicit) Move ordening (so based upon the way the moves are stored by the Movegenerator).
A number of parameters were added:

Code: Select all

if (iScore >= iBeta) {
				++iXCutoff;
				iXAMCutoff += i;
				if (i == 0) ++iXFMCutoff;
				break;
			}

So I count the number of Cutoffs (iXCutoff), the Number of Cutoffs for the first Move (iXFMCutoff), and the total movenumber for all cutoffs (iXAMCutoff).
For a perfect ordening I assume iXCutoff == iXFMCutoff and iXAMCutoff == 0 (always cutoff on the first move).

Based upon the initial position, ply 18, I get these numbers (I separated the PVS and Q-Search phase).
Average branchingfactor (BF) is calculated as 1 + iXAMCutoff/iXCutoff

Code: Select all

Phase	iXCutoff	iXFMCutoff	%	Average BF
PVS		 42.510.817	38.933.341	92%	1.2545
Q			34.846.862	34.498.455	99%	1.01048
PVS + Q	77.357.679	73.431.796	95%	1.14457

So far no conclusions, but interesting to look inside the engine, and measure what sorting is doing.
Maybe I made an error somewhere ,as I have no base to compare against.
Curious to see your results Joost...

Bert

Sure, I can add a few counters to keep track of the number of cut-offs.
I have to make it SMP aware otherwise false-sharing will slow down the engine to a crawl when I'm running multiprocessor.

Joost

[BertTuyt]

Joost, thanks, for the first insights, you can also do it in a Q&D (quick and dirty) way, with 1 processor, so we can compare easily.

Bert

[Joost Buijs]

Bert,

Should it not be:

Code: Select all

if (iScore >= iBeta) {
				++iXCutoff;
				iXAMCutoff += i + 1;
				if (i == 0) ++iXFMCutoff;
				break;
			}

Instead of:

Code: Select all

if (iScore >= iBeta) {
				++iXCutoff;
				iXAMCutoff += i;
				if (i == 0) ++iXFMCutoff;
				break;
			}

The branching-factor seems incredibly low to me.

[BertTuyt]

Joost, not sure I dont introduced errors, the output is calculated as follows:

Code: Select all

1.0 + (float)iXAMCutoff/(iXCutoff != 0 ? iXCutoff : 1)

So the +1, I do at the end...

Bert

[Joost Buijs]

Joost, not sure I dont introduced errors, the output is calculated as follows:

Code: Select all

1.0 + (float)iXAMCutoff/(iXCutoff != 0 ? iXCutoff : 1)

So the +1, I do at the end...

Bert

I have to think about it a while, but the branching-factor is exceptionally low, it should be more like 2 or so, maybe we define the branching-factor differently.

Joost

Anyway I can temporary add counters to give you a comparison.

Here it is at 18 ply:

Code: Select all

pvs     3729873  3693240  99 %  1.017
qs      2886569 2873104  100 %  1.005
pvs+qs  6616442  6566344  99 %  1.012

When I add random values to the evaluation table it looks more like your results:

Code: Select all

pvs     34336742  31314861  91 %  1.281
qs      32816278 32146173  98 %  1.021
pvs+qs  67153020  63461034  95 %  1.154

[BertTuyt]

Joost, it could be that I made an error.
On the other hand, it is good to get into the search details.
Very simplified view, if you go 18 ply deep, I expect 9 levels of cutnodes, and 9 levels of all nodes.

So if the cutnodes have branching factor 1, and the allnodes 9 (the normal average), the number of nodes would be something like 387M.
If the branching factor for the cutnodes is 2, this yields 198B.

So I expect that a cutnodes should be close to 1.
But as expressed, not sure if there is a flaw in my reasoning.

Bert