Author: Dann Corbit
Date: 06:48:16 02/04/03
Go up one level in this thread
On February 04, 2003 at 09:08:50, Mike Carter wrote:
>Dann - thanks for your reply. I've seen most of these articles before and I'll
>read them again. What I was hoping to get was a one-paragraph explanation of
>how to implement the alpha/beta concept... specifically, when/how often does the
>evaluate routine get called? I saw a program that, for 4 ply, was analyzing
>8K-10K total nodes.
The node count will be purely a function of the position. If you have 4 forced
plies in a row, the node count may be 4. If you have 7 very active queens in a
row, quiescence may explode it.
> Logically this seems impossible to me (to be able to prune
>the move tree that much).
There is no limit to how many moves you can prune, unless you get down to 4
nodes for 4 plies. The hard part is finding the right balance.
If your move ordering is perfect in alpha-beta, it will reduce the nodes to
sqrt(nodes) if it is the worst possible move ordering. So move ordering is
terribly important.
If you use null move, that adds another huge boots. You might save a lot of
nodes with the hash table. You won't need to evaluate any transpositions.
Here is the output of Crafty from the opening position with a depth of 4:
Black(1): book off
book file disabled.
Black(1): new
White(1): sd 4
search depth set to 4.
White(1): noise 1
noise level set to 1.
White(1): go
time surplus 0.00 time limit 30.00 (3:30)
depth time score variation (1)
1 0.04 0.11 1. Nf3
1 0.06 0.25 1. e4
1-> 0.10 0.25 1. e4
2 0.13 -- 1. e4
2 0.16 -0.19 1. e4 d5
2-> 0.20 -0.19 1. e4 d5
3 0.22 0.05 1. e4 d5 2. Nc3 dxe4 3. Nxe4
3 0.26 0.11 1. Nf3 d5 2. d4
3-> 0.29 0.11 1. Nf3 d5 2. d4
4 0.32 -0.19 1. Nf3 d5 2. d4 Nf6
4-> 0.36 -0.19 1. Nf3 d5 2. d4 Nf6
time=0.38 cpu=5% mat=0 n=1961 fh=87% nps=5k
ext-> chk=15 cap=9 pp=0 1rep=0 mate=0
predicted=0 nodes=1961 evals=1163
endgame tablebase-> probes done=0 successful=0
1961 nodes.
Here is Quark 176b:
go
1 15 0 2 g1h3!
1 39 5 4 g1f3!
1 42 8 13 d2d4!
1 42 11 23 d2d4
2 9 14 27 d2d4?
2 0 17 49 d2d4 d7d5
2 0 20 127 d2d4 d7d5
3 31 25 175 d2d4!
3 39 29 228 d2d4 d7d5 g1f3
3 42 32 652 e2e4!
3 42 36 840 e2e4 e7e5 f1c4
4 9 39 908 e2e4?
4 9 43 1493 e2e4 e7e5 f1c4 b8c6
4 9 47 2193 e2e4 e7e5 f1c4 b8c6
2193 nodes. Very similar.
>I'll sift through the websites you sent, and
>hopefully I'll stumble across something that turns on the light bulb for me.
>Thanks again Dann!
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.