Author: Steve Maughan
Date: 08:10:25 02/09/02
I'm trying to implement hash tables in Monarch and would appreciate some
assistance or insight. Monarch seems to be experiencing severe search
instability when there is a possible mate. The problem is so bad that it solved
*fewer* WACs with hash tables turned on compared to off!!
e.g. WAC 276
[d]r5k1/pp1RR1pp/1b6/6r1/2p5/B6P/P4qPK/3Q4 w - -
In this position Qd5+ wins for white. With hash tables disabled the problem is
solved by Monarch in <1 sec
2.01 0:00 -M1 1.Re1 Qxg2+ (56) 5.6
2.02 0:00 -M2++ 1.Re2 (109) 10.9
2.02 0:00 -9.05 1.Re2 Rxg2+ (163) 16.3
2.07 0:00 -7.97++ 1.Re8+ (193) 9.6
2.07 0:00 -7.97 1.Re8+ Rxe8 (198) 9.9
2.08 0:00 -6.97++ 1.Rxg7+ (201) 6.7
2.08 0:00 -6.97 1.Rxg7+ Rxg7 (206) 6.8
2.26 0:00 -6.74++ 1.Qg4 (427) 10.6
2.26 0:00 -6.74 1.Qg4 Rxg4 (490) 9.8
3.01 0:00 -5.74++ 1.Qg4 (875) 14.5
3.01 0:00 -5.74 1.Qg4 Rxg4 2.hxg4 (1.146) 19.1
4.01 0:00 -7.27-- 1.Qg4 (2.093) 23.2
4.01 0:00 -12.44 1.Qg4 Rxg4 2.Re8+ Rxe8 (2.572) 28.5
4.02 0:00 -6.64++ 1.Rxg7+ (2.577) 28.6
4.02 0:00 -5.92 1.Rxg7+ Rxg7 2.Qd5+ Kh8 (2.858) 28.5
5.01 0:00 -5.88 1.Rxg7+ Rxg7 2.Qd5+ Rf7 3.Qxc4 (6.042) 46.4
6.01 0:00 -5.78 1.Rxg7+ Rxg7 2.Qd5+ Rf7 3.Qxc4 Qg1+ (18.825) 93.6
7.01 0:00 -4.84++ 1.Rxg7+ (61.705) 175.7
7.01 0:00 -5.60-- 1.Rxg7+ (69.963) 183.6
7.01 0:00 -4.84++ 1.Rxg7+ (76.516) 190.8
7.01 0:00 -4.73 1.Rxg7+ Rxg7 2.Qd5+ Rf7 3.Qg5+ Kh8 4.Bb2+ (88.622) 200.9
7.16 0:00 -4.33++ 1.Rd8+ (126.238) 225.0
7.16 0:00 -2.08 1.Rd8+ Rxd8 2.Qxd8+ Bxd8 3.Re8+ Kf7 4.Rf8+ (139.717) 232.4
7.30 0:00 -1.67++ 1.Qd5+ (176.966) 242.0
7.30 0:00 +2.27 1.Qd5+ Kh8 2.Qxg5 Qg1+ 3.Kg3 Qf2+ 4.Kg4 (193.845) 245.0
8.01 0:00 +2.27 1.Qd5+ Kh8 2.Qxg5 Qg1+ 3.Kg3 Qf2+ 4.Kg4 Qxg2+ (251.025)
263.6
9.01 0:01 +3.36++ 1.Qd5+ (482.234) 312.7
9.01 0:01 +7.70 1.Qd5+ Kh8 2.Rd8+ Qf8 3.Rxf8+ Rxf8 4.Qxg5 Bd4 5.Rxb7
(564.526) 325.7
10.01 0:02 +7.80 1.Qd5+ Kh8 2.Rd8+ Qf8 3.Rxf8+ Rxf8 4.Qxg5 Bd4 5.Qd5 Bf6
(1.042.908) 360.3
In contrast when the hash table is enabled Monarch takes *much* longer to find
the key move:
2.01 0:00 -M1 1.Re1 Qxg2+ (56) 5.6
2.02 0:00 -M2++ 1.Re2 (109) 10.9
2.02 0:00 -9.05 1.Re2 Rxg2+ (163) 16.3
2.07 0:00 -7.97++ 1.Re8+ (193) 9.6
2.07 0:00 -7.97 1.Re8+ Rxe8 (198) 9.9
2.08 0:00 -6.97++ 1.Rxg7+ (201) 10.0
2.08 0:00 -6.97 1.Rxg7+ Rxg7 (206) 6.8
2.26 0:00 -6.74++ 1.Qg4 (427) 10.6
2.26 0:00 -6.74 1.Qg4 Rxg4 (490) 12.2
3.01 0:00 -5.64++ 1.Qg4 (875) 17.5
3.01 0:00 -5.74 1.Qg4 Rxg4 2.hxg4 (963) 19.2
4.01 0:00 -7.27-- 1.Qg4 (1.657) 23.3
4.01 0:00 -15.97 1.Qg4 Rxg4 2.Rxg7+ Rxg7 (2.209) 31.1
4.02 0:00 -0.90++ 1.Rxg7+ (2.214) 27.3
4.02 0:00 -5.92 1.Rxg7+ Rxg7 2.Qd5+ Kh8 (2.462) 30.3
5.01 0:00 -5.88 1.Rxg7+ Rxg7 2.Qd5+ Rf7 3.Qxc4 (4.348) 43.0
6.01 0:00 -5.78 1.Rxg7+ Rxg7 2.Qd5+ Rf7 3.Qxc4 Qg1+ (10.813) 76.6
7.01 0:00 -4.57++ 1.Rxg7+ (27.979) 139.1
7.01 0:00 -2.63 1.Rxg7+ Rxg7 2.Qd5+ Kh8 3.Rxg7 Qxa2 4.Rg3 (32.324) 153.1
7.16 0:00 -1.61++ 1.Rd8+ (42.940) 164.5
7.16 0:00 -2.63 1.Rxg7+ Rxg7 2.Qd5+ Kh8 3.Rxg7 Qxa2 4.Rg3 (47.907) 176.7
8.01 0:00 -3.28-- 1.Rxg7+ (83.148) 224.1
8.01 0:00 -3.57 1.Rxg7+ Rxg7 2.Qd5+ Kh8 3.Rxg7 Qg1+ 4.Kg3 Qe3+ (98.963)
240.7
8.16 0:00 -1.47++ 1.Rd8+ (145.607) 269.1
8.16 0:00 -3.57 1.Rxg7+ Rxg7 2.Qd5+ Kh8 3.Rxg7 Qg1+ 4.Kg3 Qe3+ (167.177)
282.8
9.01 0:00 -4.43-- 1.Rxg7+ (243.828) 304.0
9.01 0:00 -6.04 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Qg4+ Kh8 4.Qxc4 Rg8 5.Qd5
(277.367) 314.4
9.16 0:01 +0.48++ 1.Rd8+ (368.608) 322.7
9.16 0:01 -6.04 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Qg4+ Kh8 4.Qxc4 Rg8 5.Qd5
(397.306) 330.5
10.01 0:01 -6.59-- 1.Rxg7+ (597.774) 346.9
10.01 0:01 -6.83 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Bd6 Bd4 4.Qg4+ Kh8 5.Qd7 b6
(692.986) 351.2
10.16 0:03 +0.48++ 1.Rd8+ (1.147.068) 340.8
10.16 0:03 -6.83 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Bd6 Bd4 4.Qg4+ Kh8 5.Qd7 b6
(1.222.503) 345.7
11.01 0:04 -6.78 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Bd6 Bd4 4.Qa4 Rd8 5.Bc7 Qg1+
6.Kg3 (1.754.228) 363.4
11.16 0:08 -6.42++ 1.Rd8+ (2.826.548) 346.3
11.16 0:08 -6.78 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Bd6 Bd4 4.Qa4 Rd8 5.Bc7 Qg1+
6.Kg3 (2.928.006) 347.6
12.01 0:11 -6.84 1.Rxg7+ Rxg7 2.Rxg7+ Kxg7 3.Bd6 Bd4 4.Kh1 Kh8 5.g3 b6 6.a4
Kg8 (4.095.444) 359.9
12.16 0:24 -6.34++ 1.Rd8+ (8.656.328) 356.8
12.16 0:25 -2.29 1.Rd8+ Rxd8 2.Qxd8+ Bxd8 3.Re8+ Kf7 4.Rf8+ Ke6 5.Rxf2 Bb6
6.h4 Ra5 (9.049.352) 360.1
12.30 0:25 +M100++ 1.Qd5+ (9.273.991) 362.4
12.30 0:26 +8.11 1.Qd5+ Kh8 2.Rd8+ Qf8 3.Rxf8+ Rxf8 4.Qxg5 Bd4 5.Qd5 Bb6
6.Bb2 c3 (9.746.445) 367.5
13.01 0:27 +M100++ 1.Qd5+ (9.979.199) 368.6
13.01 0:28 +8.15 1.Qd5+ Kh8 2.Rd8+ Qf8 3.Rxf8+ Rxf8 4.Qxg5 Bd4 5.Qd5 Bb6
6.Qxb7 Bd4 7.Bd6 (10.730.314) 370.8
14.01 0:30 +M100++ 1.Qd5+ (11.640.243) 376.1
So my first question - is this possible? Could the hash table legitimately slow
down the search and block a solution. Logically I cannot see how this is
possible. In addition in the above examples I have simplified the search by
turning off all search extensions.
I have implemented Bruce Moreland’s trick of storing the hash entry as a bound
but this hasn't helped and I'm not sure why not. My Hash storage routine is
quite simple:
//store information
h.Age:=HashAge;
h.Key:=HashKey;
h.Move:=BestMove;
//Store a bound if a checkmate value
if Value>=MinCheckMate then
begin
if HashBound<>hbUpper then
begin
h.Value:=MinCheckMate;
h.Bound:=hbLower;
h.Depth:=+Infinity;
end
else
begin
h.Value:=Value;
h.Bound:=hbUpper;
h.Depth:=Depth;
end;
end
else if Value<=-MinCheckMate then
begin
if HashBound<>hbLower then
begin
h.Value:=-MinCheckMate;
h.Bound:=hbUpper;
h.Depth:=+Infinity;
end
else
begin
h.Value:=Value;
h.Bound:=hbLower;
h.Depth:=Depth;
end;
end
else
begin
h.Value:=Value;
h.Bound:=HashBound;
h.Depth:=p.Depth;
end;
And this is called in the following manner:
1. If a null move fail high is encountered nothing is stored.
2. If a normal fail high occurs a lower bound is stored with the fail soft value
3. After a value where Alpha<Value<Beta and exact score is stored
4. If all moves are less than Alpha an upper bound is stored with the fail soft
value
This seems straightforward so where can I be going wrong? Has anyone else come
across this type of problem?
Any suggestion gratefully received!
Thanks,
Steve
This page took 0.01 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.