佳佳象棋 2007-6-23 13:36
Slight enhancement to PVS
[url=http://wbforum.vpittlik.org/viewtopic.php?t=6558]http://wbforum.vpittlik.org/viewtopic.php?t=6558[/url]
[table=98%][tr][td=2,1][/td][/tr][tr][td=2,1][size=2]Here's a small analysis of zero window searches and perhaps a slight enhancment to PVS as well. Here's a slightly unconventional node type classification I use for imperfectly ordered trees:
[/size][table=90%][tr][td][b]Code:[/b][/td][/tr][tr][td]OPEN Nodes
----------
The root node is an OPEN node.
All children of OPEN nodes are an OPEN nodes.
An OPEN node changes to an ALL node when alpha is raised.
ALL Nodes
---------
All children of ALL nodes are CUT nodes.
An ALL node changes an OPEN node when the scout search fails high.
(will define "scout search" later)
CUT Nodes
---------
The first child of a CUT node is an ALL node.
A CUT node changes to an ALL node when the first move fails low.
Notes:
======
Parallelism isn't good on OPEN nodes because there is too much search overhead for the current window. It is very likely that the window will be smaller at a later time and that parallel search should wait until the window is smaller.
Parallelism isn't good on CUT nodes because there is too much search overhead because one of the moves will cutoff the search.
Parallelism is possible only on ALL nodes.[/td][/tr][/table]
[size=2]Basically from the definitions, on OPEN nodes we know that a move will at a later time will likely increase alpha. On CUT nodes we know that the first move will likely cause a cutoff. On ALL nodes it is likely that all the moves will fail low. So basically just like in PVS we can do a "scout search" that tests only for the fail high or fail low and does a research of the move as an OPEN node if it doesn't:
[/size][table=90%][tr][td][b]Code:[/b][/td][/tr][tr][td]a=alpha=lowerbound
b=beta=upperbound
On OPEN nodes search normally.
On nodes with a == b+1 search normally.
ALL Nodes:
Because ALL nodes are expected to fail low, all you need to do is prove the fail low so you can do a scout search on all moves assuming the current window is (a,a+1). If it fails high the node type changes to OPEN and you do a research.
CUT Nodes:
You always enter a CUT node in a zero window because it always succeeds an ALL node and scout search is done for all moves in an ALL node. And from the above conditions for zero windows, you always do a normal search on CUT nodes.[/td][/tr][/table]
[size=2]Note this is identical to PVS in every manner except in how the research is handled. For the research, if the PV doesn't increase alpha, the node remains an OPEN node. PVS assumes that it becomes an ALL node which I think is a slight inefficiency because our scout search asserts that one of the lines [i]will[/i] increase alpha except in the case of search instability...
[/size][table=90%][tr][td][b]Code:[/b][/td][/tr][tr][td]#define OPEN_NODE 0
#define CUT_NODE 1
#define ALL_NODE 2
int childNodeType(const int previous_type)
{
switch(previous_type)
{
case ALL_NODE: return CUT_NODE;
case CUT_NODE: return ALL_NODE;
default: return OPEN_NODE;
}
}
int alphabeta(int depth, int alpha, int beta, int p_nodeType)
{
int score = -MATE;
int nodeType = childNodeType(p_nodeType);
//Depth=0, Game decidable recognizers, Hashtables,
//Mate-distance pruning for beta only, Nullmove, stuff...
for( /* every move m */ )
{
int tempscore;
int lowerbound = max(alpha,score);
<makemove m>
//a CUT_NODE always has a zero window
if(lowerbound+1==beta || nodeType==OPEN_NODE)
tempscore = -alphabeta(depth-1, -beta, -lowerbound, nodeType);
else /* Node is a non-zero window ALL node */
{
tempscore = -alphabeta(depth-1, -(lowerbound+1), -lowerbound, nodeType);
if(tempscore > lowerbound && tempscore < beta)
{
nodeType = OPEN_NODE;
tempscore = -alphabeta(depth-1, -beta, -(tempscore-1), nodeType);
}
}
<unmakemove m>
if(nodeType == CUT_NODE && tempscore<beta)
nodeType = ALL_NODE;
if(tempscore>score)
{
score = tempscore;
if(score >= beta)
return score;
if(score > alpha)
{
if(nodeType == OPEN_NODE)
nodeType = ALL_NODE;
}
}
}
return score;
}[/td][/tr][/table]
[size=2]Quick Benchmarks on a P4 2.8 Ghz with 64MB hash: [/size][/td][/tr][/table]