fail high handling with tranposition tables

[Karlo Bala]

I can avoid it also by not changing alpha in probing the hash(originally when I did not use hash for pruning I did not change alpha in probing the hash) and I ask what other do about it.

A common (I think) approach is to use the hash table only for move ordering whenever the window is not a null window, which implies not updating alpha in those cases.

Does it mean also not pruning based on hash even if the hash tell you score above beta?

It mean that he don't use hash for pruning or updating alpha in PV nodes (like fruit). That is common.

Not using hash for pruning when beta>alpha+1 mean that movei cannot solve fine70 in a reasonable time.

The problem is that searching the first root move is not done with null window and if the program cannot use hash for pruning in that search then it means that it practically cannot use hash for pruning in searching the first move.

Uri

Hmmm, I'm not sure that you don't have a bug. My program solves fine70 with brute force. It take about 70.000 nodes. Positions where beta>alpha+1 are less than 0.1% of all position searched.

There are few things I learned on harder way (I'm using PVS):

1. Simplest way to avoid problems is not to update alpha nor prune in PV nodes.

2. If you really want to prune in PV do it on right way. It is dangerous to prune in PV based on eval that is not from PV search.
Safe pruning should be:

Code: Select all

if  (inPV && hash.depth  >= depth && hash.eval >= beta && hash.flag == EXACT)
   return hash.eval;

Do not update alpha in PV because sometimes you'll get truncated PV line.

3. If you are using PVS don't use aspiration windows. PVS is already enough efficient and gain from aspiration windows is small, if any.
But from other side, aspiration windows introduce search instability and sometimes you'll get ugly PV line when jumping out from ration window.
Simply call RootSearch(-WIN,WIN) and most of problems will be solved.

[Uri Blass]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

[Vempele]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

If you always search the second move with null window (even if the first failed low), 99% seems a tad low.

[Tord Romstad]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

If you always search the second move with null window (even if the first failed low), 99% seems a tad low.

For a PVS search, 99% is more than a tad too low. I did a quick test right now, searching LCT2 #9 to a depth of 17 plies. The total number of nodes was 65,353,046, while the number of nodes with beta - alpha > 1 was 12,646. This means that 99.98% of all nodes were searched with beta = alpha+1.

Tord

[mjlef]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

That suggests bad move ordering. If the best move is searched first most of the time, nearly all subtrees should be null width. What do you use for move ordering?

[Uri Blass]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

That suggests bad move ordering. If the best move is searched first most of the time, nearly all subtrees should be null width. What do you use for move ordering?

I search hash move first and later good captures and killers.

My move ordering can be improved but I do not think that it is extremely bad.

I am going to check what happens in the tree and I already printed the tree of the first 100,000 nodes of fine70 together with alpha and beta to a logfile.

Note that movei with pruning based on hash tables can find Kb1 in less than 100,000 nodes of search.

Uri

[Uri Blass]

Here is an edited logfile of the first nodes of fine70 and the diagram of fine 70
You are encouraged to tell me what you do better in your program.

I am aware of some unefficient things that I wrote about in the edited logfile.
If you do better then it I would like to know what programming tricks do you use to do better.

Note that in these first 2 plies hash for pruning still had no chance to be used and hash was used only for order of moves.


[D]8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1


1 Ka2
2 Kb2
3 Kb2 main line depth 1 evaluation 116
making a1b2 starting alphabeta(order 1) alpha=-146 beta=-86
first move to search Kb7(suggest that my move ordering can be improved and I simply order them based on order of generation when there is no knowledge of hash or history)
4 Kb2 Kb7 alphabeta order 2 (alpha=86 beta=146) evaluation 92(alpha is increased to -92 in the alphabeta(order 1)
5 Kb2 Ka8 alpha=86 beta=92 evaluation not smaller than 92 so alpha is not increased
6 Kb2 Ka6 the same as node 5
7 Kb2 Kb8 the same
8 Kb2 Kb6 avaluation is 85 so there is a fail low and research
It is clearly wasting nodes because it is possible to get an exact score in that case without research.
9 Kb2 fail high alphabeta order 1 alpha=-146 beta=-16
9 Kb2 Kb6(alphabeta order 2 alpha=16 beta=146 evaluation is 85 for white so alpha is increased to -85 in alphabeta order 1)
10 Kb2 Kb7
11 Kb2 Ka6
12 Kb2 Kb8
13 Kb2 Ka8

Nodes 10-13 are clearly waste of time because they were already searched earlier
hash could help to save not searching after these nodes but unfortunately does not help not searching them again.

kb2 Kb6 main line.
Now searching other moves with minimal window.
14 Ka2
15 Ka2 Kb6 fail high Ka2 is not good
16 Kb1
17 Kb1 Kb6 fail high Kb1 is not good.

conclusion finished depth 2 pv is Kb2 Kb6 evaluation is 0.85 for white.
alpha=55 beta=115 at depth 3.

Uri

[Uri Blass]

in 99% of the nodes beta=alpha+1?
Not for me.

It happens for moves that are not the main line but first move is always searched not with null window so I do not see how 99% of the nodes can be with beta=alpha+1

I certainly having some bugs because I see that inspite of solving fine70 fast without it latest version seems to be weaker than previous version.

Uri

That suggests bad move ordering. If the best move is searched first most of the time, nearly all subtrees should be null width. What do you use for move ordering?

My order of moves is not perfect but it is not the problem.

I change my evaluation to 0 so best move always tried first by definition and it does not help to have trees with null width.

I get the following statistics in fine 70
null search=470 not null search=71803

Note that I assume that programs may have situations when evaluation is 0 all the time like king and knight against king and knight and I wonder what is the statistics in this case

Here is the start of the logfile output in these conditions(I may edit it later to be more readable:

node debug 1 a1a2
node debug 2 a1b2
1 0 0 3 a1b2
node debug 3 a1b2
alpha=-30 beta=30 depth=400 ply=1 null search=0 not null search=0node debug 4 a1b2 a7b7
alpha=-30 beta=30 depth=0 ply=2 null search=0 not null search=1node debug 5 a1b2 a7a8
alpha=-30 beta=0 depth=0 ply=2 null search=0 not null search=2node debug 6 a1b2 a7a6
alpha=-30 beta=0 depth=0 ply=2 null search=0 not null search=3node debug 7 a1b2 a7b8
alpha=-30 beta=0 depth=0 ply=2 null search=0 not null search=4node debug 8 a1b2 a7b6
alpha=-30 beta=0 depth=0 ply=2 null search=0 not null search=52 0 0 9 a1b2 a7b7
node debug 9 a1a2
alpha=-1 beta=0 depth=400 ply=1 null search=0 not null search=6node debug 10 a1a2 a7b7
alpha=0 beta=1 depth=0 ply=2 null search=1 not null search=6node debug 11 a1b1
alpha=-1 beta=0 depth=400 ply=1 null search=2 not null search=6node debug 12 a1b1 a7b7
alpha=0 beta=1 depth=0 ply=2 null search=3 not null search=62 0 0 13 a1b2 a7b7
node debug 13 a1b2
alpha=-30 beta=30 depth=800 ply=1 null search=4 not null search=6node debug 14 a1b2 a7b7
alpha=-30 beta=30 depth=400 ply=2 null search=4 not null search=7node debug 15 a1b2 a7b7 b2c2
alpha=-30 beta=30 depth=0 ply=3 null search=4 not null search=8node debug 16 a1b2 a7b7 b2a2
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=9node debug 17 a1b2 a7b7 b2b3
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=10node debug 18 a1b2 a7b7 b2b1
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=11node debug 19 a1b2 a7b7 b2c3
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=12node debug 20 a1b2 a7b7 b2c1
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=13node debug 21 a1b2 a7b7 b2a3
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=14node debug 22 a1b2 a7b7 b2a1
alpha=-30 beta=0 depth=0 ply=3 null search=4 not null search=15node debug 23 a1b2 a7a8
alpha=-30 beta=0 depth=400 ply=2 null search=4 not null search=16node debug 24 a1b2 a7a8 b2c2
alpha=0 beta=30 depth=0 ply=3 null search=4 not null search=17node debug 25 a1b2 a7a6
alpha=-30 beta=0 depth=400 ply=2 null search=4 not null search=18node debug 26 a1b2 a7a6 b2c2
alpha=0 beta=30 depth=0 ply=3 null search=4 not null search=19node debug 27 a1b2 a7b8
alpha=-30 beta=0 depth=400 ply=2 null search=4 not null search=20node debug 28 a1b2 a7b8 b2c2
alpha=0 beta=30 depth=0 ply=3 null search=4 not null search=21node debug 29 a1b2 a7b6
alpha=-30 beta=0 depth=400 ply=2 null search=4 not null search=22node debug 30 a1b2 a7b6 b2c2
alpha=0 beta=30 depth=0 ply=3 null search=4 not null search=233 0 0 31 a1b2 a7b7 b2c2
node debug 31 a1a2
alpha=-1 beta=0 depth=800 ply=1 null search=4 not null search=24node debug 32 a1a2 a7b7
alpha=0 beta=1 depth=400 ply=2 null search=5 not null search=24node debug 33 a1a2 a7b7 a2b2
alpha=-1 beta=0 depth=0 ply=3 null search=6 not null search=24node debug 34 a1a2 a7b7 a2a3
alpha=-1 beta=0 depth=0 ply=3 null search=7 not null search=24node debug 35 a1a2 a7b7 a2a1
alpha=-1 beta=0 depth=0 ply=3 null search=8 not null search=24node debug 36 a1a2 a7b7 a2b3
alpha=-1 beta=0 depth=0 ply=3 null search=9 not null search=24node debug 37 a1a2 a7b7 a2b1
alpha=-1 beta=0 depth=0 ply=3 null search=10 not null search=24node debug 38 a1b1
alpha=-1 beta=0 depth=800 ply=1 null search=11 not null search=24node debug 39 a1b1 a7b7
alpha=0 beta=1 depth=400 ply=2 null search=12 not null search=24node debug 40 a1b1 a7b7 b1c1
alpha=-1 beta=0 depth=0 ply=3 null search=13 not null search=24node debug 41 a1b1 a7b7 b1a1
alpha=-1 beta=0 depth=0 ply=3 null search=14 not null search=24node debug 42 a1b1 a7b7 b1b2
alpha=-1 beta=0 depth=0 ply=3 null search=15 not null search=24node debug 43 a1b1 a7b7 b1c2
alpha=-1 beta=0 depth=0 ply=3 null search=16 not null search=24node debug 44 a1b1 a7b7 b1a2
alpha=-1 beta=0 depth=0 ply=3 null search=17 not null search=243 0 0 45 a1b2 a7b7 b2c2
node debug 45 a1b2
alpha=-30 beta=30 depth=1200 ply=1 null search=18 not null search=24node debug 46 a1b2 a7b7
alpha=-30 beta=30 depth=800 ply=2 null search=18 not null search=25node debug 47 a1b2 a7b7 b2c2
alpha=-30 beta=30 depth=400 ply=3 null search=18 not null search=26node debug 48 a1b2 a7b7 b2c2 b7c7
alpha=-30 beta=30 depth=0 ply=4 null search=18 not null search=27node debug 49 a1b2 a7b7 b2c2 b7a7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=28node debug 50 a1b2 a7b7 b2c2 b7b8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=29node debug 51 a1b2 a7b7 b2c2 b7b6
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=30node debug 52 a1b2 a7b7 b2c2 b7c8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=31node debug 53 a1b2 a7b7 b2c2 b7a8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=32node debug 54 a1b2 a7b7 b2c2 b7a6
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=33node debug 55 a1b2 a7b7 b2a2
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=34node debug 56 a1b2 a7b7 b2a2 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=35node debug 57 a1b2 a7b7 b2b3
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=36node debug 58 a1b2 a7b7 b2b3 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=37node debug 59 a1b2 a7b7 b2b1
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=38node debug 60 a1b2 a7b7 b2b1 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=39node debug 61 a1b2 a7b7 b2c3
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=40node debug 62 a1b2 a7b7 b2c3 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=41node debug 63 a1b2 a7b7 b2c1
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=42node debug 64 a1b2 a7b7 b2c1 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=43node debug 65 a1b2 a7b7 b2a3
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=44node debug 66 a1b2 a7b7 b2a3 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=45node debug 67 a1b2 a7b7 b2a1
alpha=-30 beta=0 depth=400 ply=3 null search=18 not null search=46node debug 68 a1b2 a7b7 b2a1 b7c7
alpha=0 beta=30 depth=0 ply=4 null search=18 not null search=47node debug 69 a1b2 a7a8
alpha=-30 beta=0 depth=800 ply=2 null search=18 not null search=48node debug 70 a1b2 a7a8 b2c2
alpha=0 beta=30 depth=400 ply=3 null search=18 not null search=49node debug 71 a1b2 a7a8 b2c2 a8b8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=50node debug 72 a1b2 a7a8 b2c2 a8a7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=51node debug 73 a1b2 a7a8 b2c2 a8b7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=52node debug 74 a1b2 a7a6
alpha=-30 beta=0 depth=800 ply=2 null search=18 not null search=53node debug 75 a1b2 a7a6 b2c2
alpha=0 beta=30 depth=400 ply=3 null search=18 not null search=54node debug 76 a1b2 a7a6 b2c2 a6b6
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=55node debug 77 a1b2 a7a6 b2c2 a6a7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=56node debug 78 a1b2 a7a6 b2c2 a6b7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=57node debug 79 a1b2 a7b8
alpha=-30 beta=0 depth=800 ply=2 null search=18 not null search=58node debug 80 a1b2 a7b8 b2c2
alpha=0 beta=30 depth=400 ply=3 null search=18 not null search=59node debug 81 a1b2 a7b8 b2c2 b8c8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=60node debug 82 a1b2 a7b8 b2c2 b8a8
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=61node debug 83 a1b2 a7b8 b2c2 b8b7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=62node debug 84 a1b2 a7b8 b2c2 b8c7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=63node debug 85 a1b2 a7b8 b2c2 b8a7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=64node debug 86 a1b2 a7b6
alpha=-30 beta=0 depth=800 ply=2 null search=18 not null search=65node debug 87 a1b2 a7b6 b2c2
alpha=0 beta=30 depth=400 ply=3 null search=18 not null search=66node debug 88 a1b2 a7b6 b2c2 b6a6
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=67node debug 89 a1b2 a7b6 b2c2 b6b7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=68node debug 90 a1b2 a7b6 b2c2 b6c7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=69node debug 91 a1b2 a7b6 b2c2 b6a7
alpha=-30 beta=0 depth=0 ply=4 null search=18 not null search=704 0 0 92 a1b2 a7b7 b2c2 b7c7
node debug 92 a1a2
alpha=-1 beta=0 depth=1200 ply=1 null search=18 not null search=71node debug 93 a1a2 a7b7
alpha=0 beta=1 depth=800 ply=2 null search=19 not null search=71node debug 94 a1a2 a7b7 a2b2
alpha=-1 beta=0 depth=400 ply=3 null search=20 not null search=71node debug 95 a1a2 a7b7 a2b2 b7c7
alpha=0 beta=1 depth=0 ply=4 null search=21 not null search=71node debug 96 a1a2 a7b7 a2a3
alpha=-1 beta=0 depth=400 ply=3 null search=22 not null search=71node debug 97 a1a2 a7b7 a2a1
alpha=-1 beta=0 depth=400 ply=3 null search=23 not null search=71node debug 98 a1a2 a7b7 a2b3
alpha=-1 beta=0 depth=400 ply=3 null search=24 not null search=71node debug 99 a1a2 a7b7 a2b1
alpha=-1 beta=0 depth=400 ply=3 null search=25 not null search=71node debug 100 a1b1
alpha=-1 beta=0 depth=1200 ply=1 null search=26 not null search=71node debug 101 a1b1 a7b7
alpha=0 beta=1 depth=800 ply=2 null search=27 not null search=71node debug 102 a1b1 a7b7 b1c1
alpha=-1 beta=0 depth=400 ply=3 null search=28 not null search=71node debug 103 a1b1 a7b7 b1a1
alpha=-1 beta=0 depth=400 ply=3 null search=29 not null search=71node debug 104 a1b1 a7b7 b1b2
alpha=-1 beta=0 depth=400 ply=3 null search=30 not null search=71node debug 105 a1b1 a7b7 b1c2
alpha=-1 beta=0 depth=400 ply=3 null search=31 not null search=71node debug 106 a1b1 a7b7 b1a2
alpha=-1 beta=0 depth=400 ply=3 null search=32 not null search=714 0 3 107 a1b2 a7b7 b2c2 b7c7
node debug 107 a1b2




Uri

[Vempele]

Here is the start of the logfile output in these conditions(I may edit it later to be more readable:

As far as I can see, that's not PVS. In PVS, once you have searched one move in any node, you search the node's other moves with null window. With perfect move ordering, a depth N search would have exactly N+1 nodes (+ QS and extensions) with open window.

[Uri Blass]

Here is the start of the logfile output in these conditions(I may edit it later to be more readable:

As far as I can see, that's not PVS. In PVS, once you have searched one move in any node, you search the node's other moves with null window. With perfect move ordering, a depth N search would have exactly N+1 nodes (+ QS and extensions) with open window.

I admit that I do not do it and I do not understand how this idea can be sound.

suppose Kb2 is the first move with score 0

suppose I search it with window (-30,30)

After searching 1.Kb2 Kb6 score 0 for all lines
second move to search is Kb8
What is alpha and beta after Kb8?

Uri