Author Topic: Games against Programs  (Read 318 times)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Games against Programs
« on: January 31, 2018, 05:21:07 pm »
Since we have several developers here and many different games represented, I thought it might be a good idea to have a section showcasing games against the programs. Annotate your games to help the programmers make even stronger versions of their creations!

Share on Facebook Share on Twitter


GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Joker80 vs. Ed Trice in Gothic Chess
« Reply #1 on: January 31, 2018, 05:52:33 pm »
I gave Joker80 a tryout today, thanks to H.G. for making this program available. I loaded it under the ChessV interface, thanks to Greg Strong for making his GUI flexible enough to do so.

Joker80 set to fixed depth searches of 12-ply. This way, programmers can most easily review the game on machines of any power and speed and produce the same result in every position.

Joker80 (white) vs. Ed Trice (black)

1. c4 Nh6
2. g3 Nc6
3. Nc3 g6
4. d3 Bg7

I used some form of this configuration, with and without ...d6 and ...Bd7, against almost any white setup. It forces my opponent to commit to a plan first. Often times it allows white to make the first mistake!

5. h4

This looks similar to the 2-move checkmate position where white lets black mate with one queen move in 8x8 chess. Even though this is 10x8 Gothic, I can't recommend this for white.

5...f6

The safest reply. Preventing Bg5 by white via this move or ...h6 when the Knight hasn't been placed on this post is almost always a good idea for black.

6. Bd5 e6
7. Be4 Af7

When playing black in Gothic, it is best to make simple and straightforward developing moves that get you closer to castling. Black is leading in this area concerning development.

8. h5?

An error. White needs to complete development before issuing any such move.

8...O-O!

I think this is better than the obvious ...f5 since if white captures black's piece activity only increases and white is making multiple moves with material that is just being removed.

9. hxg6 hxg6

The castled rook is now in a semi-open file, good for black. White still has the same piece deployment as in move 7.

10. Nh3 f5

Removes the pin, and frees up diagonal pathways for the black queen and dark-squared bishop. The only blemish for black is the prospectless queen's bishop, barricaded behind a same-colored pawn chain.

11. Bg5

A nice strike! This is another typical motif in Gothic Chess, since the knights are perfectly positioned to support interior strikes against the opponent (as opposed to the Lopezian strikes from the exterior in 8x8 chess). I was mulling over this on my prior move, and I came up with the easy remedy.

11...Bf6
12. Bxf6 Qxf6

Trading when behind in development only digs you into a deeper hole. One of white's developed minors is removed, and black gets a major piece into play as a result. Again, the undeployed black bishop is the only detriment.

13. Bf3 g5
14. Ai3

A move aiming to prevent the pawn push from g5 to g4. Can black get away with it anyway?

14...g4!

It's a matter of counting. Queen for an Archbishop + minor piece plus developing a supermajor is a beneficial trade for black.

15. Axf6 Cxf6
16. O-O

And white finds the most reasonable response right before the end of the search! It was looking at 16. Nb5?? which is a game-ending blunder.

16...exf3
17. Cxf3 d5

Black must open lines for the ostracized bishop, even though the future d-pawn is in a state of suspense and must be monitored every step of the way until it is eliminated.

18. cxd5 exd5
19. Nf4?

Blockading the pawn with 19. d4 was so much better. The typical idea is to stymie it then attack it later. In such a position, the middlegame begins in earnest. Black's pieces are ideally placed, so the question is, what to do with which one first? But now, there is a strong counter.

19...Be6!

Not just a dare, and better than ...d4 for the time being. Would white lose even more tempi by taking yet another move to go after a piece that has only made one move after having been sidelined so long?

20. Nb5?

This is called a "horizon effect move." The program can now see that NxB on e6 leads to progressively worsening positions for it. But black must "react" to Nb5, pushing the "worse scores" beyond the search horizon. The quintessential elements leading to these score still remain, they just can't trickle down from deeper nodes to the root once you insert the move Nb5.

20...Ne5!

A much stronger threat to deal with than white's threat of  Nxc7.

21. Cg1 Nhg4!!

This is the start of a "Tal combination." And, like a Tal combination, sometimes you don't know if you cooked your own goose. It's not possible to work it all out (at least for me) but it definitely lets me strike first while white is pursuing loot on a remote sector of the board.

22. Nxc7 Ci6!!

22...Nxf2 is what Joker80 (and everyone following along) expected. Notice the same move by ChessV in its earlier game against me had the same appeal: forking the queen and rook. But in the case of ChessV, white (me) had "quiet moves" as immediate replies that were strategic in nature and far-sighted, yet in this case the line was tactical and more short-ranged and therefore easier for the computer to forsee. I am pretty sure Joker80 doesn't see the danger in 21...Nhg4 and 22...Ci6

23. Cg2

Of course. But now the surprise.

23...Nxf2!

Making the idle threat of the fork anyway despite the Chancellor's hold on f2.

24. Cxf2 Ng4

The whole point of the combination. The Chancellor is overburdened.

25. Cg2 Ne3!

And the rare instance of a "desperado knight." In 8x8 chess, we see "desperado rooks" used in a variety of ways, and here the knight is poisonous and can't be touched.

26. Qg1 Rxh1+
27. Qxh1 Nxg2+
28. Qxg2 Rh8

That black rook was hanging since 22. Nxc7.

29. Ncxe6 Aj3+

A check made possible by that Chancellor pin set up with 22...Ci6!!

30. Kj1 Ah2+
31. Qxh2 Rxh2
32. Ri1

White has entrenched himself and a "technical phase" of the endgame has been reached. It's 2 knights and a pawn vs. a chancellor.

32...Ci4

Played for the smothered checkmate with ...Ch2 once the rook is placed elsewhere. White has plenty of time to deal with this.

33. Rc1 Rf2
34. Ng7+ Kh7
35. Rh1+

White begins sacrificing material to delay checkmate. But here ...Kxg7 allows the annoying Nh5+ and breathes some life into the game for white. I decide to hide behind his knight.

35...Kg8
36. Nh3 Rf1!

A nice little combo you can't do in chess.

37. Rxf1 Ch2+
38. Ki1 Cxf1+
39. Ng1 Cxg1+
40. Kh2 Cxe2+
41. Kh3 Kxg7

And hopefully everyone will agree this is a win for black.
« Last Edit: January 31, 2018, 08:19:38 pm by GothicChessInventor »

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #2 on: February 01, 2018, 05:38:58 am »
Congratulations!

I am a bit puzzled by the fact that Joker80 allowed itself to be forked with 14... g4. From what I know now about piece values, it seems the game is lost from that point on. It just bugles away a Bishop for a Pawn. And on a 10x8 board a Bishop is worth more than on 8x8. And in computer Chess a Pawn is worth only about a quarter of a minor anyway, if it isn't an advanced passer in the end-game (rather than the 1/3 of a minor you would expect from the classical piece values 1:3:3:5:9). The only other compensation it gets for the Bishop is a Q-for-A trade, but this is worth only ~3/4 Pawn. So it gives 350cP (a Bishop) for 75cp (Q-A) + 85cP (P) ~ 160 cP, a loss of about 190 cP.

Yet, even after the trade has fully materialized, if I have Joker80 think about the position, it only sees 50cP advantage for black at the level of static evaluation and Quiescence Search. So it must have piece values that are very far off. (The executable I used is older than the source code I e-mailed you, however.)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #3 on: February 01, 2018, 10:12:07 am »
Congratulations!

I am a bit puzzled by the fact that Joker80 allowed itself to be forked with 14... g4. From what I know now about piece values, it seems the game is lost from that point on. It just bugles away a Bishop for a Pawn. And on a 10x8 board a Bishop is worth more than on 8x8. And in computer Chess a Pawn is worth only about a quarter of a minor anyway, if it isn't an advanced passer in the end-game (rather than the 1/3 of a minor you would expect from the classical piece values 1:3:3:5:9). The only other compensation it gets for the Bishop is a Q-for-A trade, but this is worth only ~3/4 Pawn. So it gives 350cP (a Bishop) for 75cp (Q-A) + 85cP (P) ~ 160 cP, a loss of about 190 cP.

Yet, even after the trade has fully materialized, if I have Joker80 think about the position, it only sees 50cP advantage for black at the level of static evaluation and Quiescence Search. So it must have piece values that are very far off. (The executable I used is older than the source code I e-mailed you, however.)

Send me the latest version of the program and we can test it. That is the whole reason for this area. The program played AxQ very quickly, so you might want to look at your capture code. If the program only evaluated captures and never returned from the quiescence() routine I would expect such behavior.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #4 on: February 01, 2018, 10:21:10 am »
Ed Trice vs. ChessV at 3 minutes per move using an Intel i7-5960X @ 4.6 GHz (8 cores)

It should be noted that I deliberately played "anti-computer" moves in an attempt to confound the software. As a programmer and good Gothic Chess player, I can get most programs into trouble if I "put on my thinking cap" as my dad used to say. The moves I played were not "tactically unsound" but they were most often "strategic combinations" with a long distance goal as the objective. It's easy for a human to see if the goal is clear-cut without too many intervening complications. Such was the case here.

1. d4 d5
2. Nh3 Nc6
3. i3

The first step to defeating a program: play positionally and avoid tactics. This is a slow, developing move that programs can't decipher. It looks to "weaken" the kingside from the perspective of most evaluation functions, but it is simply preparing to castle, which is always a good idea in Gothic Chess.

3...g6
4. c3 h5?

Black is self-inflicting wounds already.

5. Bi2 e5
6. dxe5 Nxe5
7. f4 Ng4

A move with the aim of forcing the white archbishop to "babysit" the h2 square, otherwise the fork ...Nxh2+ picks up the rook on j1. This motif is ubiquitous in Gothic Chess, and many games feature such play. However, here, the program is missing the most obvious way to dodge the veiled threat made by this knight.

8. Ac5+ Ae7

Of course, trading archbishops by using the tempo of check to castle out of danger.

9. Axe7+ Cxe7
10. O-O Qd6?

The game is functionally over already from a strategic point of view. All this move does is allow a trivial skewer threat along the a3-f8 diagonal, which is the diagonal on which the game ends very shortly.

11. b3 Bf5

Ignoring the threat of Ba3 with the mistaken belief that blocking with the pawn move to c5 is "safe enough." Even though the program is completing 12- and 13-ply searches, the danger associated with the bishop on a3 is actually permanent, and not temporary. Programs have an impossible task if they wish to try and label such positional stratagems.

12. e4 Bxe4

I decide to donate a pawn to start "tilting" the alpha-beta window. As the program is now a "pawn ahead," literally every move it searches will be good for it and any lurking danger will be beyond its search horizon. This is the perfect square to lure the bishop onto, since there is a semi-pin on it considering my chancellor is gunning down the e-file and with Ng5 I compound the attack on it on e4.

13. Ba3 c5

Making this move now since BxN on b1 would deny the safety of deploying it.

14. Ng5 Nf2

Allowing black to fork my queen and rook with its forlorn knight now on f2, because my rook is actually quite safe. I will further illustrate this in upcoming moves by planting the rook directly in harm's way where the knight can capture it.

15. Qe2!

The game is definitely over now. Get out your scorecards and start counting how many hanging pieces white allows. Currently I am down one pawn and allowing the knight to take my rook.

 15...Nd3

And the knight declines winning The Exchange, wisely. I thought with the extra pawn it was ahead, it would grab it and allow Nh7+ inflicting more than collateral damage. This is actually a good move for black.

16. Cd1

White really doesn't have a choice here. One thing I have noticed in all of my years of play, if one side plays Cc2 (or Cc7 as black) that almost never works out well. Chancellors need to be treated as rooks until the late middlegame, where they become more deadly.

16...f5

This move basically turns the black bishop on e4 into a pawn. It has no safe moves anymore. It does stop Nh7+ by virtue of allowing the chancellor to cover that square, free from any pawn obstructions on the 7th rank now.

17. Nd2 Nh6
18. Re1!!

A move which wins in all variations. Black has closed the position and white needs to pry it open in order to exploit the defects in the enemy camp.

 18...Nxe1
19. Ndxe4!!

And white does the unthinkable, capturing the "bad bishop" while letting the knight that took the rook remain unscathed. The knight on e1 is dead meat anyway, and by keeping it around the program is burdened with move generation for it to no avail. The white knight on e4 is impervious to the pawn threats to capture it. White is now down a Rook and a pawn for a mere bishop, and one knight is en prise. These are the types of positions that confuse programs.

19...Qc7
20. Nh7+!!

And white sacrifices another knight!

20... Cxh7
21. Cxd5!!

Leaving the black knight on e1, and only capturing the "mission critical" d5 pawn for it while leaving the knight on e4 hang, still.

21...Kg8??

Going from the frying pan to the fire.

22. Qc4!

Again, setting up play with the concept of a deadly pin rather than try and recover material or save the hanging knight. None of these moves would ever make it "within the bounds" of an alpha-beta search window. Yet they are deadly.

22...Nxg2+

A spite check if there ever was one. The materialistic computer snags another pawn. The move is about as worthless as they come.

23. Kh1 Qf7
24. Ng5 Nxf4

Look at all of the threatened pieces in this position.

25. Ce7+!!

I decide to let the black king take my chancellor. Not now, but in 2 moves. The program still doesn't understand. How can it be so far ahead in material and still be losing?
 
25...Kf8
26. Nxh7+ Kxe7

27. Qxc5+

And now that a3-f8 diagonal is fatal.

27... Ke8
28. Re1+ Ne6
29. Qd6 Be5

The program must start tossing pieces to stop the checkmate. It's a cake walk from there to the end.

30. Rxe5 a5
31. Rxe6+ Qxe6
32. Qxe6+ Kd8
33. Qe7+ Kc8
34. Bd6 Ng8
35. Qc7#

Towards the end of the game, Chess V was showing "depths" beyond that which were reachable. This points to a bug in the program. The depth is increasing past the mate in 3 about to be delivered.


« Last Edit: February 01, 2018, 11:18:41 am by GothicChessInventor »

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Games against Programs
« Reply #5 on: February 01, 2018, 11:52:42 am »
Hmmm... yeah, something is wrong.  I think I just need to cut off the iterative deepening loop when a couple successive iterations return a checkmate score.  I'm not sure it's searching beyond depths that can be reached, though.  White isn't forced to deliver the checkmate so the game can go for another 25 ply.   True, the vast majority of that stuff should be pruned but not all will be.

Thanks for taking the time, by the way, to give us some useful analysis so we can improve our engines!

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #6 on: February 01, 2018, 01:11:33 pm »
There are two issues here: mate-distance pruning and stopping the root iteration. After you find a mate score, the only reason to search on is to find a faster mate. Once you have exhaustively searched every line to, say, 7 ply, it is not possible that there is a mate in less than 7 ply in nodes that you haven't searched yet. Now this situation probably doesn't correspond to the 7-ply iteration in the root, because of various reductions. But searching beyond 11 ply is probably overdoing it.

The second problem is that it doesn't only continue with iterations that cannot possibly turn up anything better, but that those iterations also progressively start to take up more time. So apparently the search continues to extend lines that do not lead to mate, to a depth that is already beyond the mate. If the best root score so far is a mate in N ply, (as you can see from alpha), it is pointless to search further than N-1 ply from the root, because even if the next ply performs the checkmate, it will still not be faster than what you already had. So you can just return alpha for a fail low, even if the requested depth was far larger. With such mate-distance pruning the tree would not grow larger anymore once every branch has reached the depth of the mate.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #7 on: February 01, 2018, 01:54:20 pm »
Hmmm... yeah, something is wrong.  I think I just need to cut off the iterative deepening loop when a couple successive iterations return a checkmate score.  I'm not sure it's searching beyond depths that can be reached, though.  White isn't forced to deliver the checkmate so the game can go for another 25 ply.   True, the vast majority of that stuff should be pruned but not all will be.

Thanks for taking the time, by the way, to give us some useful analysis so we can improve our engines!

Greg, the whole point of the alpha-beta search is to avoid searching the unnecessary. When there is a definitive mate encountered at a depth d, your program should return "mate score - d" if maximizing and "d - matescore" when minimizing.

If that score gets backed up to the root, then so far, there is a "mate in d" ply.

Before you increment your depth counter and proceed to the next "level" of search, examine the best score so far.

If ("mate score" - abs(best score so far)) == current depth just completed, there is NO NEED to increment the level and proceed.

Say your mate score is 20000 and there is a mate in 5 moves. The program will discover this after completing depth 9, where the 5th move for white delivers the mate and the other side made 4 moves. So the score would be set to 20000 - 9 = 19991. If there was any way to delay the mate, the program would sacrifice material to prevent this, but since that did not happen, this must be a definitive mate.

Now you are about to increment your depth variable to 10 and start ply 10. But right now it is at 9.

You examine "mate score - 9" and you get 20000 - 9== 19991.

Your best score is 19991. You can stop the search.

It should be noted that "d" here is the total depth from the root, INCLUDING any quiescence depth reached or any type of extension. So if you are running down a line in a series of "ridiculous captures" that programs must play out to reach a quiet position in order to return a score, don't return "mate score - nominal search depth" but "mate score - however deep you are" which includes all of the "nonsense" extensions. These pointless lines that occur are what keep programs from falling into those tactics I threw at them. Look how much material I was able to give away and still get both Joker80 and ChessV into trouble.

Your programs must each be pruning in turbulent positions without letting these "ridiculous" give away lines reach their terminous. And I say "ridiculous" not in a demeaning way, it is just what they are in reality in 99.9999% of the cases. However, in my particular instance, the giveaway line was perfectly valid as I could envision a way to get my material back "with interest" as they say.

Even at depth 9 and 10 it is possible to hit 30-40 plies if you let the captures run amok. As long as your quiescence search is bounded by alpha and beta, it won't go to the extreme. But it is absolutely necessary in order to make a program stronger.


« Last Edit: February 01, 2018, 02:11:50 pm by GothicChessInventor »

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Games against Programs
« Reply #8 on: February 02, 2018, 12:04:13 am »
There are two issues here: mate-distance pruning and stopping the root iteration. After you find a mate score, the only reason to search on is to find a faster mate. Once you have exhaustively searched every line to, say, 7 ply, it is not possible that there is a mate in less than 7 ply in nodes that you haven't searched yet. Now this situation probably doesn't correspond to the 7-ply iteration in the root, because of various reductions. But searching beyond 11 ply is probably overdoing it.

The second problem is that it doesn't only continue with iterations that cannot possibly turn up anything better, but that those iterations also progressively start to take up more time. So apparently the search continues to extend lines that do not lead to mate, to a depth that is already beyond the mate. If the best root score so far is a mate in N ply, (as you can see from alpha), it is pointless to search further than N-1 ply from the root, because even if the next ply performs the checkmate, it will still not be faster than what you already had. So you can just return alpha for a fail low, even if the requested depth was far larger. With such mate-distance pruning the tree would not grow larger anymore once every branch has reached the depth of the mate.

Right.  In addition to not cutting off the root iteration, I have not implemented mate-distance pruning...

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #9 on: February 02, 2018, 03:29:27 am »
In Fairy-Max the mate-distance pruning comes as a free side effect of the way I determine mate distance. Rather than assigning a different score to a checkmate depending on where it is in the tree, Fairy-Max always scores them the same. (It is actually capture of the King that receives special scoring, +INF.) It uses the general mechanism of a 'delayed-loss bonus' to make sure it prefers the fastest mate (or the fastest way to gain something in general): at the end of the node it adds 1 eval point if the node's score was below the current static evaluation (meaning a forced loss occurs in the future). Mated-in-N scores are of course always below static evaluation scores, and are thus passed to the parent as 'mate-in-(N+1)' scores.

To make sure that post-incrementing a score doesn't interfere with alpha-beta (i.e. cannot move scores that are bounds because they where out of the search window into that window, where they would be mistaken for exact scores), alpha and/or beta must be pre-decremented when they are below the current evaluation. In situations with mate scores this leads to decrementing beta, so that for the side that is going to be checkmated beta can actually be pushed to below -INF, when that side managed to delay the mate long enough compared to the branch where it was already detected. In that case the initial score of -INF you would start with in full-width nodes is already >= beta, and gives an immediate beta cutoff similar to the stand-pat cutoff in QS, before you have searched any moves!

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #10 on: February 02, 2018, 10:35:33 am »
In Fairy-Max the mate-distance pruning comes as a free side effect of the way I determine mate distance. Rather than assigning a different score to a checkmate depending on where it is in the tree, Fairy-Max always scores them the same. (It is actually capture of the King that receives special scoring, +INF.) It uses the general mechanism of a 'delayed-loss bonus' to make sure it prefers the fastest mate (or the fastest way to gain something in general): at the end of the node it adds 1 eval point if the node's score was below the current static evaluation (meaning a forced loss occurs in the future). Mated-in-N scores are of course always below static evaluation scores, and are thus passed to the parent as 'mate-in-(N+1)' scores.

To make sure that post-incrementing a score doesn't interfere with alpha-beta (i.e. cannot move scores that are bounds because they where out of the search window into that window, where they would be mistaken for exact scores), alpha and/or beta must be pre-decremented when they are below the current evaluation. In situations with mate scores this leads to decrementing beta, so that for the side that is going to be checkmated beta can actually be pushed to below -INF, when that side managed to delay the mate long enough compared to the branch where it was already detected. In that case the initial score of -INF you would start with in full-width nodes is already >= beta, and gives an immediate beta cutoff similar to the stand-pat cutoff in QS, before you have searched any moves!

That is a complicated way of doing something that can be achieved with a simple "mate - true distance from root" exact score.

Additionally, what happens if you get a fail-high or fail-low later in the search at the same depth where you found a mate and altered the bounds only by 1 point? When you complete that iteration of the search, your "mate in n" score that is no longer outside of the shifting bounds would be identified.... how?

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #11 on: February 02, 2018, 11:27:43 am »
It isn't really complicated; the only code it requires is three simple assignment statements. At the start of the node

alpha -= (alpha < currentEval);
beta -= (beta <= currentEval);


and at the end

bestScore += (bestScore < currentEval);

You would need a similar or even larger amount of extra code to adapt mate scores with the distance to root to make sure they show up right in the root, and correct for that while storing and probing in the transposition table.

I am not sure what you mean by 'later in the search'. There is no inconsistensy: the search window is shifted down when propagating towards the leaves; the score is shifted back up when propagated back towards the root. It is just like each level of the tree has its own, slightly shifted zero point of the score scale, so that transferring scores from one tree level to the next needs to translate the score to the new scale by adding or subtracting 1 quantum.

And the delayed-loss bonus does more than just accounting for DTM. For one, it gives you automatic mate-distance pruning, as explained earlier; with the root-distance method you would have to program that separately. In addition, it also works for other gains than checkmates. The engine will always take the shortest path to the best forcible position within its horizon. Plain minimax / alpha-beta doesn't do that; it only cares whether you reach it in the leaves, but not where along the branch towards the leaf. This can be a problem with 'bumpy evaluations', like you often encounter in late end-games like KBNK, where you temporarily have to allow the bare King to flee away from the edge, to drive it back later and closer to the fatal corner. The evaluation doesn't like that. So if you look along the line of optimal play the static evaluation goes up and down, and then up to an even higher local maximum, etc. If the seach has the nearest local maximum well within its horizon, but not the higher maximum beyond it, it wouldn't see any reason to immediately start pushing towards that local maximum, and speding the rest of the depth there. First wasting time deep in the valley, until just enough moves are left to climb to the nearest maximum, scores just as much. And there are always many more ways to waste time than to take the best path. So wasting time is what it will do, and will continue to do forever (as from that valley the next-higher summit will never come into view, it will only be able to see that when it has mounted the nearest maximum). Even 50-move blackmail would not help to make it finally do something, because the nearest maximum does ot involve a capture or Pawn push, and at some point it will just see "hey, that's strange... now it will be draw in X moves whatever I do!" WIth a delayed loss bonus a maximum will look lower if it lies further away, so the engine will start climbing it as fast as it can. And once it reaches the top, it then can see the next-higher maximum, and goes as fast as it can there, etc. A delayed-loss bonus is really a very good cure for indecisive play.

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Games against Programs
« Reply #12 on: February 03, 2018, 09:33:26 pm »
It isn't really complicated; the only code it requires is three simple assignment statements. At the start of the node

alpha -= (alpha < currentEval);
beta -= (beta <= currentEval);


and at the end

bestScore += (bestScore < currentEval);

You would need a similar or even larger amount of extra code to adapt mate scores with the distance to root to make sure they show up right in the root, and correct for that while storing and probing in the transposition table.

I am not sure what you mean by 'later in the search'. There is no inconsistensy: the search window is shifted down when propagating towards the leaves; the score is shifted back up when propagated back towards the root. It is just like each level of the tree has its own, slightly shifted zero point of the score scale, so that transferring scores from one tree level to the next needs to translate the score to the new scale by adding or subtracting 1 quantum.

And the delayed-loss bonus does more than just accounting for DTM. For one, it gives you automatic mate-distance pruning, as explained earlier; with the root-distance method you would have to program that separately. In addition, it also works for other gains than checkmates. The engine will always take the shortest path to the best forcible position within its horizon. Plain minimax / alpha-beta doesn't do that; it only cares whether you reach it in the leaves, but not where along the branch towards the leaf. This can be a problem with 'bumpy evaluations', like you often encounter in late end-games like KBNK, where you temporarily have to allow the bare King to flee away from the edge, to drive it back later and closer to the fatal corner. The evaluation doesn't like that. So if you look along the line of optimal play the static evaluation goes up and down, and then up to an even higher local maximum, etc. If the seach has the nearest local maximum well within its horizon, but not the higher maximum beyond it, it wouldn't see any reason to immediately start pushing towards that local maximum, and speding the rest of the depth there. First wasting time deep in the valley, until just enough moves are left to climb to the nearest maximum, scores just as much. And there are always many more ways to waste time than to take the best path. So wasting time is what it will do, and will continue to do forever (as from that valley the next-higher summit will never come into view, it will only be able to see that when it has mounted the nearest maximum). Even 50-move blackmail would not help to make it finally do something, because the nearest maximum does ot involve a capture or Pawn push, and at some point it will just see "hey, that's strange... now it will be draw in X moves whatever I do!" WIth a delayed loss bonus a maximum will look lower if it lies further away, so the engine will start climbing it as fast as it can. And once it reaches the top, it then can see the next-higher maximum, and goes as fast as it can there, etc. A delayed-loss bonus is really a very good cure for indecisive play.

Ok, it took me a while to get my mind around this.  I think I understand why it works.  And it seems to be significantly simpler than the alternative.  You don't need specific mate-distance-pruning code, and you don't need the code to adjust mate scores when reading and writing from the TT.  And it has the added advantage of solving the mate-distance-pruning issue in more general cases.  Very clever innovation.  I wonder why other programs aren't doing this.  There are no others that I'm aware of.  True, some programs don't do a full eval at every node and this approach requires that, but I think most engines do that now.  ChessV does full eval at every node, so I think I'm going to give this a try.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #13 on: February 04, 2018, 05:11:57 am »
Even when you don't want to do a full evaluation in every node, you could use the same idea with some other score replacing currentEval. E.g. when you would replace that by -INF+MATERANGE it would add the bonus only for delaying a mate (with as consequence the opponent would always go for the fastest path to mate). It then would have no effect on other gains. You could also put it at the incrementally calculated material eval (usually also including PST). In that case it would cause the engine to take the fastest path to material gains, even if no follow-up gain would be visible between that gain and the horizon. Usually there is a backlash after a gain, because you have been busy securing the gain while in the mean time the opponent could already write it off as a loss, and prepare some form of retaliation. This would encourage the engine to postpone the gain to just at the horizon, pushing the retaliation over the horizon. The next move the horizon would have advanced, so it would plan to postpone it even more, if it can, preferably never cashing it at all. The delayed-loss bonus counteracts this, but if the backlash is too large, one score quantum would probably not be enough to entirely solve it. Having a larger bonus would require more complex code, however, as you want the score after bonus to be a monotonous function of the score before the bonus. And you would have to think very hard how you would have to adapt alpha and beta to prevent that out-of-window scores (i.e. bounds) could ever be shifted in window and be mistaken for exact. (This would lead to arbitrarily large blunders.)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #14 on: February 04, 2018, 08:31:26 am »
Even when you don't want to do a full evaluation in every node, you could use the same idea with some other score replacing currentEval. E.g. when you would replace that by -INF+MATERANGE it would add the bonus only for delaying a mate (with as consequence the opponent would always go for the fastest path to mate). It then would have no effect on other gains. You could also put it at the incrementally calculated material eval (usually also including PST). In that case it would cause the engine to take the fastest path to material gains, even if no follow-up gain would be visible between that gain and the horizon. Usually there is a backlash after a gain, because you have been busy securing the gain while in the mean time the opponent could already write it off as a loss, and prepare some form of retaliation. This would encourage the engine to postpone the gain to just at the horizon, pushing the retaliation over the horizon. The next move the horizon would have advanced, so it would plan to postpone it even more, if it can, preferably never cashing it at all. The delayed-loss bonus counteracts this, but if the backlash is too large, one score quantum would probably not be enough to entirely solve it. Having a larger bonus would require more complex code, however, as you want the score after bonus to be a monotonous function of the score before the bonus. And you would have to think very hard how you would have to adapt alpha and beta to prevent that out-of-window scores (i.e. bounds) could ever be shifted in window and be mistaken for exact. (This would lead to arbitrarily large blunders.)

Try this in 8x8 chess using your idea:

1.e4 e5
2.Nf3 Nc6
3.Bc4 Nd4
4.Nxe5 Qg5
5.Nxf7 Qxg2
6.Rf1

Black to move. Does it show mate in 2?