best move changes always

[bob]

At first i want to introduce me again (Older members may remember me)
In the 90s, i programmed "InmiChess". Due to time lack i stopped programming on it in 2000. InmiChess has implemented all "stand of the art" things and plays somewhat "ok".
Having more time now, and interest comes back, i started again to look into the source and let it play some matches......

The Question.
Looking into games of my program, there are often more or less 'non tactical positions', where my "dumb program" switches between two moves at each ply, with a score difference not worth it. (more or less random).
Evaluating a new "best move" is extremly time consumating, so while switching the best moves, it doesnt get deep in search and misses tactical things in deep plys.. (Hope that is understandable)

Any implementations known, which prevent "dumb switchings"?

I can't just implement, to not reevaluate the "new best move", if score differs only a little, cause in my program, i more or less only get back, that ist better. Only at reevaluating with more open window, i know how much its better...

greetings
Werner[/b]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

Did you test this idea to see if it can give some elo points to Crafty?

I think that it may be also interesting to test negative x in the first iterations(for example as long as you did not use more than 2% of the target time).

The idea is that you may get some differnet information in the hash and maybe this different information can help for better order of moves later.

Uri

Tried and rejected a long time back. The idea is that if you don't believe .05 improvement in the score is worthwhile, then why not have your evaluation compute in units of 1/20th of a pawn rather than 1/100ths?

[bob]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

I like this idea
Will test it next days. Think i will try to increase x in getting deeper in search. Maybe the idea can help getting one ply deeper too

Werner

[Your extremly fast and useful answers did not change since I left in 2000.Thanks.]

Fast, maybe. But useful? I tried this idea a long while back and found it was either worse, or just no better, depending on how wide you made that "gap". For example, a gap of +100 will overlook winning a pawn which is obviously bad...

[Eelco de Groot]

At first i want to introduce me again (Older members may remember me)
In the 90s, i programmed "InmiChess". Due to time lack i stopped programming on it in 2000. InmiChess has implemented all "stand of the art" things and plays somewhat "ok".
Having more time now, and interest comes back, i started again to look into the source and let it play some matches......

The Question.
Looking into games of my program, there are often more or less 'non tactical positions', where my "dumb program" switches between two moves at each ply, with a score difference not worth it. (more or less random).
Evaluating a new "best move" is extremly time consumating, so while switching the best moves, it doesnt get deep in search and misses tactical things in deep plys.. (Hope that is understandable)

Any implementations known, which prevent "dumb switchings"?

I can't just implement, to not reevaluate the "new best move", if score differs only a little, cause in my program, i more or less only get back, that ist better. Only at reevaluating with more open window, i know how much its better...

greetings
Werner[/b]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

Did you test this idea to see if it can give some elo points to Crafty?

I think that it may be also interesting to test negative x in the first iterations(for example as long as you did not use more than 2% of the target time).

The idea is that you may get some differnet information in the hash and maybe this different information can help for better order of moves later.

Uri

Tried and rejected a long time back. The idea is that if you don't believe .05 improvement in the score is worthwhile, then why not have your evaluation compute in units of 1/20th of a pawn rather than 1/100ths?

I think this is the same idea as Marco's suggestion of using a "grainy" evaluation function. Some versions of Fruit have this option too. What I don't like about it is that you are throwing some of the accuracy of your evaluation function away. It is a bit like the sampling error that was introduced with digitalized music back around 1985 when the CD format was introduced. This was supposed not detectable with a high enough sampling rate and yet CDs did not always sound as good as the best vinyl recordings could. Vinyl is still here!

The question posed by Werner is a good one though, I think it comes down to noise reduction in computerchess. There must be some industry techniques, like parallels from electrical engineering that could help thinking about the problem. A dumb way of going about it is surely just making sure that your evaluation gets more precise when two moves are close together, viz. rather than just accept the nullwindow search result at depth(Iteration) you can require that the nullwindow search has to go several plies deeper. In Ancalagon nullwindow searches go four ply deeper than the corresponding pv-searches, practically everywhere. At least I think they should but I have not rigorously implemented this requirement everywhere. Of course this changes drastically some of the response times of search.

This probably falls into the tuning category, rather than that general algorithms can be recommended. It depends on the program.

For Werner, at the moment I'm experimenting with structures like this, maybe something for you to try:

Code: Select all

	value = -search(pos, ss, -(alpha), newDepth + 4*OnePly, ply+1, true, threadID);
	if (value < alpha) alpha = Value((alpha + value - 0x60) >> 1);
        }
        nullwindowValue = value;

        value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
        EvalErrormargin = Value(abs(value - nullwindowValue));
        if (newDepth < OnePly && ply < Iteration + 5)
        {
	oldValue = value;
	value = -search_pv(pos, ss, -beta, -alpha, newDepth + OnePly, ply+1, threadID);
	LeafevalErrormargin = Value(Max(abs(value - oldValue), EvalErrormargin));
        }

But not sure yet how to use EvalErrormargin and LeafevalErrormargin Both these variables are not yet in use

Another problem with using alpha, or alpha + margin, in nullwindowsearches is that, if the actual value of a nullwindow search at depth x is almost exactly alpha (or alpha + margin), you have to try the best moves for both Black and White to get a correct result. In other words, the alpha beta window for a nullwindow search at depth x might almost as well have been +Infinity, -Infinity, instead of alpha, alpha + 1! Well maybe that is nonsense, the smaller window still does help, but it sure makes the null window search longer than you would like, in some cases!

Not sure what to do about this fundamental problem

Regards,
Eelco

[Eelco de Groot]

Trying to correct indentation:

Code: Select all

                value = -search(pos, ss, -(alpha), newDepth + 4*OnePly, ply+1, true, threadID);
                if (value < alpha) alpha = Value((alpha + value - 0x60) >> 1);
        }
        nullwindowValue = value;

        value = -search_pv(pos, ss, -beta, -alpha, newDepth, ply+1, threadID);
        EvalErrormargin = Value(abs(value - nullwindowValue));
        if (newDepth < OnePly && ply < Iteration + 5)
        {
                oldValue = value;
                value = -search_pv(pos, ss, -beta, -alpha, newDepth + OnePly, ply+1, threadID);
                LeafevalErrormargin = Value(Max(abs(value - oldValue), EvalErrormargin));
        }

[Eelco de Groot]

This is not very interesting I suppose but as an example of how the latest code is doing here the testposition I am using at the moment, from the last round in the Staunton Memorial in London, Short was playing an exceptional tournament and was singledhandely responsible for the defeat of the Dutch. In the last round Van Wely tried to stop the onslaught and did get a good position, Short praised his game but at move 37 Loek may have missed a better move. Both players agreed afterwards that 37. Bf1 would have been better but here the computer thinks that actually 37. Be2 or 37. Ke1 may have been best.


The new British number one (photo by Barry Martin for ChessBase)

The last Ancalagon version does find 37. Be2 but the move is not completely stable, after an hour there is a switch to 37. Ke1 and then back to 37. Be2. The really hard move seems to be 38. Nf3 after 37. Be2 and that is something Build 237 actually found faster than latest Build 240.

[Event "7th Staunton Memorial"]
[Site "London ENG"]
[Date "2009.08.17"]
[Round "10"]
[White "Van Wely,L"]
[Black "Short,N"]
[Result "0-1"]
[WhiteElo "2655"]
[BlackElo "2684"]
[EventDate "2009.08.08"]
[ECO "E34"]

1. d4 e6 2. c4 Nf6 3. Nc3 Bb4 4. Qc2 d5 5. cxd5 Qxd5 6. e3 c5 7. a3 Bxc3+
8. bxc3 O-O 9. Nf3 b6 10. c4 Qh5 11. Be2 Bb7 12. O-O Nbd7 13. a4 Qg6 14.
Qxg6 hxg6 15. Bb2 a5 16. Rfd1 Rfd8 17. Nd2 Rac8 18. f3 cxd4 19. exd4 Ba6
20. Kf2 Rc7 21. Rac1 Rdc8 22. Ba3 Ne8 23. f4 Bb7 24. Re1 Bc6 25. Bd1 Ndf6
26. g4 Rd7 27. Ke3 Rcd8 28. Bb2 Nd6 29. h3 Rc8 30. Ba3 Bb7 31. Be2 Ba6 32.
Bd3 Rc6 33. Rc2 Rdc7 34. Rec1 Rc8 35. Ke2 Kh8 36. Kd1 Nfe8 37. Ke2 Nf6 38.
Ke3 Kg8 39. g5 Nh5 40. d5 exd5 41. cxd5 Rxc2 42. Rxc2 Re8+ 43. Kd4 Bxd3 44.
Rc6 Nf5+ 0-1

What is best, 37. Bf1 what the human GMs preferred in the analysis after the game, 37. Be2 or 37. Ke1?

[d]2r1n2k/5pp1/bprnp1p1/p7/P1PP1PP1/B2B3P/2RN4/2RK4 w - -

Engine: Ancalagon 1.3 Weak Squares 180 Board Control middle game 50 endgame 50 Null move in quiescence Build 240 (Athlon 2009 MHz, 256 MB)
by Romstad, Costalba, Kiiski, de Groot

2.00 0:01 +0.70 37.h4 Nf6 38.Be2 (201.615) 169

2.04 0:01 +0.84 37.Rc3 Nf6 38.Ke2 Bb7 (312.578) 224

3.01 0:01 +0.88 37.Rc3 Nf6 38.Ke2 Kh7 39.Bxd6 Rxd6 (625.370) 325

3.03 0:02 +1.07 37.Ke1 Kg8 38.Kf2 R6c7 39.Kg3 Rc6
40.Bb2 Nf6 41.h4 R6c7 (1.057.813) 395

4.01 0:03 +0.94 37.Ke1 Kg8 38.Kf2 Nf6 39.Kg3 Rd8
40.Re1 (1.431.062) 448

5.01 0:03 +1.03 37.Ke1 Kg8 38.Kf2 Nf6 39.Kg3 Rd8
40.Re1 Rc7 41.Rb1 Rc6 42.Rcc1 (1.772.729) 478

5.05 0:05 +1.47 37.Be2 Kg8 38.Bf3 Rxc4 39.Nxc4 Rxc4
40.Rxc4 Nxc4 41.Be2 Ne3+ 42.Kd2 Bxe2
43.Kxe3 (3.130.940) 525

6.01 0:06 +1.52 37.Be2 Rd8 38.Bf3 Rc7 39.c5 bxc5
40.Rxc5 Ra7 41.h4 Kg8 42.Bb2 Bb7 (3.529.061) 544

7.01 0:07 +1.50 37.Be2 R6c7 38.c5 Bxe2+ 39.Kxe2 Nb7
40.Nf3 Kg8 41.c6 Nbd6 42.Ke3 Kf8
43.Ne5 (4.279.028) 582

8.01 0:08 +1.56 37.Be2 R6c7 38.c5 Bxe2+ 39.Kxe2 Nb7
40.Nf3 Kg8 41.c6 Nbd6 42.Ke3 Kf8
43.Ne5 Ke7 (5.775.898) 651

9.01 0:16 +1.60 37.Be2 R6c7 38.c5 Bxe2+ 39.Kxe2 Nb7
40.Nf3 bxc5 41.dxc5 Nd8 42.Bb2 Nc6
43.Be5 Nxe5 44.Nxe5 (11.770.965) 695

10.01 0:24 +1.56 37.Be2 R6c7 38.c5 Bxe2+ 39.Kxe2 bxc5
40.Rxc5 Nb7 41.Rxc7 Rxc7 42.Rc4 Rxc4
43.Nxc4 Nf6 44.Kf3 Nd5 45.Bc5 (18.488.542) 754

11.01 0:59 +1.64 37.Be2 Rd8 38.Bf3 Rc7 39.c5 bxc5
40.Bxc5 Bb7 41.Bb6 Rxc2 42.Rxc2 Bxf3+
43.Nxf3 Ra8 44.Rc5 Ne4 45.Rxa5 Nc3+
46.Kd2 Rxa5 47.Bxa5 Nxa4 (45.323.671) 756

12.01 1:38 +1.64 37.Be2 Rd8 38.Bf3 Rc7 39.c5 bxc5
40.Bxc5 Bb7 41.Bb6 Rxc2 42.Rxc2 Bxf3+
43.Nxf3 Ra8 44.Rc5 Ne4 45.Rxa5 Nc3+
46.Kd2 Rxa5 47.Bxa5 Nxa4 (78.069.485) 794

13.01 5:53 +1.62 37.Be2 Rd8 38.Bf3 Rc7 39.c5 bxc5
40.Rxc5 Ra7 41.Ke1 Bb7 42.Bxb7 Rxb7
43.Rxa5 Kg8 44.Ke2 (243.856.303) 690

14.01 11:41 +1.66 37.Be2 Rd8 38.Bf3 Rc7 39.c5 bxc5
40.Rxc5 Ra7 41.Ke1 Bb7 42.Bxb7 Rxb7
43.Rxa5 Kg8 44.d5 Nc7 45.Rc6 Nde8
46.dxe6 Nxe6 (486.404.603) 693

15.01 62:51 +1.47 37.Be2 Rd8 (2.333.048.037) 618

15.03 324:50 +1.49 37.Ke1 Nf6 38.Be2 Nde8 39.Nf3 R6c7
40.Ne5 Bb7 41.Kd2 Rd8 42.Ke3 Kg8
43.Bd3 Nd7 44.Rb1 Nxe5 45.dxe5 Rcd7
46.Rd2 Ba6 47.Rbb2 Rc8 48.Rxb6 Bxc4 (11.098.651.858) 569

16.01 372:18 +1.47 37.Ke1 Nf6 38.Be2 Nde8 39.Nf3 R6c7
40.Ne5 Bb7 41.Kf2 Kg8 42.Rb2 Rd8
43.Nf3 Be4 44.Ke3 Bxf3 45.Bxf3 Nd5+
46.Bxd5 exd5 47.Rxb6 Rxc4 48.Rxc4 dxc4
49.Rb5 (12.891.275.947) 577

16.02 503:57 +1.60 37.Be2 Rd8 38.Nf3 Bb7 39.Ne5 Rc7
40.c5 bxc5 41.Rxc5 Rxc5 42.Bxc5 Kg8
43.Bb6 Ra8 44.Rc5 Ne4 45.Rxa5 Nc3+
46.Ke1 Rxa5 47.Bxa5 Nxe2 48.Kxe2 (15.651.099.131) 517

17.01 712:13 +1.54 37.Be2 Rd8 38.Nf3 Bb7 39.Kd2 Kg8
40.Ne5 Rc7 41.Ke3 Nc8 42.Bd3 Nf6
43.Rb1 Nd7 44.Be4 g5 45.Bxb7 gxf4+
46.Kxf4 Nxe5 47.Kxe5 Rxb7 48.h4 (22.703.852.123) 531

Build 237 worse in the first plies but with a better branching factor, not using the code fragment above, last plies:

15.01 78:24 +1.64 37.Be2 Rd8 38.Nf3 Bb7 39.Ne5 Rc7
40.c5 bxc5 41.Rxc5 Rxc5 42.Bxc5 Bd5
43.Bb5 Kg8 44.Nc6 Rd7 45.Nxa5 Nxb5
46.axb5 (3.024.677.931) 642

16.01 153:26 +1.54 37.Be2 Rd8 38.Nf3 Bb7 39.Ne5 Rc7
40.c5 bxc5 41.Rxc5 Rxc5 42.Bxc5 Kg8
43.Bb6 Ra8 44.Rc5 Ne4 45.Rxa5 Nc3+
46.Ke1 Rxa5 47.Bxa5 Nxa4 (5.876.931.172) 638

best move: Bd3-e2 time: 379:00.656 min n/s: 553.972 nodes: 12.597.630.369

The main difference however is that later builds do less razoring which affects the branching factor:

Code: Select all

    // Null move search not allowed, try razoring
    else
	{
		if (   !value_is_mate(beta)
             && depth < RazorDepth
             && approximateEval < beta - RazorApprMargins[int(depth) - 2] + (approximateEvalTT ? Value(0x50) : Value(0))
             && ss[ply - 1].currentMove != MOVE_NULL
             && ttMove == MOVE_NONE
             && ss[ply - 1].reduction // New in last three builds 238-240
             && !pos.has_pawn_on_7th(pos.side_to_move()))
        {
            Value v = qsearch(pos, ss, beta-1, beta, Depth(0), ply, false, threadID);
            if (v < beta - RazorMargins[int(depth) - 2])
              return v;
        }
        if (isCheck && approximateEval > 0)
            perpetualExtension = true;
	}

Eelco

[Inmann]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

I like this idea
Will test it next days. Think i will try to increase x in getting deeper in search. Maybe the idea can help getting one ply deeper too

Werner

[Your extremly fast and useful answers did not change since I left in 2000.Thanks.]

Fast, maybe. But useful? I tried this idea a long while back and found it was either worse, or just no better, depending on how wide you made that "gap". For example, a gap of +100 will overlook winning a pawn which is obviously bad...

Implemented it last days in the following way.
In iterative deepening, i search 6 distanzes normal. Starting at distanz 7, i add 4 to alpha on root for non non pv moves. Increasing this factor till value 12 at iteration 11 and higher. (All only on root)
Idea is. In ply 7 i have hopefully a nice pv move (with exact value). Also the "Positional thing" should be "done" here. Deeper i just want to see, if one of the other moves are "really" better (more or less tactical). So a non pv move must be at leat 4 , later 12 points better. I just add this value at root to the alpha. On Research if something interesting found, i dont add a value again.(Damned to describe the thing...)

First tests on positions show me a tree half the size in many positions!!!
On my tactical suits, it missed nothing, but was faster. On 10 games of this version against prior versions, this versions won 6 and 2 draws.
Still find the idea interesting and tempting...

[bob]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

I like this idea
Will test it next days. Think i will try to increase x in getting deeper in search. Maybe the idea can help getting one ply deeper too

Werner

[Your extremly fast and useful answers did not change since I left in 2000.Thanks.]

Fast, maybe. But useful? I tried this idea a long while back and found it was either worse, or just no better, depending on how wide you made that "gap". For example, a gap of +100 will overlook winning a pawn which is obviously bad...

Implemented it last days in the following way.
In iterative deepening, i search 6 distanzes normal. Starting at distanz 7, i add 4 to alpha on root for non non pv moves. Increasing this factor till value 12 at iteration 11 and higher. (All only on root)
Idea is. In ply 7 i have hopefully a nice pv move (with exact value). Also the "Positional thing" should be "done" here. Deeper i just want to see, if one of the other moves are "really" better (more or less tactical). So a non pv move must be at leat 4 , later 12 points better. I just add this value at root to the alpha. On Research if something interesting found, i dont add a value again.(Damned to describe the thing...)

First tests on positions show me a tree half the size in many positions!!!
On my tactical suits, it missed nothing, but was faster. On 10 games of this version against prior versions, this versions won 6 and 2 draws.
Still find the idea interesting and tempting...

Lots of these kinds of things help "positions". Because the offset window makes the search go faster, so that you can get to the key tactical move quicker. But in real games it has hurt for any value >5, and values <= 5 showed no significant change.

10 games is _way_ too few to measure the difference in the two programs. You need 100000 games...

[Uri Blass]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

I like this idea
Will test it next days. Think i will try to increase x in getting deeper in search. Maybe the idea can help getting one ply deeper too

Werner

[Your extremly fast and useful answers did not change since I left in 2000.Thanks.]

Fast, maybe. But useful? I tried this idea a long while back and found it was either worse, or just no better, depending on how wide you made that "gap". For example, a gap of +100 will overlook winning a pawn which is obviously bad...

Implemented it last days in the following way.
In iterative deepening, i search 6 distanzes normal. Starting at distanz 7, i add 4 to alpha on root for non non pv moves. Increasing this factor till value 12 at iteration 11 and higher. (All only on root)
Idea is. In ply 7 i have hopefully a nice pv move (with exact value). Also the "Positional thing" should be "done" here. Deeper i just want to see, if one of the other moves are "really" better (more or less tactical). So a non pv move must be at leat 4 , later 12 points better. I just add this value at root to the alpha. On Research if something interesting found, i dont add a value again.(Damned to describe the thing...)

First tests on positions show me a tree half the size in many positions!!!
On my tactical suits, it missed nothing, but was faster. On 10 games of this version against prior versions, this versions won 6 and 2 draws.
Still find the idea interesting and tempting...

Lots of these kinds of things help "positions". Because the offset window makes the search go faster, so that you can get to the key tactical move quicker. But in real games it has hurt for any value >5, and values <= 5 showed no significant change.

10 games is _way_ too few to measure the difference in the two programs. You need 100000 games...

Maybe it helps and maybe it does not help but I suspect that you did not try it to know(you tried to do this trick for all iterations but Werner does it only from iteration 7).

Uri

[bob]

You can easily do this if you want. The solution is that after you search the first move and get a score of V, you start to search with an alpha-beta window of V+x, V+x+1, rather than the normal V, V+1. This means that a new score has to be at least X better before it will get backed up to the root. X can be whatever you want.

I like this idea
Will test it next days. Think i will try to increase x in getting deeper in search. Maybe the idea can help getting one ply deeper too

Werner

[Your extremly fast and useful answers did not change since I left in 2000.Thanks.]

Fast, maybe. But useful? I tried this idea a long while back and found it was either worse, or just no better, depending on how wide you made that "gap". For example, a gap of +100 will overlook winning a pawn which is obviously bad...

Implemented it last days in the following way.
In iterative deepening, i search 6 distanzes normal. Starting at distanz 7, i add 4 to alpha on root for non non pv moves. Increasing this factor till value 12 at iteration 11 and higher. (All only on root)
Idea is. In ply 7 i have hopefully a nice pv move (with exact value). Also the "Positional thing" should be "done" here. Deeper i just want to see, if one of the other moves are "really" better (more or less tactical). So a non pv move must be at leat 4 , later 12 points better. I just add this value at root to the alpha. On Research if something interesting found, i dont add a value again.(Damned to describe the thing...)

First tests on positions show me a tree half the size in many positions!!!
On my tactical suits, it missed nothing, but was faster. On 10 games of this version against prior versions, this versions won 6 and 2 draws.
Still find the idea interesting and tempting...

Lots of these kinds of things help "positions". Because the offset window makes the search go faster, so that you can get to the key tactical move quicker. But in real games it has hurt for any value >5, and values <= 5 showed no significant change.

10 games is _way_ too few to measure the difference in the two programs. You need 100000 games...

Maybe it helps and maybe it does not help but I suspect that you did not try it to know(you tried to do this trick for all iterations but Werner does it only from iteration 7).

Uri

So? Iterations 1-6 take a few microseconds. I did not cut it off at 7, but I did try varying the window offset by increasing it as depth increased. It simply didn't help unless the window got into the 5-10 range, and there it was a bit faster, but it dropped in Elo...

As I said...