Multi-cut prunning

[Alvaro]

Hi erveryone

This is my first post here, I didn't know about the existence of this forum untill a few days ago.
I program only the spanish/portuguese variant of draughts (8x8, flying kings, men can't capture backwards).
I would like to ask if someone could explain with pseudo code the implementation of MCP.
I saw the link: http://chessprogramming.wikispaces.com/Multi-Cut
but I didn't understand why in the all moves cycle, the "cut" variable is set to "!cut",
so zwSearch() is allways called with "!cut".
Could you also please say wich conditions/parmeters you use to activate MPC?
For example, do you use MCP if:
- current node is a pv node
- beta is a winning/loosing score
- current node has captures and/or promotions
- minimum depth,
and wich reduction to use (2 ply)?

best regards,
Alvaro

[Rein Halbersma]

Hi erveryone

This is my first post here, I didn't know about the existence of this forum untill a few days ago.
I program only the spanish/portuguese variant of draughts (8x8, flying kings, men can't capture backwards).
I would like to ask if someone could explain with pseudo code the implementation of MCP.
I saw the link: http://chessprogramming.wikispaces.com/Multi-Cut
but I didn't understand why in the all moves cycle, the "cut" variable is set to "!cut",
so zwSearch() is allways called with "!cut".
Could you also please say wich conditions/parmeters you use to activate MPC?
For example, do you use MCP if:
- current node is a pv node
- beta is a winning/loosing score
- current node has captures and/or promotions
- minimum depth,
and wich reduction to use (2 ply)?

best regards,
Alvaro

Hi Alvaro, and welcome to this forum!

As is explained in the Chess Programming Wiki, Multi-Cut is only applied at Cut nodes. And also remember that the children of a Cut node are All nodes, and vice versa. Therefore, the parameter "cut" is alternating its sign depending whether the node type is Cut or All.

The parameters you mention as Multi-Cut pre-conditions, all make sense to me, and it's a matter of tuning and testing to get them right.

Rein

[BertTuyt]

Alvara, also welcome to this forum.

I agree with he post of Rein.
MCP is applied on expected cut nodes and only applied in the zero-window search part of the search.
Therefore the alternate between ALL-nodes and CUT nodes ( !cut).
MCP is never applied at PV nodes.
In a later stage MCP was also applied at ALL nodes, and some improvement was claimed over the "orginal use" in expected CUT nodes only.

In the case of Damage/Horizon I apply a depth-reduction factor ( SEARCH_MCP_DEPTHREDUCTIONFACTOR ) of 3 ply
and I claim a cutoff if 2 ( SEARCH_MCP_CHILD_BETACUTOFF ) children produce a (reduced) search score greater/equal beta.
I only apply MCP when the newdepth > SEARCH_MCP_DEPTHREDUCTIONFACTOR , which in my case is 3 ply.

Below the code:

Code: Select all

	//	Multi Cut Pruning (only in non_PV Nodes )
	if ( pEngineData->bMCP && ( pTDepth->bPV == false ) && ( iNewDepth > pEngineData->iMCP_DepthReductionFactor ) && ( iXMoves >= pEngineData->iMCP_Child_Search ) )
		if ( PPMulti_Cut_Pruning(iSearchThreadID, iNewDepth, iHashMove, iAlfa, iBeta, pTDepth, pEngineData, bTurn) ) {
			SearchReturn(pTDepth, pSearchThreadData) ; 
			return ( iBeta ) ;
		}

Hope this helps,

Bert