DIR Return Create A Forum - Home
---------------------------------------------------------
The Chess Variant Forum
HTML https://chessvariantforum.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: General Discussion
*****************************************************
#Post#: 657--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 27, 2018, 2:50 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.
#Post#: 660--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 27, 2018, 8:20 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.
#Post#: 663--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 27, 2018, 9:23 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.
#Post#: 664--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 27, 2018, 3:09 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg663#msg663
date=1522160580]
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.
[/quote]
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.
[quote author=HGMuller link=topic=56.msg663#msg663
date=1522160580]
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.
[/quote]
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.
[quote author=HGMuller link=topic=56.msg663#msg663
date=1522160580]
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.
[/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.
#Post#: 666--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 27, 2018, 5:08 pm
---------------------------------------------------------
[quote author=GothicChessInventor link=topic=56.msg664#msg664
date=1522181361]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.[/quote]
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.
[/quote]
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.
#Post#: 668--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 27, 2018, 8:16 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg666#msg666
date=1522188510]
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]
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.
[quote author=HGMuller link=topic=56.msg666#msg666
date=1522188510]
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.
[/quote]
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?
[/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.
#Post#: 669--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 28, 2018, 1:34 am
---------------------------------------------------------
[quote author=GothicChessInventor link=topic=56.msg668#msg668
date=1522199813]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.[/quote]
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.[/quote]
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.
[/quote]
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,
#Post#: 671--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 28, 2018, 5:16 am
---------------------------------------------------------
[quote author=GothicChessInventor link=topic=56.msg668#msg668
date=1522199813]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.
[/quote]
[quote author=HGMuller link=topic=56.msg669#msg669
date=1522218873]
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,
[/quote]
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:
HTML https://image.ibb.co/he5kX7/Nx_Q_or_Hawk_c5.jpg
HTML https://ibb.co/dJTiKn
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.
#Post#: 672--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 28, 2018, 6:23 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.
#Post#: 673--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 28, 2018, 11:18 am
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg672#msg672
date=1522236232]
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.
[/quote]
I don't think the piece values for the Hawk and Fortress are
that high.
I use the following:
[code]
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;
[/code]
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?
*****************************************************
DIR Previous Page
DIR Next Page