Code: Select all
function PVS(n,d,alpha,beta)
S = Successors(n)
if d <= 0 OR S == {} then
return f(n)
best = -PVS(n1 an element of S, d-1, -beta, -alpha)
for ni an element of S such that i > 1 do
if best >= beta then
return best
alpha = max(alpha, best)
v = -NWS(ni, d-1, -alpha)
if v > alpha AND v < beta then
v = -PVS(ni, d-1, -beta, -v)
if v > best then
best = v
return best
function NWS(n,d,beta)
S = Successors(n)
if d <= 0 OR S = {} then
return f(n)
best = -INFINITY
for all ni an element of S do
v = -NWS(ni, d-1, -beta + epsilon)
if v > best then
best = v
if best >= beta then
return best
return best
I type in the above algorithm (well, actually, I use a slightly modified version, which appears here on the chess programming wiki) and run it a few thousand times to test it, and I see that it always returns the correct minimax score for any given position and collects either an identical PV to a standard AB implementation, or a different PV but with the exact same minimax score.
My concern is the time required to run the algorithm. I have a chess engine that I have written which contains many, many variants of each of the popular search algorithms. For example, I can run AB and then run AB + iterative deepening + insert the PV of the previous iteration as the first variation to try + killer moves + move sorting (winning captures first, etc).
When I run these on the opening chess position, I see this:
(My code for negamax AB, capture the PV, use iterative deepening, do move sorting, collect and use killer moves)
Code: Select all
best_move_nabcpv_id_ms_killer(...) called with depth = 6
About to start iterative deepening...
Depth = 1, Number of evaluations: 20
Depth = 1
PV length = 1
PV =
Move: WKnight b1 -> c3
Depth = 2, Number of evaluations: 48
Depth = 2
PV length = 2
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Depth = 3, Number of evaluations: 707
Depth = 3
PV length = 3
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Move: WKnight g1 -> f3
Depth = 4, Number of evaluations: 1,902
Depth = 4
PV length = 4
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Move: WKnight g1 -> f3
Move: BKnight g8 -> f6
Depth = 5, Number of evaluations: 53,625
Depth = 5
PV length = 5
PV =
Move: WPawn e2 -> e4
Move: BKnight b8 -> c6
Move: WBishop f1 -> b5
Move: BKnight c6 -> d4
Move: WBishop b5 -> d7
Depth = 6, Number of evaluations: 677,091
Depth = 6
PV length = 6
PV =
Move: WPawn e2 -> e3
Move: BPawn e7 -> e5
Move: WKnight g1 -> e2
Move: BBishop f8 -> b4
Move: WPawn e3 -> e4
Move: BBishop b4 -> d2
Number of evaluations: 733,393
Best move: WPawn e2 -> e3
Score: -945.000
Elapsed time: 4.006 seconds
Evaluations per second: 183,066
Code: Select all
best_move_npvs_nws_cpv_ms_killer(...) called with depth = 6
About to start iterative deepening...
Depth = 1, Number of evaluations: 1,919,912
Depth = 1
PV length = 6
PV =
Move: WPawn e2 -> e3
Move: BPawn e7 -> e5
Move: WKnight g1 -> e2
Move: BBishop f8 -> b4
Move: WPawn e3 -> e4
Move: BBishop b4 -> d2
Number of evaluations: 1,919,912
Best move: WPawn e2 -> e3
Score: -945.000
Elapsed time: 10.406 seconds
Evaluations per second: 184,497
Code: Select all
best_move_npvs_nws_cpv_id_ms_killer(...) called with depth = 6
About to start iterative deepening...
Depth = 1, Number of evaluations: 23
Number of unique evaluations: Searched 20 unique positions
FWS evaluations: 4
ZWS evaluations: 19
Depth = 1
PV length = 1
PV =
Move: WKnight b1 -> c3
Depth = 2, Number of evaluations: 97
Number of unique evaluations: Searched 94 unique positions
FWS evaluations: 4
ZWS evaluations: 93
Depth = 2
PV length = 2
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Depth = 3, Number of evaluations: 907
Number of unique evaluations: Searched 904 unique positions
FWS evaluations: 4
ZWS evaluations: 903
Depth = 3
PV length = 3
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Move: WKnight g1 -> f3
Depth = 4, Number of evaluations: 4,954
Number of unique evaluations: Searched 4266 unique positions
FWS evaluations: 4
ZWS evaluations: 4950
Depth = 4
PV length = 4
PV =
Move: WKnight b1 -> c3
Move: BKnight b8 -> c6
Move: WKnight g1 -> f3
Move: BKnight g8 -> f6
Depth = 5, Number of evaluations: 298,875
Number of unique evaluations: Searched 159,718 unique positions
FWS evaluations: 5254
ZWS evaluations: 293621
Depth = 5
PV length = 5
PV =
Move: WPawn e2 -> e4
Move: BKnight b8 -> c6
Move: WBishop f1 -> b5
Move: BKnight c6 -> d4
Move: WBishop b5 -> d7
Depth = 6, Number of evaluations: 2,528,551
FWS evaluations: 43153
ZWS evaluations: 2485398
Depth = 6
PV length = 6
PV =
Move: WPawn e2 -> e3
Move: BPawn e7 -> e5
Move: WKnight g1 -> e2
Move: BBishop f8 -> b4
Move: WPawn e3 -> e4
Move: BBishop b4 -> d2
Number of evaluations: 2,833,407
Best move: WPawn e2 -> e3
Score: -945.000
Elapsed time: 15.060 seconds
Evaluations per second: 188,141
My question is, is there anything I can do in the NWS to reduce the number of evaluations? I know I can add a null move heuristic, I can further add a forward pruning mechanism such as multi-cut, and I can further add transposition tables to speed up searches of positions that have been previously evaluated using the evaluation function.
But can I perform move ordering inside the NWS to any benefit? It seems that, by definition, I cannot use the PV of the previous iteration inside the NWS, since the PV is searched in the full-width recursive call to PVS. I can clearly do some sort of move sorting (winning captures first, for example). Perhaps I can also do killer moves (I haven't looked at doing killer moves inside the NWS carefully as yet, however). Perhaps I could also do some type of iterative deepening (is this what is meant by "internal" iterative deepening?).
Is there some other move ordering option or something else outside of null-move, multi-cut and/or transposition tables that could be added to the NWS that would improve execution time significantly? I'm also aware of Extended Futility Pruning but haven't even started reading that paper yet.
Thank you very kindly,
Rob