Why minimax is fundamentally flawed

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

syzygy wrote:Theoretically there may be cases where it goes wrong. In practice this seems to occur so rarely that I am confident that any "solution" (replace the minimax principle by somthing else?) would negatively affect playing strength.
That is a daring claim, for something you have not tested and goes against logic at the same time...

My experience is that this is actually very common. In Chess there is almost always some backlash after materializing a gain, because while one side was occupied securing the gain the other could prepare for some retaliation. So you are almost always better off to postpose the gain to occur exactly on the horizon, conveniently push the backlash out of view.

Of course another common reason for ID not finding the shortest path first is that it initially was masked by some other line. Engines do not only switch root move now and then to reach the same position through a different path; usually they do it to realize a different objective altogether. The path to that new objective then has not been obtained through ID at all, it was found at the depth where the original plan fell through, a depth that might very well have been sufficient to already include an amount of stalling in the path to the new objective.

Delayed loss bonus also helps against other forms of minimax stupidity, btw: if the same final position can be forced starting with a sacrifice, and recouping the loss later, or by first gaining something, and having to give it up later, the latter would be preferred. (Because there you collect the delayed-loss bonus yourself upto the point where you have the give up the gain, while otherwise the opponent would get it.) The sac or gain can also be something as trivial as moving your Knight from b1 to c4 via a poor square (a3, a sac) or a good one (d2). If deeper search then reveals that going to c4 is not so hot as it first seemed, it would be better to get stuck on the good square than on the poor one...

One thing is for sure, though: resigning will never add any Elo to an engine!
Maarten Claessens
Posts: 106
Joined: Mon May 12, 2014 10:08 am
Location: Near Nijmegen

Re: Why minimax is fundamentally flawed

Post by Maarten Claessens »

I need to mention that in WaDuuttie a KRK-position is scored by
  • 1. the position of the lone king (closer to the edge is better)
    2. the distance between the two kings (smaller is better)
On top of that a constant is added to signify a winning position.
Nothing is unstable (Lawrence Krauss)
Maarten Claessens
Posts: 106
Joined: Mon May 12, 2014 10:08 am
Location: Near Nijmegen

Re: Why minimax is fundamentally flawed

Post by Maarten Claessens »

I repeated the experiment with Joker 1114 (asuming he uses the delayed loss-bonus). Joker can deliver the mate with at least a 4 ply search. With only a 3 ply search the 50-moves rule saves the (knowing) opponent.
Nothing is unstable (Lawrence Krauss)
User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

Of course Fairy-Max, having nothing but King centralization in its eval, (and delayed-loss bonus), has little difficulty finding the mate, form the position immediately after conversion to KRK:
[d]8/8/8/8/4k3/8/1RK5/8 w - - 0 1

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 25	+79.85 	53.2M  	0:42.37	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3f2 c3d3 f2f3 b4d4
 24	+79.85 	31.0M  	0:24.78	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 c2c3 e3e2
 23	+79.83 	24.8M  	0:19.81	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e1 b3c3 e1e2 c3c2
 22	+79.78 	13.1M  	0:10.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 d4b4 e3f3 c2d2 f3f2 b4f4 f2g2 d2d1
 21	+79.76 	9.31M  	0:07.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e3 b3c3 e3e2 c3c2
 20	+5.52 	6.15M  	0:04.82	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f2 d4d3 f2f3 b4e4
 19	+5.45 	4.70M  	0:03.68	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e1 b3c2 e1e2 d4f4 e2e3 f4b4
 18	+5.16 	3.34M  	0:02.61	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 c2c3
 17	+5.05 	2.60M  	0:02.03	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2
 16	+5.03 	2.17M  	0:01.70	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e2 c4c3 e2f2 c3c2 f2g2 b4c4
 15	+5.01 	2.02M  	0:01.56	b2b5 e4d4 c2b3 d4d3 b5d5 d3e3
 15	+4.92 	1.23M  	0:00.93	c2c3 e4e5 b2e2 e5f4 c3c4 f4f5 c4d4
 14	+4.92 	666311	0:00.50	c2c3 e4e5 b2e2 e5f5 c3d4 f5f4 e2f2 f4g3 d4e3 g3g4 f2f7
 13	+4.91 	494410	0:00.36	c2c3 e4e5 b2e2 e5f5 c3d4 f5f4 e2f2 f4g3 f2f7 g3g4
 12	+4.91 	448463	0:00.32	c2c3 e4e5 b2e2 e5f5 c3d4 f5f4 e2b2
 12	+4.76 	327831	0:00.23	b2b1 e4f4 b1b5 f4e4 c2c3 e4f3 b5b4 f3e3 c3c2 e3f2 b4e4 f2g3
 11	+4.75 	185469	0:00.12	b2b1 e4f4 c2d3 f4e5 b1f1 e5d6 f1e1 d6c6 d3d4
 10	+4.79 	114425	0:00.07	b2b1 e4f4 c2d3 f4e5 b1f1 e5d6 f1e1 d6d5 e1e2
  9	+4.77 	92718  	0:00.06	b2b1 e4f4 c2d3 f4e5 b1f1 e5d6 d3e4 d6e6 f1g1
  9	+4.64 	65630  	0:00.04	c2d2 e4d4 d2e2 d4e5 e2e3 e5f5 e3d3
  8	+4.68 	39439  	0:00.01	c2d2 e4d4 b2b4 d4d5 d2e3 d5e5 b4c4 e5f5
  8	+4.66 	34280  	0:00.01	c2c3 e4f4 c3d3 f4e5 b2f2 e5d5 f2e2 d5d6
  7	+4.60 	26436  	0:00.01	c2c3
  7	+4.59 	19624  	0:00.01	c2c3 e4f4 c3d3 f4e5 b2b6
  6	+4.63 	14825  	0:00.00	c2c3 e4f4 c3d3 f4e5 d3e3 e5f5
  6	+4.61 	11842  	0:00.00	b2b7 e4d4 b7b5
  6	+4.59 	10899  	0:00.00	b2b6 e4d5 c2c3 d5e5 c3d3
  5	+4.63 	4485    	0:00.00	b2b6 e4d4 b6e6 d4d5 e6f6
  5	+4.58 	3164    	0:00.00	b2b3 e4d4 b3b2 d4e5 c2d3
  4	+4.62 	1624    	0:00.00	b2b3 e4d4 c2d2 d4e4
  4	+4.57 	1254    	0:00.00	b2b1 e4d4 b1e1 d4d5
  4	+4.54 	684      	0:00.00	b2b4 e4f5 c2d3 f5e5
  3	+4.60 	263      	0:00.00	b2b4 e4e5 c2d3
  3	+4.49 	213      	0:00.00	b2b1 e4e5 c2d3
  3	+4.42 	159      	0:00.00	b2b5 e4d4 c2d2
  2	+4.57 	61        	0:00.00	b2b5 e4f4
  2	+4.47 	36        	0:00.00	b2a2 e4e5
  2	+4.44 	27        	0:00.00	b2b1 e4e5
  2	+4.36 	18        	0:00.00	b2b8 e4e5
  1	+4.59 	10        	0:00.00	b2b8
At 21 ply it already sees a mate in 24, which at 24 ply (24 sec on a single 2.4GHz i3 core) is improved to a mate in 15.

This of course is cause by grafting, as to see M15 would need 29 ply. (Checks just delay the mate in KRK, so you wont get free plies from the check extension.) So not doing hash cuts in PV moves, which destroys the ability to graft, probably plays a role here too.

I must admit that the search above was using Fairy-Max 4.8V's new feature for recognizing bare King in the root, and multiplying its centralization bonus by 5. (This was needed to reliably checkmate with many centralizing pieces, such as in KNFFK with the F both on the same color; when it would give centralization of the bare King equal weight to centralization of the 4 pieces of the winning side, the latter would think it more profitable to just centralize his own pieces, and leave the bare King alone to do what he wants!) When I let it search the same position using the normal centralization bonus for both Kings, it takes a bit longer:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 24	+79.83 	48.3M  	0:40.03	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f3 d4d3 f3f2 b4f4 f2g2 d3d4
 23	+79.83 	41.3M  	0:34.31	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f3 d4d3
 22	+79.79 	35.5M  	0:29.48	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f2 d4d3 f2f3 b4b5
 21	+79.76 	32.9M  	0:27.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3b2 d2d3 b4a4 d3e3 b2c2 e3f3 c2c1
 21	+5.25 	31.5M  	0:26.12	b2b1 e4d4 b1e1 d4c4 e1d1 c4b4 c2d3 b4c5 d3c3
 20	+5.26 	27.9M  	0:23.15	b2b1 e4d4 b1e1 d4c5 e1d1 c5c4 c2b2 c4b5 b2c3 b5c5 c3b3
 20	+5.19 	22.9M  	0:19.18	b2b4 e4d5 c2d3 d5c5 b4b3 c5d5 b3c3 d5e5 c3c6 e5d5 c6c4
 19	+5.25 	15.9M  	0:13.20	b2b4 e4e5 c2d3 e5e6 d3d4 e6f5 d4d5 f5f6 d5e4
 19	+5.18 	13.9M  	0:11.53	b2b8 e4e5 c2d3 e5d6 d3c4 d6e6 c4d4
 18	+5.24 	9.07M  	0:07.37	b2b8 e4f4 b8e8 f4f5 c2d3 f5f4 d3d4 f4f5 d4e3 f5g5 e3e4 g5f6 e8b8 f6e6 b8b6 e6e7 b6a6 e7f7
 18	+5.22 	8.26M  	0:06.73	b2b1 e4f4 c2d3 f4e5 b1a1 e5f5 a1a5 f5f4 a5c5 f4f3 c5c4 f3f2 d3e4 f2g3 c4c2
 18	+5.16 	6.75M  	0:05.54	b2b4 e4e5 c2d3 e5e6 d3d4 e6d6 d4e4
 17	+5.21 	3.81M  	0:03.07	b2b4 e4d5 c2d3 d5e5 b4b5 e5f4 b5c5 f4f3 c5f5 f3g3 d3e3 g3g2
 17	+5.17 	3.00M  	0:02.42	b2b5 e4d4 c2b3 d4d3 b5e5 d3d4 e5b5
 16	+5.19 	2.10M  	0:01.67	b2b5 e4d4 c2b3 d4e3 b3c4 e3e4 c4c3 e4f3 c3d4
 15	+5.20 	1.50M  	0:01.18	b2b5 e4d4 c2b3 d4e3 b3c3 e3e4 b5a5 e4e3 a5a4 e3f2 c3d3 f2f1 a4c4 f1f2 c4c2
 14	+5.22 	1.21M  	0:00.95	b2b5 e4d4 c2b3 d4d3 b5b4 d3e3 b3c3 e3e2 c3d4 e2f2 d4d3 f2f3 d3d4 f3f4
 14	+5.17 	1.11M  	0:00.87	b2b4 e4d5 c2d3 d5c5 b4b8 c5c6 d3e4 c6c5 b8b3 c5c4 b3f3 c4c5
 13	+5.18 	854690	0:00.67	b2b4 e4d5 c2d3 d5c5 b4b8 c5d5 b8b5
 12	+5.21 	592846	0:00.45	b2b4 e4e5 c2d3 e5d5 b4b5 d5c6 d3c4 c6d6 c4d4
 12	+5.15 	550810	0:00.42	b2b1
 12	+5.14 	550810	0:00.42	b2b1 e4d4 b1d1 d4c5 c2c3 c5b6 c3d4 b6c6 d4c4 c6b6 c4d5 b6b5
 11	+5.22 	372085	0:00.29	b2b1 e4f4 c2d3 f4e5 b1e1 e5f4 d3d4 f4f5 e1f1 f5e6 d4e4
 11	+5.20 	345229	0:00.26	b2b8 e4f4 c2d3 f4e5 b8f8 e5e6 d3e4 e6d6 f8f6 d6c5 f6f5
 10	+5.20 	292881	0:00.21	b2b8 e4e3 c2c3 e3e4 b8e8 e4f4 c3d4 f4f5 e8b8
 10	+5.13 	263347	0:00.20	b2b6 e4d4 c2d2 d4c5 b6b3 c5d5 b3b6
 10	+5.11 	225133	0:00.17	b2b4 e4f5 c2d3 f5e6 d3e4 e6e7 e4d3 e7f6
  9	+5.23 	184816	0:00.14	b2b4 e4f5 c2d3 f5e5 b4a4 e5d5 a4a5 d5e6 d3e4
  9	+5.10 	155073	0:00.11	c2c1 e4e5 c1d1 e5e6 b2b5 e6f6 b5c5 f6g6 c5c2
  9	+5.05 	138132	0:00.11	c2d2 e4d5 d2e3 d5c6 b2b1 c6c7
  8	+5.19 	61070  	0:00.04	c2d2 e4d4 d2e2 d4e4 b2b3 e4f4 e2d3 f4g4
  8	+5.17 	43524  	0:00.03	b2b4 e4f5 c2c3 f5e5 c3d3
  7	+5.17 	37687  	0:00.03	b2b4 e4f5 c2c3 f5e5 c3d3
  7	+5.13 	22236  	0:00.01	c2c1 e4d3 c1d1 d3e3 d1c2 e3e4
  7	+5.01 	16612  	0:00.01	c2b3 e4d3 b2a2 d3e3 b3c4 e3e4 a2a1
  6	+5.15 	9150    	0:00.01	c2b3 e4d4 b3b4 d4d5 b2d2 d5e5
  6	+5.11 	7641    	0:00.01	c2c3 e4e5 c3c4 e5e6 c4d4 e6f6
  5	+5.21 	3604    	0:00.01	c2c3 e4e5 c3d3 e5d5 d3e3
  4	+5.18 	1529    	0:00.00	c2c3 e4e3 c3c4 e3e4
  4	+5.11 	1193    	0:00.00	c2d1 e4d3 b2b4 d3e3
  4	+5.02 	822      	0:00.00	c2b1 e4d4 b2e2 d4d5
  4	+4.98 	490      	0:00.00	c2d2
  4	+4.97 	490      	0:00.00	c2d2 e4d4 d2e2 d4e4
  3	+5.19 	341      	0:00.00	c2d2 e4d4 d2e2
  3	+5.13 	251      	0:00.00	b2b4 e4e3 c2c3
  3	+5.04 	183      	0:00.00	b2b1 e4d4 c2d2
  2	+5.13 	25        	0:00.00	b2b1 e4e5
  2	+4.90 	18        	0:00.00	b2b8 e4e5
  1	+5.11 	9          	0:00.00	b2b8
User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

When I switch off alpha-beta pruning (i.e. force the window completely open in the recursive call, making it Search(-INF, INF) rather than Search(-beta, -alpha)), it also doesn't do so bad: 33 sec before it finds the mate, but then it immediately finds a mate in 17, rather than a very distant one.

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 15	+79.83 	31.2M  	0:33.04	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 14	+5.44 	13.0M  	0:13.37	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 13	+5.19 	7.12M  	0:07.20	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 12	+5.06 	3.79M  	0:03.73	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 11	+4.97 	2.82M  	0:02.73	b2b5 e4d4 c2b3 d4d3 b5b4
 11	+4.92 	2.32M  	0:02.21	b2b4 e4e5 c2d3 e5f5 b4b5 f5e6 d3d4
 10	+4.88 	1.60M  	0:01.50	b2b4 e4e5 c2d3 e5f5 b4b5
 10	+4.87 	1.17M  	0:01.07	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
  9	+4.79 	894691	0:00.79	b2b5 e4d4 c2b3 d4e4 b3c3
  9	+4.76 	759038	0:00.67	b2b1 e4e5 c2d3 e5f5 d3d4 f5e6 b1f1
  9	+4.75 	713819	0:00.62	b2b8 e4e5 c2d3 e5f5
  8	+4.71 	577230	0:00.50	b2b8 e4f4 c2d3 f4f5 d3e3 f5e5 b8b5
  8	+4.69 	542883	0:00.46	b2b1 e4e5 c2d3 e5f5 b1b8 f5f6
  8	+4.68 	374344	0:00.31	c2c3 e4e5 b2e2 e5f4 c3d3 f4f5 e2e3
  7	+4.68 	271334	0:00.21	c2c3 e4e5 b2e2 e5f4
  7	+4.67 	247360	0:00.20	b2b8 e4f5 c2d3 f5e5
  7	+4.66 	218364	0:00.17	b2b6 e4d4 b6e6 d4d5
  7	+4.65 	194234	0:00.15	b2b3 e4d4 c2d2 d4e4
  7	+4.64 	140459	0:00.10	b2b5 e4d4 c2b3 d4e3 b5b4
  6	+4.64 	86784  	0:00.06	b2b5 e4d4 c2b3 d4e3 b5b4
  6	+4.61 	52202  	0:00.03	b2b7 e4e5 c2c3 e5f4
  5	+4.64 	25240  	0:00.01	b2b7 e4d5 c2d3 d5e5
  5	+4.59 	18933  	0:00.01	b2b3 e4d4 b3d3 d4e4
  5	+4.58 	15117  	0:00.00	b2b1 e4d5 c2d3 d5e5
  5	+4.50 	12452  	0:00.00	b2b6 e4e5 c2c3 e5f4
  4	+4.61 	4824    	0:00.00	b2b6 e4d4 b6e6 d4d5
  4	+4.58 	4140    	0:00.00	b2b5 e4d4 b5b4
  4	+4.50 	1770    	0:00.00	b2b3 e4f5 b3b4 f5e6
  3	+4.65 	392      	0:00.00	b2b3 e4e5 c2d3
  3	+4.59 	189      	0:00.00	b2b4 e4e5 c2d3
  2	+4.53 	98        	0:00.00	b2b4 e4e5
  2	+4.52 	35        	0:00.00	c2c1 e4e5
  2	+4.43 	19        	0:00.00	c2c3 e4e5
  1	+4.63 	11        	0:00.00	c2c3
That was with 64MB hash. With 256MB it would be a bit faster. (Hash size is pretty important to Fairy-Max, as it doesn't have any form of depth-preferred replacement, just always replace.) This is again pure minimax, not alpha-beta:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 18	+79.86 	36.9M  	0:40.11	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 17	+79.86 	22.8M  	0:24.40	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 16	+79.85 	21.0M  	0:22.48	b2b5 e4d4 c2b3 d4d3 b5b4
 16	+79.83 	17.7M  	0:18.81	c2c3 e4e5 b2b5 e5d6 c3d4 d6e6 b5b6
 15	+5.84 	13.5M  	0:14.21	c2c3 e4e5 b2b5 e5d6 c3d4 d6e6 b5h5
 15	+5.65 	12.5M  	0:13.17	b2b8 e4e5 c2c3 e5f6 c3d4 f6e7 d4e5 e7d7 b8b4
 15	+5.61 	12.1M  	0:12.70	b2b7 e4f5 c2d3 f5e5 b7b4
 15	+5.56 	9.39M  	0:09.84	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
 14	+5.37 	5.85M  	0:06.04	b2b5 e4d4 c2b3 d4e4 b3c3
 13	+5.18 	5.44M  	0:05.61	b2b5 e4d4 b5a5
 13	+5.13 	5.35M  	0:05.51	b2b1 e4e5 c2d3 e5f5 d3d4
 13	+5.12 	4.57M  	0:04.68	c2c3 e4e5 b2a2 e5e6 c3d4 e6f5
 12	+5.07 	3.85M  	0:03.92	c2c3 e4e5 c3d3
 12	+5.05 	2.62M  	0:02.62	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3
 11	+4.97 	1.72M  	0:01.67	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3
 10	+4.91 	1.02M  	0:00.95	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2
  9	+4.90 	780094	0:00.70	b2b5 e4d4 c2b3 d4d3 b5b4
  9	+4.76 	736589	0:00.65	b2a2 e4d4 a2a5 d4e4 c2c3 e4f4 a5c5
  9	+4.75 	653203	0:00.57	b2b4 e4f5 c2d2 f5e5 d2d3
  8	+4.75 	339607	0:00.28	b2b4 e4e5 c2d2 e5f5 d2c3
  7	+4.76 	195806	0:00.15	b2b4 e4f5 c2d2 f5e5 d2d3
  7	+4.74 	152217	0:00.12	b2b1 e4f4 c2d3 f4e5
  6	+4.70 	50496  	0:00.03	b2b1 e4d5 c2d3 d5e5 d3e3 e5f5
  5	+4.64 	12753  	0:00.00	b2b1 e4d5 c2d3 d5e5
  4	+4.56 	6264    	0:00.00	b2b1 e4d4 b1e1 d4d5
  4	+4.54 	4918    	0:00.00	c2d1 e4e5 b2e2 e5f5
  4	+4.51 	3255    	0:00.00	c2c1 e4e5 b2e2 e5f5
  4	+4.46 	1849    	0:00.00	c2b3 e4d3 b3b4 d3e4
  3	+4.62 	1046    	0:00.00	c2b3 e4e5 b3c3
  3	+4.60 	209      	0:00.00	b2a2 e4e5 c2d3
  2	+4.56 	38        	0:00.00	b2a2 e4e5
  2	+4.49 	29        	0:00.00	b2b1 e4e5
  2	+4.46 	20        	0:00.00	b2b5 e4f4
  1	+4.59 	13        	0:00.00	b2b5
User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

I get the best of both worlds when I change Fairy-Max' hash table to a two-sided one (storing upper and lower limit separately, each with its own depth). I am not sure if I did this in the best way, as I had really never used dual hashing before, but what I do on probing is this:

1) if the hashed lower limit is above beta, take it as a cutoff for the associated hashed depth, and use the hash move when starting iterating from that depth if the depth was not yet enough.
2) otherwise, if the hashed upper limit is below alpha, take it as a fail low for the associated hashed depth. Ignore the move and start deepening from there if the depth was not enough.
3) otherwise, if upper and lower limit are the same, take it as an exact hit of the lowest depth of the two. Use the hashed move, and start iterating from that depth if it was not deep enough.
4) otherwise, treat it as a hash miss, and start IID at QS level.

With alpha beta this gives:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 23	+79.86 	37.2M  	0:31.56	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4
 22	+79.86 	27.8M  	0:23.68	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4
 21	+79.86 	20.5M  	0:17.56	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4
 20	+79.86 	17.2M  	0:14.79	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4
 19	+79.84 	11.8M  	0:10.07	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2
 18	+79.84 	8.02M  	0:06.81	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2c2 b4b6 c2d2 c4d4 d2e2 b6b3
 17	+5.19 	4.12M  	0:03.46	b2b5 e4d4 c2b3 d4e4 b3c3 e4f4 c3d3
 16	+5.19 	3.06M  	0:02.54	b2b5 e4d4 c2b3 d4e4 b3c3 e4f4 c3d3
 15	+5.16 	2.28M  	0:01.85	b2b5 e4d4 c2b3 d4e3 b5b4 e3d3 b4g4 d3d2 b3c4 d2e2 c4c3 e2e3
 14	+5.09 	1.90M  	0:01.53	b2b5 e4d4 c2b3 d4e3 b5b4 e3d3 b4c4 d3d2 c4d4
 13	+5.08 	1.75M  	0:01.40	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3 c3d3 f3f4 b5h5 f4g4 h5e5 g4g3
 13	+4.90 	1.64M  	0:01.31	b2a2 e4d4 a2a5 d4c4 a5g5
 13	+4.87 	1.52M  	0:01.21	b2b1 e4e5 c2d3 e5d5 b1b5 d5d6 d3e4 d6e6
 12	+4.79 	752933	0:00.57	b2b1 e4f4 c2d3 f4f5 b1b5 f5f6 d3e4 f6e6 b5e5 e6f6 e5b5
 11	+4.81 	437382	0:00.32	b2b1 e4f4 c2d3 f4f5 b1b5 f5f6 d3e4 f6e6 b5b6 e6e7 e4e5
 10	+4.75 	228432	0:00.15	b2b1 e4f4 c2d3 f4f5 b1c1 f5e6 d3d4 e6f5
  9	+4.67 	116823	0:00.07	b2b1 e4d5 c2d3 d5e5 b1f1 e5e6 f1b1 e6f5
  8	+4.70 	76304  	0:00.04	b2b1 e4d5 c2d3 d5e5 b1f1 e5d5 f1f5 d5e6
  8	+4.64 	54717  	0:00.03	c2c3 e4e5 b2b6 e5f5 b6b1
  7	+4.69 	39813  	0:00.01	c2c3 e4e5 b2e2 e5f5 c3d4 f5f4 d4d5
  7	+4.67 	22037  	0:00.01	b2b1 e4d5 c2d3 d5e5 d3e3 e5f5 e3d4
  6	+4.64 	13863  	0:00.00	b2b1 e4d5 c2d3 d5e5 d3e3 e5f5
  5	+4.62 	4760    	0:00.00	b2b1 e4d5 c2d3 d5e5
  5	+4.58 	2920    	0:00.00	b2b6 e4d4 b6e6 d4d5 e6f6
  4	+4.55 	1006    	0:00.00	b2b6 e4d4 b6e6 d4d5
  3	+4.65 	324      	0:00.00	b2b6 e4e5 c2d3
  3	+4.59 	220      	0:00.00	b2b1 e4e5 c2d3
  3	+4.58 	162      	0:00.00	b2b7 e4e5 c2d3
  2	+4.59 	22        	0:00.00	b2b7 e4e5
  1	+4.59 	14        	0:00.00	b2b7
(With minimax it would of course be pointless, as all hashed scores would be exact, and the lower and upper limit would always be equal.)
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Why minimax is fundamentally flawed

Post by bob »

hgm wrote:
syzygy wrote:Theoretically there may be cases where it goes wrong. In practice this seems to occur so rarely that I am confident that any "solution" (replace the minimax principle by somthing else?) would negatively affect playing strength.
That is a daring claim, for something you have not tested and goes against logic at the same time...

My experience is that this is actually very common. In Chess there is almost always some backlash after materializing a gain, because while one side was occupied securing the gain the other could prepare for some retaliation. So you are almost always better off to postpose the gain to occur exactly on the horizon, conveniently push the backlash out of view.

Of course another common reason for ID not finding the shortest path first is that it initially was masked by some other line. Engines do not only switch root move now and then to reach the same position through a different path; usually they do it to realize a different objective altogether. The path to that new objective then has not been obtained through ID at all, it was found at the depth where the original plan fell through, a depth that might very well have been sufficient to already include an amount of stalling in the path to the new objective.

Delayed loss bonus also helps against other forms of minimax stupidity, btw: if the same final position can be forced starting with a sacrifice, and recouping the loss later, or by first gaining something, and having to give it up later, the latter would be preferred. (Because there you collect the delayed-loss bonus yourself upto the point where you have the give up the gain, while otherwise the opponent would get it.) The sac or gain can also be something as trivial as moving your Knight from b1 to c4 via a poor square (a3, a sac) or a good one (d2). If deeper search then reveals that going to c4 is not so hot as it first seemed, it would be better to get stuck on the good square than on the poor one...

One thing is for sure, though: resigning will never add any Elo to an engine!
This is, and always has been, a problem. Probably the simplest example is the concept of castling. You want to get your king to safety since you, as a human, see that your opponent is slowly developing some threats with the king uncastled. So you can castle now, or at move 2, or at move 3, etc. The only problem with delaying is that if you happen to overlook something that is too deep for your search to see, you treat castling at move 1, 2, ..., N as completely equal, when in reality, as N grows larger, the chances for overlooking something critical grows larger since your depth at move 1 is limited.

To a human, it is "I am castling now before something unexpected in the center might make it difficult to castle later." To the computer, it is "I can castle anywhere within the search horizon, and they are all equal since the decision is based only on the final position along the path...
User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

Well, the delayed-loss bonus cures that too: if castling is worth something, your score at the leaf on a branch where you castled, which propagates back to the root, will be higher than the current evaluation in the nodes before you castled. The opponent will see your castling there as a future unavoidable loss, and will thus harvest the bonus for every move between the root and the casting, which (seen from the castling side) will deduct from the score. So a branch where he castles early (or in fact immediately) will be worth more than one where he castles only late (to eventually reach the same position).
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Why minimax is fundamentally flawed

Post by bob »

hgm wrote:Well, the delayed-loss bonus cures that too: if castling is worth something, your score at the leaf on a branch where you castled, which propagates back to the root, will be higher than the current evaluation in the nodes before you castled. The opponent will see your castling there as a future unavoidable loss, and will thus harvest the bonus for every move between the root and the casting, which (seen from the castling side) will deduct from the score. So a branch where he castles early (or in fact immediately) will be worth more than one where he castles only late (to eventually reach the same position).
This might wreck havoc with the trans/ref table would it not? The instant you include path dependent information things get muddy. We can correct for mate scores since that is straightforward, but positional evaluation adjustments I have trouble visualizing.
User avatar
hgm
Posts: 27796
Joined: Fri Mar 10, 2006 10:06 am
Location: Amsterdam
Full name: H G Muller

Re: Why minimax is fundamentally flawed

Post by hgm »

Actually it is exactly the opposite. This is not really path-dependent info. That is, it does not depend on the path through which you reach the node from the root. What you hash is the path-independent eval score from the leaves, corrected according to the path between the leaves and the current node.

That is an intrinsic property of the position; each time you would encounter that same position, you would sprout the same sub-tree from it, which would apply the same correction to the score that was backed up from the leaf to the current node. There would never be any consistency. The inconsistencies occur when you start including info on the path between the root and the note (like distance to the root).

Micro-Max relies for the scoring of the mate distance entirely on the delayed-loss bonus. (On the path to a mate the score is of course always much higher than the current evaluation, so every move the opponent can delay the mate gives him the bonus, counting the length of the path.) There never is any need to correct what you store or retrieve from the hash table. It is automatically correct, no matter in what level of the tree you would hit on it.
Last edited by hgm on Mon Nov 10, 2014 6:42 pm, edited 1 time in total.