TalkChess.com

There is also MTD-f (Memory-enhanced Test Driver) Don't know how to get a PV for there are no exact scores in null window searches.

So I added an extra search at the end of the loop. But then I get only an one move PV.

Henk wrote:There is also MTD-f (Memory-enhanced Test Driver) Don't know how to get a PV for there are no exact scores in null window searches.

Code: Select all

 
        public int MTDF(int depth, int initGuess)
        {
            var guess = initGuess;
            var lowerbound = -ABSearch.INFINITE_INT;
            var upperbound = ABSearch.INFINITE_INT;
 
            do
            {
                int ub = (guess == lowerbound) ? ub = guess + 1: ub = guess;
                guess = Search(depth, 0, ub - 1, ub, Position.LastMove);
                if &#40;guess < ub&#41;
                &#123;
                    upperbound = guess;
                &#125;
                else lowerbound = guess;
            &#125;
            while (!Position.Expired && lowerbound < upperbound&#41;;
           
            return guess;
        &#125;

Try to collect the PV after the first move, like in PVS, but not from the last iteration but one before. That should be the PV in most cases. Perhaps always.

[Extracting PV not a problem anymore]

In the game below:
White: MTD
Black: PVS

Both using no other reductions/pruning.

Looks like PVS playing stronger.

[pgn]
[Event "Computer Chess Game"]
[Site "HP"]
[Date "2016.06.25"]
[Round "-"]
[White "SkipperWinb"]
[Black "SkipperWinb"]
[Result "0-1"]
[TimeControl "120"]
[Annotator "1. +0.00 1... +0.00"]

1. e3 {+0.00/5} d5 {+0.00/5 2.0} 2. d4 {+0.00/5 2.0} e6 {+0.10/5 2.0} 3.
Be2 {+0.00/5 2.0} Qd6 {+0.10/5 2.0} 4. Nf3 {-0.10/4 1.9} Qb4+ {+0.10/3 1.9}
5. c3 {+1.60/5 1.9} Qd6 {-1.50/3 1.9} 6. O-O {+1.50/4 1.9} c5 {-1.50/3 1.9}
7. Na3 {+1.60/4 1.8} c4 {-1.60/3 1.8} 8. Nb5 {+1.60/4 1.8} Qb6
{-1.40/4 1.8} 9. a4 {+1.40/4 1.8} Bd7 {-1.40/3 1.8} 10. Ne5 {+1.00/4 1.8}
Bxb5 {-1.00/4 1.7} 11. axb5 {+1.00/4 1.7} Qxb5 {-1.00/4 1.7} 12. b4
{+1.00/4 1.7} Be7 {-1.00/4 1.7} 13. Bd2 {+1.00/4 1.7} f6 {-1.10/4 1.7} 14.
Ra5 {+1.10/5 1.6} Qb6 {-1.10/5 1.6} 15. Qa4+ {+1.20/5 1.6} Nc6
{-1.10/5 1.6} 16. Nxc6 {+1.10/4 1.6} Qxc6 {-1.10/5 1.6} 17. Qa2
{+1.10/4 1.5} Qb6 {-1.20/4 1.5} 18. Bh5+ {+1.10/4 1.5} g6 {-1.00/5 1.5} 19.
Be2 {+1.00/4 1.5} f5 {-1.00/3 1.5} 20. Qa4+ {+1.10/4 1.5} Qc6 {-1.10/4 1.5}
21. Qa1 {+1.00/4 1.4} Qb6 {-1.00/3 1.4} 22. Ra4 {+1.10/3 1.4} Nf6
{-0.20/4 1.4} 23. Re1 {+0.00/4 1.4} O-O {+0.00/4 1.4} 24. Rf1 {-0.30/4 1.4}
Kg7 {+0.30/4 1.4} 25. Ra2 {-0.40/4 1.4} Ne4 {+0.40/4 1.4} 26. Bf3
{-0.50/4 1.3} h6 {+0.40/4 1.3} 27. Bxe4 {-0.40/4 1.3} fxe4 {+0.50/4 1.3}
28. b5 {-0.50/4 1.3} Bd6 {+0.80/4 1.3} 29. Rc1 {-0.90/4 1.3} Qc7
{+0.90/4 1.3} 30. Rxa7 {-0.90/5 1.3} Rxa7 {+0.90/5 1.2} 31. Qxa7
{-0.90/6 1.2} Bxh2+ {+0.90/5 1.2} 32. Kf1 {-0.90/5 1.2} Qf7 {+1.00/5 1.2}
33. Be1 {-0.90/5 1.2} Bb8 {+1.00/5 1.2} 34. Qa5 {-1.00/5 1.2} Bg3
{+1.00/5 1.2} 35. Rc2 {-0.90/5 1.2} Bh4 {+0.90/4 1.1} 36. Qa7 {-0.90/4 1.1}
Bd8 {+0.90/4 1.1} 37. b6 {-0.90/4 1.1} Bg5 {+0.90/5 1.1} 38. Re2
{-0.90/5 1.1} Bf6 {+0.90/5 1.1} 39. Kg1 {-0.90/4 1.1} Bh4 {+0.90/5 1.1} 40.
Kf1 {-0.90/4 1.1} Bg3 {+0.90/5 1.1} 41. Ra2 {-0.90/5 1.0} Bh2 {+0.90/5 1.0}
42. Ra1 {-0.90/4 1.0} Bb8 {+1.00/5 1.0} 43. Qa5 {-0.90/5 1.0} Bg3
{+0.90/4 1.0} 44. Ra2 {-0.90/4 1.0} Bh2 {+0.90/4 1.0} 45. Qa7 {-0.90/4 1.0}
e5 {+0.90/5 1.0} 46. Ra1 {-0.90/4 1.0} exd4 {+1.40/5 1.0} 47. exd4
{-1.40/4 1.0} Bg3 {+2.10/4 1.0} 48. f3 {-2.10/4 0.9} Bb8 {+2.20/5 0.9} 49.
Qa2 {-2.20/4 0.9} exf3 {+2.30/4 0.9} 50. Kg1 {-2.30/4 0.9} Qf4
{+2.30/4 0.9} 51. gxf3 {-2.30/4 0.9} Qxf3 {+2.20/4 0.9} 52. Qg2
{-2.30/4 0.9} Qe3+ {+3.40/5 0.9} 53. Bf2 {-3.00/5 0.8} Qxc3 {+3.00/5 0.9}
54. Re1 {-3.00/4 0.8} Qa5 {+3.00/4 0.8} 55. Re7+ {-3.00/4 0.8} Rf7
{+3.10/5 0.8} 56. Be1 {-3.10/4 0.8} Qb5 {+2.90/5 0.8} 57. Re6 {-2.90/4 0.8}
Qb1 {+2.80/4 0.8} 58. Qxd5 {-2.80/3 0.8} Qb2 {+3.40/4 0.8} 59. Qh1
{-3.40/3 0.8} Qxd4+ {+11.10/5 0.8} 60. Re3 {-11.10/4 0.8} Qxe3+
{+3355.44/5 0.8} 61. Kg2 {-3355.44/4 0.8} Qf3+ {+3355.44/5 0.7} 62. Kg1
{-3355.44/6 0.7} Qf1# {+3355.44/6 0.7}
{Xboard adjudication: Checkmate} 0-1
[/pgn]

Not so sure. Here evaluation rounded to 0.2 in (previous game 0.1).

[pgn]
[Event "Computer Chess Game"]
[Site "HP"]
[Date "2016.06.25"]
[Round "-"]
[White "SkipperWinb"]
[Black "SkipperWinb"]
[Result "1-0"]
[TimeControl "120"]
[Annotator "1. +0.00 1... +0.00"]

1. e4 {+0.00/6} e5 {+0.00/5 2.0} 2. Qh5 {+0.00/5 2.0} Bd6 {+0.00/5 2.0} 3.
Qg4 {+0.00/5 2.0} g5 {+0.00/4 2.0} 4. Na3 {+0.00/4 1.9} Bxa3 {+0.00/5 1.9}
5. bxa3 {+0.00/5 1.9} d5 {+0.00/5 1.9} 6. Qg3 {+0.20/5 1.8} f6
{-0.20/5 1.9} 7. Bb2 {+0.20/5 1.8} dxe4 {-0.20/5 1.8} 8. O-O-O
{+0.20/4 1.8} Qd5 {-0.20/5 1.8} 9. h4 {+0.20/4 1.8} g4 {-0.20/5 1.8} 10.
Re1 {+0.20/4 1.8} Na6 {-0.20/4 1.7} 11. Bxa6 {+0.20/4 1.7} bxa6
{-0.20/5 1.8} 12. Ne2 {+0.20/4 1.7} Qd6 {-0.20/4 1.7} 13. Qb3 {+0.20/4 1.6}
f5 {-0.20/4 1.7} 14. h5 {+0.20/4 1.6} c5 {-0.20/4 1.6} 15. Qg3
{+0.20/4 1.6} f4 {-1.00/5 1.6} 16. Nxf4 {+1.00/5 1.6} exf4 {-0.60/5 1.6}
17. Qh4 {+1.00/5 1.6} Nf6 {-1.00/4 1.5} 18. Bxf6 {+2.20/5 1.5} O-O
{-2.00/4 1.5} 19. Qg5+ {+1.60/5 1.5} Kf7 {-1.60/5 1.5} 20. Be5
{+1.60/4 1.5} Qd5 {-2.00/5 1.5} 21. Qxf4+ {+1.80/4 1.5} Ke7 {-1.80/5 1.5}
22. Qg3 {+1.80/4 1.4} Bf5 {-1.80/3 1.4} 23. Bg7 {+1.80/4 1.4} Rf7
{-1.60/4 1.4} 24. h6 {+1.60/4 1.4} Qxa2 {-1.60/3 1.4} 25. Qc7+
{+4.80/5 1.4} Ke6 {-4.60/5 1.3} 26. Qc6+ {+4.60/5 1.3} Ke7 {-5.40/5 1.3}
27. Qxa8 {+5.40/4 1.3} Qxa3+ {-5.20/4 1.3} 28. Bb2 {+5.20/5 1.3} Qa2
{-5.40/5 1.3} 29. f3 {+5.40/4 1.3} gxf3 {-5.40/4 1.3} 30. gxf3
{+5.40/4 1.3} Kd6 {-5.60/4 1.2} 31. fxe4 {+5.60/4 1.2} Bg4 {-5.80/4 1.2}
32. e5+ {+6.00/5 1.2} Kc7 {-6.00/5 1.2} 33. Re4 {+6.00/4 1.2} Bh3
{-6.00/4 1.2} 34. Re3 {+6.40/4 1.2} Rf1+ {-6.40/3 1.2} 35. Rxf1
{+7.60/6 1.2} Bxf1 {-7.60/5 1.1} 36. e6 {+7.80/5 1.1} Kb6 {-7.80/4 1.1} 37.
Qb8+ {+9.60/5 1.1} Ka5 {-9.60/5 1.1} 38. e7 {+9.60/4 1.1} Bb5 {-9.60/4 1.1}
39. Ra3+ {+10.40/4 1.1} Qxa3 {-12.20/7 1.1} 40. Bxa3 {+12.20/6 1.1} Ka4
{-12.40/5 1.1} 41. Bxc5 {+18.00/5 1.0} Ka5 {-18.80/5 1.0} 42. c4
{+18.80/4 1.0} Ka4 {-19.80/5 1.0} 43. e8=Q {+3355.44/5 1.0} Ka5
{-3355.44/5 1.0} 44. Qbxb5+ {+3355.44/6 1.0} axb5 {-3355.44/7 1.0} 45.
Qxb5# {+3355.44/6 1.0}
{Xboard adjudication: Checkmate} 1-0
[/pgn]

Henk wrote:
In the game below:
White: MTD
Black: PVS

Both using no other reductions/pruning.

Looks like PVS play stronger

TWO games is too few to say that .. you need around 600-1000 game to be sure "pvs version is stronger than mtd version" .. But sure you know that ..

Daniel Anulliero wrote:

Henk wrote:
In the game below:
White: MTD
Black: PVS

Both using no other reductions/pruning.

Looks like PVS play stronger

TWO games is too few to say that .. you need around 600-1000 game to be sure "pvs version is stronger than mtd version" .. But sure you know that ..

Mtd-f using guesses all the time.

He that toucheth pitch shall be defiled.
Who keeps company with the wolf will learn to howl.

Henk wrote:

Daniel Anulliero wrote:

Henk wrote:
In the game below:
White: MTD
Black: PVS

Both using no other reductions/pruning.

Looks like PVS play stronger

TWO games is too few to say that .. you need around 600-1000 game to be sure "pvs version is stronger than mtd version" .. But sure you know that ..

Mtd-f using guesses all the time.

He that toucheth pitch shall be defiled.
Who keeps company with the wolf will learn to howl.

There's no guesswork in MTD(f). It zeroes in on the exact score. Choosing the right starting point is an art-form however, and choosing an optimal approach to converge on the correct score is also. But it will give exactly the same result as PVS, the only difference being the time required. It is difficult (to impossible) to make it faster than PVS however, at least from my experimentation years ago. And the fact that few if any use it is another hint..

bob wrote:

Henk wrote:

Daniel Anulliero wrote:

Henk wrote:
In the game below:
White: MTD
Black: PVS

Both using no other reductions/pruning.

Looks like PVS play stronger

TWO games is too few to say that .. you need around 600-1000 game to be sure "pvs version is stronger than mtd version" .. But sure you know that ..

Mtd-f using guesses all the time.

He that toucheth pitch shall be defiled.
Who keeps company with the wolf will learn to howl.

There's no guesswork in MTD(f). It zeroes in on the exact score. Choosing the right starting point is an art-form however, and choosing an optimal approach to converge on the correct score is also. But it will give exactly the same result as PVS, the only difference being the time required. It is difficult (to impossible) to make it faster than PVS however, at least from my experimentation years ago. And the fact that few if any use it is another hint..

There is also a problem with search inconsistencies when adding other pruning to MTD(f).

Perhaps using alpha beta search is better than PVS for there you have a similar problem with search inconsistencies.

Perhaps using alpha beta search is better than PVS for there you have a similar problem with search inconsistencies.

There is no inconsistency problem in PVS - if the re-search disagrees with the scout search, you trust the re-search and move on. The only question is whether it overall saves you time or not (and if it doesn't you have problems to be looking at).

in mtd(f) you could indeed have difficulty though resolving search instabilities as there's no reason to pick one search over the other in terms of which to trust and it's possible that always trusting the most recent search may result in a continuing oscillation.