Author Topic: Games against Programs  (Read 318 times)

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #30 on: March 27, 2018, 03:50:02 am »
The true cure is to put a term in the evaluation that adds the value of a piece in hand if its designated gating square still contains a virgin piece. That basically amounts to the same as your 'compound-piece' idea. It should not be very hard to implement, though: Virginity is easy to keep track of, and you already must be doing it anyway to keep track of castling rights. I don't know how you do that now, but one popular method is to have a word that contains a bit flag for each castling, and a 'spoiler' board size table that for each square lists which castlings are spoiled by activity on that square. Like (in MakeMove())

rightFlags |= spoiler[fromSqr] | spoiler[toSqr];

Then e1 and e8 would each spoil 2 castlings, a1, a8, h1 and h8 each one. If the four castling flags are the lowest four bits you can then use the rightFlags in the evaluation function as an index in a pre-calculated 16-entry table for a bonus for having castling rights. You can piggy-back virginity of other pieces on that as well, without extra cost. In Seirawan Chess I use the lowest two bytes of the rightFlags word, one byte for each group of 8 back-rank pieces, and these bytes can be used as index in a 256-entry gating-bonus table to see how much that virginity combination is worth. Which is the sum of the gating bonuses and the castling-rights bonuses. Actually this is a 4x256-entry table, the other index indicating which pieces you still have in hand. If you have nothing left in hand only King and Rook virginity is worth something. If you do have a piece in hand, having one or more virgin pieces is worth about the value of that piece. If you still have both pieces in hand, one virgin piece is worth the most-valuable of the two, two or more gating possibilities the sum of their values (and no castling-rights bonus if the only two are King + Rook). You can then add some extra positional bonus for having more choice. In Musketeer Chess this can be much simpler, as you know which virginity corresponds to which piece, and can use that to initialize the table at the start of the game.

The Pawn sacrifices to push the gating over the horizon are the typical consequence of large, irrealistic evaluation swings. In orthodox Chess they can already happen for pushing opponent castling over the horizon, if the castling rights are not worth enough, and the King-Safety difference between the King in the castled and virgin position is very large. To prevent it I award the King-Safety bonus the King would get in a castled position already to a King that has the right to castle there, with a discount factor depending on the number of occupied squares between Rook and King. This awards the bonus in smaller steps, rather than at once, reducing what the engine would be willing to sacrifice to push one such step over the horizon. It also helps at very low depth where the castling itself would be always beyond the horizon to encourage the engine to prepare for it by evacuating the squares, so that sooner or later it will get within the horizon.

I had similar problems in the late middle-game of Shogi variants, (e.g. Chu Shogi), where sliders like Rook and Bishop do promote (in a rather deep zone). The promotion is not as dramatic as P -> Q in Chess, but still worth far more than a Pawn. So the engine started to sacrifice Pawns to push opponent slider promotion over the horizon. Which is pretty silly, because as the board empties, promotion of these pieces cannot be postponed forever. (If only because in the end you run out of Pawns to sacrifice...) In the end I realized that promotion of these pieces is only a positional advantage, worth about the same as a tempo, and that the true strategic asset is promotability, plus the fact that the board is getting empty. So I made the evaluation already add a (possibly very large) fraction of the promotion gain to the score, in anticipation to the fact that these pieces will sooner or later promote. The fraction being determined by the board population ('game phase'), approaching 1.0 for an empty board. There was just one pitfall: if (compared to your opponent) too large a fraction of your piece value comes from these not-yet-realized promotions, he has an instant tactical superiority that might destroy you before the board is empty enough (or you simply had enough time) to promote anything. So the sum of these promotability bonuses must be made to saturate.

When large, unpredictable score jumps are unavoidable, (such as in the case of Pawn promotion, where you either lose the passer or it queens), the pain must be softened by searching the moves that gain the score in QS, and prevent that the opponent will stand pat in the face of a threat that would be unsolvable by extending one ply in QS.
« Last Edit: March 27, 2018, 06:02:14 am by HGMuller »

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #31 on: March 27, 2018, 09:20:53 am »
I have been looking at the alpha-beta routine as part of the problem in a Musketeer Chess implementation. Alpha-Beta wasn't really designed to handle a game with an opening phase like this. To prevent ridiculous "fails" of one kind or another, which trigger researches and just bloat the tree (causing more problems like not being able to reach a sufficient depth), I am coming up with a new kind of search that has additional parameters. It's basically an Alpha-Beta-Gamma-Delta function, that has not two but four competing terms; actually, more precisely, two pairs of competing terms. The idea is to mitigate instances where the Horizon Effect delays a Musketeer Piece introduction, yet maximizes instances where strong play forces the opponent to forgo introducing the Musketeer pieces without serious negative consequences. In essence, I have a Horizon Effect term added to each side. It keeps track of the "real" score without the piece introduction evaluation, and an algorithm determines to what extent the line of play is just trying to maximize one score with disregard of the other.

There are many details I am leaving out, but that was the gist of it. If it works, Planchet should be able to search much more deeply than it is now, with the lines of play much more meaningful.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #32 on: March 27, 2018, 10:23:00 am »
Well, I am sure standard alpha-beta search still has many weaknesses that can be improved upon. But this gating problem seems purely self-inflicted, by introducing a huge misevaluation in a subset of the positions (namely those with pieces in hand that are still gatable, and almost certainly will be gated), and then hoping that the search will correct it. Trying to make the search guess something the evaluation could already have known seems a very round-about way to solve it.

Most noticeable problems I have with iteratively deepening alpha-beta (when analyzing positions) is that when in a PV node (most noticeable the root) the score of the best move of the previous iteration experiences a large drop in the next, it takes 'forever' to complete the new iteration. Often it is an order of magnitude faster to just abort the analysis, and restart it (making sure the hash table is kept). Then the score that collapsed will be found in the hash table at high depth, good enough to be used at any lower depth, so that from d=1 on the search will start working on proving the other moves are worse than that low score. Sometimes aspiration helps, in particular if there was another move with a score close to that of the previous iteration, but if there isn't the aspiration would give you fail low after fail low.

Also annoying is that in an iteration where the PV score spectacularly drops, the search tends to switch to nonsense sacrifices (that cannot be refused), having the idea that it can play the PV that was no good unmodified after these sacrifices, as the sacrifice reduced the depth by two ply, so that the PV there still has the score from before the drop. It will then stick to the nonsense sacrifice even in the next iteration, before it has enough depth to see that the PV drops the same amount after the sacrifice, so that the latter just adds the loss of the sacrifice. Only then it switches to a reasonable alternative. I guess that after a PV drop it should just be forbidden (i.e. pruned) to play that same PV after reducing the depth to one where it still looked good with a sacrifice. But of course sometimes the sacrifice is really tactically connected to the PV drop, and does remove the problem that is waiting beyond the horizon to make the score drop.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #33 on: March 27, 2018, 04:09:21 pm »
But this gating problem seems purely self-inflicted, by introducing a huge misevaluation in a subset of the positions (namely those with pieces in hand that are still gatable, and almost certainly will be gated), and then hoping that the search will correct it. Trying to make the search guess something the evaluation could already have known seems a very round-about way to solve it.

It is even worse than that if you think about it. The program needs to "discover" what you would call the "gating gain." That is, it has no idea a piece is a deployer of the Musketeer piece until the move generator spawns that move, and then the score jumps with the piece dropped to the vacated square. But, fortunately, the History Heuristic is quick to note such thrashing of the alpha and beta bounds, and soon such moves have high history scores and are tried near the top of the move list.

Most noticeable problems I have with iteratively deepening alpha-beta (when analyzing positions) is that when in a PV node (most noticeable the root) the score of the best move of the previous iteration experiences a large drop in the next, it takes 'forever' to complete the new iteration.

Exactly! But do you want to know what the world's simplest cure is for this? You might laugh when I tell you. Perform "depth += 2" instead of "depth++" and you cure most of the odd/even "ply explosion" which bloats the tree depending on who has the last move! At least in the case of Musketeer Chess it has huge payoffs.


Also annoying is that in an iteration where the PV score spectacularly drops, the search tends to switch to nonsense sacrifices (that cannot be refused), having the idea that it can play the PV that was no good unmodified after these sacrifices, as the sacrifice reduced the depth by two ply, so that the PV there still has the score from before the drop. It will then stick to the nonsense sacrifice even in the next iteration, before it has enough depth to see that the PV drops the same amount after the sacrifice, so that the latter just adds the loss of the sacrifice.

This is compounded to the extreme in Musketeer Chess. My estimate is that 6-ply of additional search is needed to get a reasonable pv compared to just standard chess. If you want a program to play with the tactical foresight of a chess program that can hit 13-ply, you need 19-ply in Musketeer chess.
« Last Edit: March 27, 2018, 04:19:02 pm by GothicChessInventor »

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #34 on: March 27, 2018, 06:08:30 pm »
It is even worse than that if you think about it. The program needs to "discover" what you would call the "gating gain." That is, it has no idea a piece is a deployer of the Musketeer piece until the move generator spawns that move, and then the score jumps with the piece dropped to the vacated square. But, fortunately, the History Heuristic is quick to note such thrashing of the alpha and beta bounds, and soon such moves have high history scores and are tried near the top of the move list.
But valuing the virginity of that particular piece as the value of the piece it will gate, should completely solve that. And can be done with zero extra cost, if you already value castling rights. The gating rights are logically equivalent to castling rights, just of vastly higher value.

Quote
This is compounded to the extreme in Musketeer Chess. My estimate is that 6-ply of additional search is needed to get a reasonable pv compared to just standard chess. If you want a program to play with the tactical foresight of a chess program that can hit 13-ply, you need 19-ply in Musketeer chess.
Is that also in the middle-game, after all pieces have been gated in, or just in the opening phase? If so, what would be the reason? Just that there are more and more-powerful pieces, which leads to more complex tactics? Another reason for needing high depth can be that the evaluation sucks. (A perfect evaluation would only need a 1-ply search!) The engine then can only distinguish positionally good from positionally poor moves by searching deep enough that the material loss that in the long run follows from the poor positional moves will come within the horizon.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #35 on: March 27, 2018, 09:16:53 pm »
But valuing the virginity of that particular piece as the value of the piece it will gate, should completely solve that. And can be done with zero extra cost, if you already value castling rights. The gating rights are logically equivalent to castling rights, just of vastly higher value.

The problem with code such as "if the king castles, award this particular bonus" is that, at some point, you search beyond that, and the castle flag is changed, and the bonus no longer is awarded.

The way I handle it is "distance until castle flag is changed for the better," with distance being the depth of search. So if the king can no longer castle because he did castle, the bonus is "castle bonus - (ply * 2)" so that it is encouraged to castle quickly. If the king can no longer castle because the castle privilege was lost, the penalty is "lost castle penalty - (ply * 2)" so it can try to postpone the castling loss if possible.



Is that also in the middle-game,

Quote
This is compounded to the extreme in Musketeer Chess. My estimate is that 6-ply of additional search is needed to get a reasonable pv compared to just standard chess. If you want a program to play with the tactical foresight of a chess program that can hit 13-ply, you need 19-ply in Musketeer chess.

after all pieces have been gated in, or just in the opening phase? If so, what would be the reason? Just that there are more and more-powerful pieces, which leads to more complex tactics?

I meant in the opening, prior to the gating. Usually by the middlegame a few minors and pawns have been traded, so the branching factor is not that bad. The worst case is Dragon + Spider (I think) because the spider has like 20 legal moves and the Dragon is ridiculously strong. Those two on the board will grind the search to a near standstill beyond depth 11.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #36 on: March 28, 2018, 02:34:33 am »
The problem with code such as "if the king castles, award this particular bonus" is that, at some point, you search beyond that, and the castle flag is changed, and the bonus no longer is awarded.
This is not what I mean. When I say the engine should award a bonus for castling rights, I mean a bonus for being able to castle, but not having done it yet. The bonus for actually having castled would simply follow from the good King Safety you have in the castled position. If the program does not assign a value to the right to castle, it might inadvertantly squander the right by needlessly moving the King, at times where the castled position is still beyond the horizon.

So in fact it is just a bonus for the King and a Rook being virgin. At some point in the game you will trade that bonus for improved King Safety by actually castling. The bonus should be somewhat lower than the King Safety you can expect from castling, otherwise the program would not think this is a good trade, and rather postpone the castling to preserve the rights. (So the King Safety after a good castling should actually be worth more than having rights for both castlings!) This both makes that the program will not needlessly desroy its castling rights, and reduces the score jump you get from actual castling (which would cause horizon effect with silly Pawn sacrifices if it is too large).

Quote
The way I handle it is "distance until castle flag is changed for the better," with distance being the depth of search. So if the king can no longer castle because he did castle, the bonus is "castle bonus - (ply * 2)" so that it is encouraged to castle quickly. If the king can no longer castle because the castle privilege was lost, the penalty is "lost castle penalty - (ply * 2)" so it can try to postpone the castling loss if possible.
In my engines the delayed-loss bonus would take care of that automatically. Castling is just a move that reaps a large improvement of the evaluation score, and the delayed-loss bonus would encourage the search to find the fastest path to any such score improvement, be it mate, castling, passer advance or material gain through promotion or capture. So I don't have to treat castling special, I just have to make sure that the evaluation realizes that having the King on g1 or c1/b1 (without a Rook in the corner!) is a large positional advantage (e.g. by awarding points for the Pawn shield). Then as soon as the castled position gets within the horizon (and there is nothing that is even more profitable), it will embark on the fastest path to it (even if longer paths are also within the horizon).

The problem is that castling is often far away (if you count all distractions the opponent can interject in a typical opening, to which you have to react), so that it can be beyond the horizon altogether. Then you just have to hope that the general drive to develop pieces will eventually clear the path between King and Rook, bringing the castling closer so that it get within the horizon. In my more-advanced engines I solve that by having a dynamic bonus for the possession of castling rights, making it dependent on the number of empty squares between K and R. Another common problem is that engines destroy the Pawn shield before they have castled, if they are given too much opportunity to move their Pawns for other purposes, before actual presence of the King behind the Pawns would punish that in the evaluation. If you make the castling-rights bonus dynamic anyway, you can also make it depend on the quality of the Pawn shield on that wing, to prevent such behavior.


Quote
I meant in the opening, prior to the gating. Usually by the middlegame a few minors and pawns have been traded, so the branching factor is not that bad. The worst case is Dragon + Spider (I think) because the spider has like 20 legal moves and the Dragon is ridiculously strong. Those two on the board will grind the search to a near standstill beyond depth 11.
Well, that is purely an artifact of badly misevaluating the positions with gatable pieces. This forces the search to gate these pieces before the horizon or consider them lost, while in practice there would not be any reason to assume they could not be gated just as easily behind the horizon. So yes, with each two pieces in hand 4 plies will effectively get lost on gating moves, reducing the depth left to see the really important stuff by 4 ply, so that you need that extra depth to get the same tactical quality. Doing those extra 4 ply is very expensive, no matter how smart your search is. Awarding a bonus for the virginity of the piece on the gating square in evaluation would acihieve the same, and cost exactly nothing,

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #37 on: March 28, 2018, 06:16:09 am »
I meant in the opening, prior to the gating. Usually by the middlegame a few minors and pawns have been traded, so the branching factor is not that bad. The worst case is Dragon + Spider (I think) because the spider has like 20 legal moves and the Dragon is ridiculously strong. Those two on the board will grind the search to a near standstill beyond depth 11.
Well, that is purely an artifact of badly misevaluating the positions with gatable pieces. This forces the search to gate these pieces before the horizon or consider them lost, while in practice there would not be any reason to assume they could not be gated just as easily behind the horizon. So yes, with each two pieces in hand 4 plies will effectively get lost on gating moves, reducing the depth left to see the really important stuff by 4 ply, so that you need that extra depth to get the same tactical quality. Doing those extra 4 ply is very expensive, no matter how smart your search is. Awarding a bonus for the virginity of the piece on the gating square in evaluation would acihieve the same, and cost exactly nothing,

In practice, it is usually 6-ply needed to "clear the hurdle" since there is always the "toss a pawn, capture the pawn" 2-ply delaying phenomenon at work. So it's 4-ply to get the pieces in play, 2-ply to see that tossing a pawn "won't work," for 6-ply total.

But here is a position where the Compound Piece evaluation might not work:



You can see white is clearly winning with NxQ an obvious continuation. But here Planchet played Hc5! because the black Queen is really not safe no matter where it goes. The game continued:

1. Hc5 Qg4
2. f3 Qd7 (and here the Queen blocks the Bishop which prevents the Hawk from deploying)
3. Nxa8! (amazingly the Fortress + Bishop on f8 cannot be saved) e5
4. Hxf8 (destroys the Fortress as well) Kxf8

And white is winning everything in sight.

I don't think the Compound Evaluator would see the "value" in forcing a move such as ...Qd7 since the Hawk would still "be there" in the sum of material.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #38 on: March 28, 2018, 07:23:52 am »
It depends on which stage you already want to see that the gating opportunity will be destroyed. With the the compound-piece/virginity-bonus there are two enormously valuable (>Q) pieces on c8 and f8, which is a pretty good description of reality. In this particular case, there happens to be tactics that can gain one of these pieces (by forking them with the Hawk). That would not have been different if there had been real Queens or Amazons on those squares.

So yes, the search struggles here. But I would not say that is because of a failure of the compound-piece evaluation. It is just a manifestation of the more general (and well-kown) problem that a standard Quiescence Search is not able to recognize unsolvable threats like forks, skewers or trapped/suffocated pieces, and happily stands pat for the side subjected to those, assuming that having the move can solve any problem. Of course this gets more noticeable in Musketeer Chess, because the Hawk has such a tremendous forking and suffocation power, and there are so many more-valuable or unprotected targets for it on the back rank.

The logical solution here would be to have the static evaluation recognize threats against the side to move, and discount the evaluation a bit if there is one such threat, (because the move choice is restricted to those that solve the threat), and by the value of the second threat in case of multiple threats. (This still would require you to recognize a skewer as a multiple threat.) None of my attempts to try such things has met with much success, though. The problem is likely that modern searches, using null move, tend to leave many pieces hanging, just because it is too lazy to capture them if it is already ahead, or because it is so stupid to even try the most silly things when it is behind. So the typical leaf position contains multiple threats agains both sides. The outcome of that is very hard to predict, or even guess statically. You might have your Queen and Rook under attack by a Knight and a Bishop (suggesting that you must rescue the Queen and will lose the exchange), but if the opponent also has his Queen and Rook under attack they will both just capture Queens, then Rooks, and it equals out. In addition there is the fact that any complex analysis of leaf nodes takes time, which could also have been used to simply search one ply deeper, after which you would see the stuff the static analysis revealed anyway, even with a 'naive' evaluation.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #39 on: March 28, 2018, 12:18:30 pm »
It depends on which stage you already want to see that the gating opportunity will be destroyed. With the the compound-piece/virginity-bonus there are two enormously valuable (>Q) pieces on c8 and f8, which is a pretty good description of reality. In this particular case, there happens to be tactics that can gain one of these pieces (by forking them with the Hawk). That would not have been different if there had been real Queens or Amazons on those squares.

I don't think the piece values for the Hawk and Fortress are that high.
I use the following:

Code: [Select]
piece_value[PAWN] = 100;
piece_value[KNIGHT] = 300;
piece_value[BISHOP] = 325;
piece_value[ROOK] = 500;
piece_value[QUEEN] = 975;
piece_value[HAWK] = 575;
piece_value[UNICORN] = 550;
piece_value[LEOPARD] = 680;
piece_value[ELEPHANT] = 640;
piece_value[CANNON] = 760;
piece_value[FORTRESS] = 770;
piece_value[SPIDER] = 820;
piece_value[ARCHBISHOP] = 790;
piece_value[CHANCELLOR] = 840;
piece_value[DRAGON] = 1350;

So let's look at two different (short) lines of play, with a Compound Evaluator and my Piece Introduction Evaluator.

Line 1.
NxQe6 BxNe6 = H@c8

Compound Evaluator:
White gains Queen - Knight = 975 - 300 = 675.

Piece Introduction Evaluator
White gains Queen - Knight - introduced Hawk =  975 - 300 - 575 = 100.

Line 2.
Hc5 Qg4 f3 Qd7 Nxa8 e5 Hxf8 Kxf8

Compound Evaluator:
White gains Fortress + Bishop + Rook - Knight = 770 + 325 + 500 - 300 = 1295.

Piece Introduction Evaluator
White gains Fortress + Bishop + Rook - Knight = 770 + 325 + 500 - 300 = 1295.

The only difference we need to account for is that White started this whole line of play with a Knight sacrifice.

So both evaluators would have elected to play for line 2 here. I guess the question is, what is the "real" value of line 1? Is it a huge 675 point gain, or is it "not that big" since a Hawk is being thrown into the mix as a result of engaging in the exchange?



HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #40 on: March 28, 2018, 01:18:09 pm »
I would say the the gain of 625 is about right, because you gain a Queen for a Knight. That as a side effect black gates his Hawk should not discourage you, because it is reasonable to assume he would gate that Hawk anyway on some later move. So it should at most be accounted as a tempo gain for black, a small positional advantage.

That in this particular position the gating possibility can be destroyed, is a-typical. A program that speculates "he has not gated it on this move, so now he will never be able to gate it" for no particular reason (which is what ignoring the value of hand pieces amounts to) will be wrong in >99% of the nodes where it makes this speculation. If it would assume that the gating will simply occur later, it would have been right in 99% of the cases. But not here, as this position belongs to the other 1%.

Making wrong speculations in static evaluation is in general very detrimental, because search is very clever to find a path that has exactly the number of moves to make the position a leaf where the speculation is made. You would really want to reduce the fraction of wrong speculations as small as possible. Which is a real problem when you have to decide about something that goes one way in ~50% of the cases, and the other way in the other 50%. Just assuming the average of the possible outcomes often makes things even worse, as it is wrong in 100% of the cases.

The common case in Chess is that when you have a piece, you will be able to hang on to it, if you have the move. And that if you don't have the move, you will only lose it if the opponent can capture it immediately. This is why we do QS as we do it: stand pat or make a capture. You don't assume loss of material unless the search has proven loss of material. (And that should then also hold for the gating possibility associated with the presence of that material.) In the case of forks and skewers this assumption fails, but fortunately forks and skewers are pretty rare in the tree.

Another way to look at this is that you should place the 'burden of proof' on the unlikely result. This is why patterns for things like a Bishop trapped on a7 by a protected Pawn on b6 helps: such a Bishop will almost always be lost, even though you still have it, and is thus one of the cases where the default QS assumption fails. But fortunately one that can be easily recognized staticly. So you recognize that pattern, and invert the burden of proof, only counting the Bishop when the search can see a way to break the pattern without losing it. Another notorious case is the KQKP end-game with a 7th-rank Bishop Pawn where the defending King protects the promotion square. The default assumption with regard to promotion is that a Pawn is not counted as a Queen, not even on 7th rank. (Although you can perhaps count it as 2.5 Pawn.) So the side with the Queen would count itself way ahead as long as the Pawn is still a Pawn, and it can basically keep up that situation forever by keeping checking from all over the board, avoiding repetitions. So you would have to search extremely deep before the program would recognize it as a draw, much deeper than the program can search at the move where it commits to the situation. Inverting the burden of proof, assuming that 7th-rank Bishop Pawns (and Rook Pawns, for that matter) will promote in KQKP (and thus draw), unless the Queen is on the promotion square, already solves it. You don't even have to do complex static tests to see if the King protects the promotion square, because when he doesn't a quite shallow search will already be able to see that you can get your Queen on that square, to revert to normal scoring.
« Last Edit: March 28, 2018, 01:23:20 pm by HGMuller »

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #41 on: March 28, 2018, 06:17:07 pm »
That as a side effect black gates his Hawk should not discourage you, because it is reasonable to assume he would gate that Hawk anyway on some later move. So it should at most be accounted as a tempo gain for black, a small positional advantage.

That in this particular position the gating possibility can be destroyed, is a-typical. A program that speculates "he has not gated it on this move, so now he will never be able to gate it" for no particular reason (which is what ignoring the value of hand pieces amounts to) will be wrong in >99% of the nodes where it makes this speculation. If it would assume that the gating will simply occur later, it would have been right in 99% of the cases. But not here, as this position belongs to the other 1%.

I partially agree and I partially disagree. As you indicated, for the vast majority of the cases, the pieces will get into play, one way or another.

But is a piece off the board, unable to move, really worth the full value of its force if it were on the board? Perhaps the very definition of an overly-hypothetical example, akin to a pinned piece being temporarily worthless (yet its full value stays in tact).

What vexes me: Non-leapers behind the wall of pawns can get permanently stuck with as few as 2 pawn pushes in a locked pawn chain. They're done. The whole game will play out and they won't make a move. While not forced, just a few careless moves can create the situation.

Furthermore, it is possible to play the opening without pushing a single pawn and be way ahead, as in the example most recently shown here. The game is Planchet vs. Viswanathan Raman on Jocly.com and the program's 2 knights deployed, introduced their Musketeer counterparts, and the Queen was chased around before a single pawn push. The game was won before the first pawn move.

Using the Compound Piece Evaluator, the program would not think it was that far behind for most of these lines where Planchet saw it was ahead by an avalanche and a half.

And the program sacrificed a Knight to create the position shown here, which it would never have done unless certain the Musketeer pieces were trapped.

It is a difficult thing to try to program, and I think my Alpha-Beta-Gamma-Delta search has solved it nicely. It evaluates the position both ways: with and without compound pieces. Neither method can fully maximize without some "consent" of the other evaluator. It is the perfect blend, once all of the details are fully resolved. The program uses singular extensions to examine lines that are promising "entombers" of Musketeer pieces without bogging down the search. Likewise, captures that delete the compound piece are sought after specifically rather than just "chance encountered" through the normal searching process.

I'll see if I can post some examples. What is apparent: A new way to search was needed.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #42 on: March 29, 2018, 04:05:02 am »
Well, is a Rook on a1 behind a wall of Pawns really worth a Rook? Basically the only thing it does is protect one of the Pawns. The early middle-game is dominated by Knights and Bishops, which can easily jump over Pawns or sneak between them, and it takes a long time before Rooks become of any use. Yet, allowing the corner Rook to be traded for a minor early in the opening is a losing strategy. It is an empirical fact that the value of pieces is highly dominated by the value they will have in the end-game, perhaps for as much as 90%, and only for a small part by their current activity on the board. Of course the latter counts for something, and this is why engines use Piece-Square Tables and calculate mobility as evaluation terms. But the contribution of those (for a single piece) is typically in the sub-Pawn range, and over-weighting them makes the engine pursue a very aggressive, but in the end losing strategy.

So yes, still having an ungated piece is bad, because it has no mobility, and exerts no board control. But that is hardly different from keeping your Knights on b1/g1. It isn't really different from any other undeveloped piece. (Except perhaps that it also causes a vulnerability that the gating can be made impossible by capturing the piece on the gating square, so that the effect is somewhat larger.) Normally PST are used to take that into account, effectively making the value of pieces (slightly) dependent on their location on the board. This can also be done for the value of the ungated piece, making it (say) 30 centi-Pawn lower than what it would be on the back rank. (Which then again might be 30cP lower than what it would be in the center.) And adding that discounted value to the compound piece. If you really want to be subtle, you could dynamically calculate the 'vulnerability penalty' from how well the opponent is developed (or just increase it with move number), putting more urgency on the gating of the piece as the opponent deploys his pieces, and could possibly direct them at the virgin pieces on the gating squares. The fact that the ungated piece has no mobility should be accounted for automatically by the way you calculate mobility.

Permanent trapping of pieces is an area where engines are notoriously stupid. IIRC there was an Alpha Zero vs Stockfish game where Stockfish had trapped its own Bishop on the f1-g2-h3 behind blocked Pawns at e2-f3-g4. Hilarious to human players, but Stockfish of course insisting that Bishop was still worth a full Bishop (and embarrassingly losing the game). Other common cases with weak programs are a Rook on h1 with their King on f1/g1 (after a check destroyed their castling rights, and they decided to walk the King to safety behind the f2-g2-h2 Pawn shield on their own initiative. And in the end-game a white Rook on a1 with a black Pawn on a2 and a black Bishop on b1. The point is that such trapped pieces have no future at all, no matter how long the game continues and how much of the other pieces disappear. So they will never get to the point where their normal end-game value will be realized. For programs it is quite hard to recognize such situations, however. They of course apply the penalty for the piece being rather inactive at the moment, but that penalty is tuned (to a rather small value) on the assumption that sooner or later this situation will be corrected. Which is almost always true, but not quite. Likewise, it seems very hard to statically detect situations where you still have the virgin piece at the gating square, but you will never be able to gate.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #43 on: March 29, 2018, 06:23:10 pm »
Well, is a Rook on a1 behind a wall of Pawns really worth a Rook? Basically the only thing it does is protect one of the Pawns. The early middle-game is dominated by Knights and Bishops, which can easily jump over Pawns or sneak between them, and it takes a long time before Rooks become of any use.

Yes, and this is why I alluded to my remark as being about as hypothetical as one could get. I knew we each could cite examples and counterexamples, none of which help us code an appropriate solution. I did come across a rather nice coding trick today I should have tried first:



This is the dreaded "White Hawk Threatens Mate And Queen Capture Simultaneously" position that Planchet could not resolve with a search to depth 9 previously. Now it finds the correct move, ...d6! in about one second.

The idea I implemented: Adding Piece Deployment moves to the Quiescence() search! Simple. Quiescence() generates all captures until there are none, and then performs additional tests to see if piece drops are available. It does not consider the position ready for evaluation until all deployment moves have been made, or none can be made even if given the chance to move twice in a row (NULL move, kind of), or all deployable pieces have been captured.

Early on it really bloats the game tree but it finds the moves leading to the sharpest cutoffs, and compounded with the history heuristic, it flies through the move list on subsequent search depths.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #44 on: March 30, 2018, 03:19:20 am »
Well, as I mentioned at the bottom of my first posting on this page, it is essential for any search to work well that QS examines all moves that cause a large immediate score gain (to test if there is a backlash). If gating a piece 'gains' its value, that definitely would count as a large immediate score gain.

So searching the gating moves in QS should definitely ameliorate things. But it does not solve it entirely; in the same posting I also mention that you have to prevent the stand pat if there is such a threat against you (i.e. if the side not to move in QS can gate). Otherwise you get the same problems as are typical in searches that do not use a QS at all: the program tries to grab the most valuable target it can get at the last move before the horizon, even if it is protected, because it is blind to the recapture. So the engine would concentrate its efforts on manoeuvring to get a shot at Q x protected N. When the opponent still has, say, a Chancellor to gate, he now has the choice to gate it, (and lose the Knight), or to recapture the Queen. 'Losing' the Chancellor in addition to the Knight, because the other side will now stand pat (a comfortable Knight ahead) to make sure the Chancellor gating will remain beyond the horizon. In reality of course the Chancellor will almost always be gated on the next move, whatever he plays instead of the stand pat, leaving him down Q vs N.

Focussing on one particular position is very dangerous. In computer Chess it is almost always possible to find a search technique that speeds up finding the good move in that position, but turns out to weaken the engine in real games. This is even true for sets of test positions like the WAC test suite: people that tune their engine to perform best on WAC typically find this causes a hefty Elo reduction. To measure the merit of any search strategy you really should play games. Which, admittedly, is a bit hard for testing a method designed for handling the gating, as during most of the game you would have nothing to gate. To make sure the search strategy has an easily measurable effect on game results, you would have to go through an artificial situation, where gating is possible for most of the game. E.g. by giving the players a new piece to gate every 10 moves. Or better, every time the total material on the board has dropped by ~30 Pawn values (so that they then each get a piece worth ~7 Pawns back, and the total material still decreases over the game).