Search Algorithm

[Joost Buijs]

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

Bert,

It is not straightforward to calculate the branching factor for an alpha-beta pruned tree.
You can estimate it with sqrt(nodes depth n) / (nodes depth n - 2) or something like all-nodes / terminal-nodes;
When I look at the output of my program, the number of nodes approx. doubles each iteration, so I assume a branching-factor of 2 or thereabout.

Joost

[BertTuyt]

Joost, thanks.

I know it is not straightforward, but I also did not 100% understand the output.
So there are certainly errors, and / or mistakes, and we will find them.
On the other hand, it would be nice to have a metric for the quality of the sorting , and more insights what happens at a cut node ..

Bert

[Joost Buijs]

Joost, thanks.

I know it is not straightforward, but I also did not 100% understand the output.
So there are certainly errors, and / or mistakes, and we will find them.
On the other hand, it would be nice to have a metric for the quality of the sorting , and more insights what happens at a cut node ..

Bert

The assumption that on a cut-node the first move will always be a cut-off is probably wrong.

It is also very interesting to know why my move-ordering with material only is almost optimal and after I add random values to the pattern evaluation table it looks more like your results. I count men = 100 and kings = 320 just like you, so I really don't understand what the difference is.

Joost

[BertTuyt]

Joost, an easy way to test some assumptions, is to start with a board position with 5 black pieces on 1-5, and 5 white pieces on 46-50.
At least for the first 7 plies, there shouldnt be captures, and the branching factor is more or less constant.
If all evals are 0, than you should have a minimal tree.
Than you can measure the behavior for the cut nodes, and i assume that all cut nodes have a branching factor of 1.

Bert

[Joost Buijs]

Joost, an easy way to test some assumptions, is to start with a board position with 5 black pieces on 1-5, and 5 white pieces on 46-50.
At least for the first 7 plies, there shouldnt be captures, and the branching factor is more or less constant.
If all evals are 0, than you should have a minimal tree.
Than you can measure the behavior for the cut nodes, and i assume that all cut nodes have a branching factor of 1.

Bert

You can let you evaluation function always return zero, then you will get the same situation.
Node-types are very much interleaved especially when you start with things like null-window search and forward pruning, in practice I never found any value in using node-types.
I tried splitting only on ALL nodes for my SMP search (which seems theoretically sound), but in practice things like this don't work at all.

Joost

[BertTuyt]

See below code (no tested for errors yet) for a minimal tree, and which provides Node info.

Code: Select all

// MT.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#define PVNODE	0
#define ALLNODE	1
#define CUTNODE	2
#define TNODE	3

#define FBRANCH	9

int iXPNode, iXANode, iXCNode, iXTNode;

bool MT(int iDepth, int iNode)
{
	int iXBranch, iNextNode;

	if (iDepth == 0) {
		++iXTNode;
		return (true);
	}

	if (iNode == PVNODE) {
		++iXPNode;
		iNextNode = PVNODE;
	} else if (iNode == ALLNODE) {
		++iXANode;
		iNextNode = CUTNODE;
	} else if (iNode == CUTNODE) {
		++iXCNode;
		iNextNode = ALLNODE;
	}
	
	if (iNode == CUTNODE)
		iXBranch = 1;
	else
		iXBranch = FBRANCH;

	for (int i = 1; i <= iXBranch; i++) {

		MT(iDepth - 1, iNextNode);

		if (i == 1 && iNode == PVNODE) iNextNode = CUTNODE;
	}

	return (true);
}

int main()
{

	for (int iDepth = 1; iDepth <= 8; iDepth++) {

		iXPNode = 0;
		iXANode = 0;
		iXCNode = 0;
		iXTNode = 0;

		MT(iDepth, PVNODE);

		printf("Depth = %d, P A C T = %d %d %d %d\n", iDepth, iXPNode, iXANode, iXCNode, iXTNode);
	}

    return 0;
}

The output for a branching factor of 9:

Code: Select all

Depth = 1, P A C T = 1 0 0 9
Depth = 2, P A C T = 2 0 8 17
Depth = 3, P A C T = 3 8 16 89
Depth = 4, P A C T = 4 16 96 161
Depth = 5, P A C T = 5 96 176 809
Depth = 6, P A C T = 6 176 904 1457
Depth = 7, P A C T = 7 904 1632 7289
Depth = 8, P A C T = 8 1632 8192 13121
Press any key to continue . . .

For a minimal tree the theoretical number of terminal nodes is 2 * (Branching-Factor ^ (Depth / 2)) -1.

In case branching factor is 9 and depth is 8 this yields 2 * (9 ^ 4) - 1 = 13121.

For a minimal tree the branching factor at cut nodes = 1.

Bert

[BertTuyt]

Joost, you are right when you start mixing than things become hyper complicated.
The only thing I wanted to understand (before entering into optimizations) is how to improve sorting, with no or limited sorting.
And how good the sorting already was.
That was the reason I examined the behavior of cut-nodes.
Most likely with your sorting you are at a 99% level.
In general I think (at least for me) what is really hapening underneath the alpha-beta framework is often black magic.

Bert

[Joost Buijs]

Bert,

Strange, I did post a reply but somehow it disappeared.

You are completely right that in a minimal tree the branching-factor for CUT-nodes will be 1.
I was thinking and talking about the average branching-factor, this is why I didn't understand the low figures.

Joost

[BertTuyt]

I realized that my (implicit) movesort was still a little non-optimal, as I used 2 while loops for the 2 man directions.
So basically the movelist is devided in 2 ordered part.
I changed this, and now have a full ordening (only based upon BITSCANFORWARD and BITSCANREVERSE).
See code:

Code: Select all

//	WhiteMan Move
	BITBOARD bbWhiteManMove0 = DBR(bbEmpty) & (bbWhitePiece & ~bbKing);
	BITBOARD bbWhiteManMove1 = DBL(bbEmpty) & (bbWhitePiece & ~bbKing);
	BITBOARD bbWhiteManMove = bbWhiteManMove0 | bbWhiteManMove1;

	while (bbWhiteManMove) {

//		bbPosition = bbWhiteManMove & (~bbWhiteManMove + 1);

		DWORD dPosition;
		BITSCANREVERSE64(&dPosition, bbWhiteManMove);
		bbPosition = (BITBOARD)1 << dPosition;
		bbWhiteManMove ^= bbPosition;

		if (bbWhiteManMove0 & bbPosition) {

			bbToPosition = DFL(bbPosition);

			rlsp->bbField[BB_WHITEPIECE] = bbWhitePiece ^ (bbPosition ^ bbToPosition);
			rlsp->bbField[BB_BLACKPIECE] = bbBlackPiece;
			rlsp->bbField[BB_KING] = bbKing | (bbToPosition & DFLD_PROMOTION_WHITE);

			++iXMoves;
			++rlsp;
		}

		if (bbWhiteManMove1 & bbPosition) {

			bbToPosition = DFR(bbPosition);

			rlsp->bbField[BB_WHITEPIECE] = bbWhitePiece ^ (bbPosition ^ bbToPosition);
			rlsp->bbField[BB_BLACKPIECE] = bbBlackPiece;
			rlsp->bbField[BB_KING] = bbKing | (bbToPosition & DFLD_PROMOTION_WHITE);

			++iXMoves;
			++rlsp;
		}
	}

See below results (initial position, ply 18), especially RF is remarkably good...

Code: Select all

White	Black	Nodes
F		F		91.273.098
R		F		39.647.801
R		R		111.531.649
F		R		354.097.675

EDIT:
And for the RF 12.422.090 Cutoff Nodes, 12.155.591 Cutof First Move ( 98%), and average cutoff move 1.048

Bert

[BertTuyt]

Also for the Woldouby position 25 ply.
The first number is the first implementation, the second the new man-order.

Code: Select all

White	Black	Nodes Old	Nodes New	FM%		FA
F		F		150.967.354	197.934.176	91%		1.25
R		F		342.237.097	655.874.355	82%		1.54
R		R		345.962.328	434.304.558	87%		1.36
F		R		160.613.611	178.325.177	93%		1.15

Although not an overall improvement, the same overall trend (here most important F for White), and a good correlation between nodes, FM% and FA.

Bert

[Joost Buijs]

I realized that my (implicit) movesort was still a little non-optimal, as I used 2 while loops for the 2 man directions.
So basically the movelist is devided in 2 ordered part.
I changed this, and now have a full ordening (only based upon BITSCANFORWARD and BITSCANREVERSE).

Bert

Well, I did exactly the same here, I added 3 functions for the reverse direction, note that the MSB() is actually not needed:

Code: Select all

// get most significant bit-number
inline uint MSB(bb_t bb)
{
	return 63 - static_cast<uint>(_lzcnt_u64(bb));
}

// get most significant bit
inline bb_t BMSI(bb_t bb)
{
	return 0x8000000000000000 >> _lzcnt_u64(bb);
}

// reset most significant bit
inline void RMSB(bb_t &bb)
{
	bb ^= BMSI(bb);
}

And after that I changed the move-generator:

Code: Select all

void movegen_c::gen_man_sliders()
{
	if (own == White)
	{
		for (bb_t from_bb = pos->men(own) & pos->empty() << 6; from_bb; RLSB(from_bb))
			store(ptop, BLSI(from_bb), BLSI(from_bb) >> 6);
		for (bb_t from_bb = pos->men(own) & pos->empty() << 5; from_bb; RLSB(from_bb))
			store(ptop, BLSI(from_bb), BLSI(from_bb) >> 5);
	}
	else
	{
		//for (bb_t from_bb = pos->men(own) & pos->empty() >> 5; from_bb; RLSB(from_bb))
			//store(ptop, BLSI(from_bb), BLSI(from_bb) << 5);
		//for (bb_t from_bb = pos->men(own) & pos->empty() >> 6; from_bb; RLSB(from_bb))
			//store(ptop, BLSI(from_bb), BLSI(from_bb) << 6);

		for (bb_t from_bb = pos->men(own) & pos->empty() >> 5; from_bb; RMSB(from_bb))
			store(ptop, BMSI(from_bb), BMSI(from_bb) << 5);
		for (bb_t from_bb = pos->men(own) & pos->empty() >> 6; from_bb; RMSB(from_bb))
			store(ptop, BMSI(from_bb), BMSI(from_bb) << 6);
	}
}

It decreases the number of nodes by ~20% and it has very little impact on speed so I will leave it in.

As you will probably notice I use separate loops for each direction and I do some redundant shifts, but for clarity of the code I will leave it like it is. Nowadays the optimizers are so smart that there is a big change the redundancy is removed anyway.

Joost

[TAILLE]

Hi,

I have just made a tuning work on my new algorithm in order to optimize one of the major parameters of my algorithm. The gain is very substantial:


White to play

Damy is now able to prove the loss in less than 1'30" (with the relevant egdb already in cache!)

Comparing with my previous PV the change occur at the move 15:
1.35-30 24x35 2.28-22 23-28 3.32x12 21x41 4.12-7 19-23 5.7-1 41-46 6.1x29 46-28 7.38-32 28x6 8.29-1 6-17 9.32-27 17-3 10.1-7 3-21
11.27-22 26-31 12.7-23 21-8 13.23-7 13-19 14.33-28 31-36 15.7-29 ... because on 15.7-23 Damy plays now 15...8-13 instead of 15...8-3

[TAILLE]

Hi,

The same position but Black to play is also a losing position but far easier to analyse.


Black to play

Damy proves the loss in 5" (always with the relevant egdb already in cache).

[TAILLE]

Hi,

The same position but Black to play is also a losing position but far easier to analyse.


Black to play

Damy proves the loss in 5" (always with the relevant egdb already in cache).

BTW, with only the 7p db it is far more difficult and Damy needs almost 8' to prove the loss.

[Rein Halbersma]

Hi,

The same position but Black to play is also a losing position but far easier to analyse.


Black to play

Damy proves the loss in 5" (always with the relevant egdb already in cache).

BTW, with only the 7p db it is far more difficult and Damy needs almost 8' to prove the loss.

OK, now that the magic tricks have been shown, how about a little explanation of the methods that you use?