Author: Dann Corbit
Date: 14:32:21 05/17/01
Go up one level in this thread
On May 17, 2001 at 17:09:47, David Rasmussen wrote:
>On May 17, 2001 at 16:32:01, Jesper Antonsson wrote:
>
>>>But given those algorithms, specialized for chess, I would like for you to show
>>>me one that is O(1). You haven't yet.
>>
>>Take a look at Crafty, for example, it has available source code.
>
>It isn't a chess algorithm. It is a couple of algorithms coupled with some code
>to describe the input to these algorithms. The algorithms themselves are
>exponential. The runtime of the entire program is O(1).
Depends on what you are doing. The entire program runs as a function of depth
if I want it to, in which case the behavior is O(exp(depth)). For instance:
E:\crafty\release>crafty1immx
EPD Kit revision date: 1996.04.21
unable to open book file [e:\crafty\release/books.bin].
hash table memory = 48M bytes.
pawn hash table memory = 10M bytes.
EGTB cache memory = 64M bytes.
draw score set to 0.00 pawns.
choose from book moves randomly (using weights.)
choose from 5 best moves.
book learning enabled
result learning enabled
position learning enabled
threshold set to 9 pawns.
5 piece tablebase files found
20258kb of RAM used for TB indices and decompression tables
Crafty v18.9
White(1): st 99999999999999
search time set to 18749193.24.
White(1): sd 9999
search depth set to 9999.
White(1): book off
book file disabled.
White(1): go
clearing hash tables
time surplus 0.00 time limit 312486:33 (312486:33)
nss depth time score variation (1)
7 0.30 -0.04 1. e3 d5 2. Nc3 Nc6 3. Nf3 Nf6 4. Bb5
7 0.35 -0.01 1. d3 Nc6 2. Nf3 e5 3. Nc3 Nf6 4. e4
7 0.40 0.00 1. Nc3 d5 2. Nf3 Nc6 3. d3 e5 4. Bg5
<HT>
7 0.44 0.01 1. Nf3 d5 2. d3 Nc6 3. Bf4 Nf6 4. Nc3
<HT>
7-> 0.45 0.01 1. Nf3 d5 2. d3 Nc6 3. Bf4 Nf6 4. Nc3
<HT>
8 0.52 -0.19 1. Nf3 d5 2. d3 Nc6 3. Bf4 Nf6 4. Nc3
Bf5
8 0.81 -0.13 1. e4 Nc6 2. Nf3 Nf6 3. Nc3 d5 4. exd5
Nxd5 5. Bc4
8-> 1.01 -0.13 1. e4 Nc6 2. Nf3 Nf6 3. Nc3 d5 4. exd5
Nxd5 5. Bc4
9 2.12 -0.09 1. e4 e6 2. Nf3 d5 3. e5 Nc6 4. Nc3
Bc5 5. d3
9 2.44 -0.08 1. e3 Nc6 2. Nc3 d5 3. Nf3 Nf6 4. Bb5
a6 5. Bxc6+ bxc6 6. O-O
9 2.84 -0.01 1. Nf3 Nf6 2. Nc3 d5 3. d3 Nc6 4. Bf4
Bf5 5. e3 <HT>
9-> 3.00 -0.01 1. Nf3 Nf6 2. Nc3 d5 3. d3 Nc6 4. Bf4
Bf5 5. e3 <HT>
10 3.63 -0.17 1. Nf3 Nf6 2. Nc3 d5 3. d4 e6 4. Bf4
Nc6 5. Ne5 Bb4 6. Nxc6 bxc6
10 5.85 -0.15 1. e4 Nc6 2. Nf3 e6 3. d4 d5 4. Bd3
dxe4 5. Bxe4 Bb4+ 6. c3 Bd6
10-> 7.51 -0.15 1. e4 Nc6 2. Nf3 e6 3. d4 d5 4. Bd3
dxe4 5. Bxe4 Bb4+ 6. c3 Bd6
11 11.52 0.00 1. e4 Nc6 2. Nf3 e6 3. Nc3 Nf6 4. Bd3
Bb4 5. a3 Bc5 6. O-O
11-> 12.46 0.00 1. e4 Nc6 2. Nf3 e6 3. Nc3 Nf6 4. Bd3
Bb4 5. a3 Bc5 6. O-O
12 32.81 -0.03 1. e4 e5 2. Nf3 Nf6 3. Nc3 Nc6 4. Bb5
Nd4 5. Bc4 d6 6. O-O Bg4
12-> 44.28 -0.03 1. e4 e5 2. Nf3 Nf6 3. Nc3 Nc6 4. Bb5
Nd4 5. Bc4 d6 6. O-O Bg4
13 1:47 0.08 1. e4 Nc6 2. Nf3 Nf6 3. e5 Nd5 4. Nc3
e6 5. Nxd5 exd5 6. d4 d6 7. Bg5 Be7
13-> 1:51 0.08 1. e4 Nc6 2. Nf3 Nf6 3. e5 Nd5 4. Nc3
e6 5. Nxd5 exd5 6. d4 d6 7. Bg5 Be7
14 3:19 0.02 1. e4 Nc6 2. Nf3 Nf6 3. e5 Ng4 4. d4
d5 5. Nc3 e6 6. Bg5 Be7 7. Bxe7 Nxe7
8. Bd3
14-> 3:57 0.02 1. e4 Nc6 2. Nf3 Nf6 3. e5 Ng4 4. d4
d5 5. Nc3 e6 6. Bg5 Be7 7. Bxe7 Nxe7
8. Bd3
...
Anybody notice a pattern as we go from completed ply to completed ply? I would
have to alter the code a bit to use 64 bit integers for the timer if I wanted to
make it search until the transistors in my computer died, but that would be a
fairly trivial change. The timer overrides the depth.
>But since that always
>hold, for any program that terminates, it bears no valuable meaning.
Look, he's obviously a smart person, and just having some fun yanking our chain
at this point. I am absolutely sure he understands the argument and just wants
to have a bit of fun trolling.
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.