MTD-f: Extracting PV ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

MTD-f: Extracting PV ?

Post by Henk » Fri Jun 24, 2016 12:46 pm

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;

Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

Re: MTD-f: Extracting PV ?

Post by Henk » Fri Jun 24, 2016 1:04 pm

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

Code: Select all

            var r = Search&#40;depth, 0, guess - 1, guess + 1, Position.LastMove&#41;;
            if (!Position.Expired&#41; Debug.Assert&#40;r == guess&#41;;
            return guess; 

Karlo Bala
Posts: 300
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: MTD-f: Extracting PV ?

Post by Karlo Bala » Fri Jun 24, 2016 1:14 pm

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&#40;int depth, int initGuess&#41;
        &#123;
            var guess = initGuess;
            var lowerbound = -ABSearch.INFINITE_INT;
            var upperbound = ABSearch.INFINITE_INT;
 
            do
            &#123;
                int ub = &#40;guess == lowerbound&#41; ? ub = guess + 1&#58; ub = guess;
                guess = Search&#40;depth, 0, ub - 1, ub, Position.LastMove&#41;;
                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.
Best Regards,
Karlo Balla Jr.

Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

Re: MTD-f: Extracting PV ?

Post by Henk » Sat Jun 25, 2016 11:47 am

[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]

Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

Re: MTD-f: Extracting PV ?

Post by Henk » Sat Jun 25, 2016 12:12 pm

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]

Daniel Anulliero
Posts: 665
Joined: Fri Jan 04, 2013 3:55 pm
Location: Nice

Re: MTD-f: Extracting PV ?

Post by Daniel Anulliero » Sat Jun 25, 2016 12:14 pm

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 ..

Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

Re: MTD-f: Extracting PV ?

Post by Henk » Sat Jun 25, 2016 12:16 pm

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.

bob
Posts: 20362
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: MTD-f: Extracting PV ?

Post by bob » Sat Jun 25, 2016 2:43 pm

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..

Henk
Posts: 5544
Joined: Mon May 27, 2013 8:31 am

Re: MTD-f: Extracting PV ?

Post by Henk » Sat Jun 25, 2016 3:00 pm

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.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: MTD-f: Extracting PV ?

Post by kbhearn » Sat Jun 25, 2016 10:46 pm

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.

Post Reply