DIR Return Create A Forum - Home
---------------------------------------------------------
The Chess Variant Forum
HTML https://chessvariantforum.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: General Discussion
*****************************************************
#Post#: 408--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: February 6, 2018, 12:47 pm
---------------------------------------------------------
End-game tables are a special case of transposition tables. With
the delayed-loss bonus probing them should not be dependent on
the location in the tree where they are probed. If the EGT says
mate in 535, the score of that position should simply be mate in
535 (e.g. INF - 535). If the probe happens 20 moves from the
root, repeated application of the delayed-loss bonus during
propagation towards the root will cause the score to arrive
there as mate in 555.
#Post#: 409--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: February 6, 2018, 3:43 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg408#msg408
date=1517942838]
End-game tables are a special case of transposition tables. With
the delayed-loss bonus probing them should not be dependent on
the location in the tree where they are probed. If the EGT says
mate in 535, the score of that position should simply be mate in
535 (e.g. INF - 535). If the probe happens 20 moves from the
root, repeated application of the delayed-loss bonus during
propagation towards the root will cause the score to arrive
there as mate in 555.
[/quote]
OK, that is helping me understand it a little better. My
questions this time:
1. You mentioned "repeated application of the delayed-loss
bonus." In my currently implementation, this TB position would
be hit once at "depth 37" and scored INF - "TB WIN distance" - 1
and never need to be hit subsequently. The score returned is
correct for that depth at that leaf node. If this sets a bound,
then the program will try and find faster tablebase wins or the
same one at a shallower depth. In each instance, it is one, and
only one, unique value returned. Your scoring method will always
"undercut" the lowest bound by 1, even if it is a "mate in 535,"
correct?
2. If my program finds a mate in 19-ply at nominal depth 11
during the quiescence probe (not assisted by tablebases), will
it still report the same "undercut" score as a long TB win in
535? That is, whatever the bound is at that level - 1?
3. If yes, to the one above, how does the program distinguish
which is actually better?
#Post#: 420--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: February 7, 2018, 2:43 am
---------------------------------------------------------
Each time the score (bound) is returned from a node where the
losing side is on move (so the score is 'mated-in-N'), the score
will be ameliorated by one quantum by application of the
delayed-loss bonus. That means it will be turned into a
'mated-in-(N+1)' score before it is returned, where the parent
node than turns it into a 'mate-in-(N+1)' score because of
negamax. Which will then be returned unmodified (and show up in
the grandparent as 'mated-in-(N+1)' in the grandparent, as this
score is above the current evaluation, and will thus not be
awarded a delayed-loss bonus.
If the EGT mate-in-N score will be found at ply level 37 in the
tree, it will be returned 18 times as a 'mated-in' score, and in
each of these occasions a delayed-loss bonus will be received.
So in the root a mate-in-(N+18) score will be seen.
I am not sure what you mean by 'nominal depth' in (2). Is that
the number of the iteration in the root? This doesn't directly
enter the equation. If it finds a mating move in a node 18 ply
away from the root, it would score it as a mate-in-1 in that
node, mated-in-1 in its parent, mate-in-2 in its grandparent,
etc, until it is scored a mate-in-10 in the root (if it is not
trumped by any score from a side-branch on the way, i.e. if it
is the PV). Even the mate-in-10 would always be better than a
mate-in-535 from an EGT probe that is further increased on its
way to the root by delayed-loss bonuses to even longer mates, so
the winning side would never prefer this. (But the losing side
would of course prefer any mated-in-(535+x) over mated-in-10,
and go for the EGT loss.)
#Post#: 421--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: February 7, 2018, 9:16 am
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg420#msg420
date=1517993006]I am not sure what you mean by 'nominal depth'
in (2). Is that the number of the iteration in the root? This
doesn't directly enter the equation.
[/quote]
I refer to the "nominal depth" as the depth that the counter
assigns to be searched before quiescence. So your code looks
like this:
counter = 0;
while(1)
{
score = search(alpha, beta, counter, position);
counter++;
if(time_expired()) break;
}
Then "counter" is the nominal depth.
But, of course, quiescence can extend this to a factor of 2 or 3
or more in turbulent positions.
I check the piece count within quiescence. If it is <= 5, I
check the tablebase, return the score, and exit quiescence. If >
5, I check to see if there are more pending captures, and repeat
until there are none. I only score a position when there are no
pending captures no matter whose turn it is to move. So if it is
white to move but black has a capture, the position is not yet
quiescent.
But I don't know if using your recommended bounds adjustment for
loss postponement will functionally change what is happening in
my search. I would need to see where in the search you set the
values, making allowances for "what if a TB result was returned"
during the search.
If it finds faster paths to mate, and saves search overhead like
you suggested, I will surely implement it!
#Post#: 492--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: February 19, 2018, 12:27 am
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg358#msg358
date=1517588863]
It isn't really complicated; the only code it requires is three
simple assignment statements. At the start of the node
[font=courier]alpha -= (alpha < currentEval);
beta -= (beta <= currentEval);[/font]
and at the end
[font=courier]bestScore += (bestScore < currentEval);[/font]
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.
[/quote]
After a considerable amount of testing, I found an
implementation that takes the best from both worlds. First, a
few discoveries using your code:
1. If the evaluation function returns a score of 0, you can
still use the Delayed Loss Bonus (DLB) code for instances where
one side would prefer to enter into the quickest such position.
2. If encountering a stalemate, 50-move rule draw, or repetition
draw, the DLB bonus bloats the search tree. The reason: All of
those nice, neat "0" scores are now +1, +2, +3 from the DLB
scaling. More unique scores = more nodes = fewer cutoffs etc.
3. Applying the DLB to mate positions can have the unusual
effect of showing the mating distance "off by 1" depending on
whether or not alpha or beta ran into it first, and whether or
not one side is being mated or is delivering the mate.
So my cure for this behavior is to use DLB scoring for all
positions such that alpha and beta are sufficiently distant from
a mate score.
Example:
[code]
#define INF (30000)
#define WINDOW_OVERRIDE (INF - 1000)
adjusting_score = 0;
static_evaluation_of_position = evaluation_routine_score();
// pre-adjust window for bonus that will be added afterwards
if ((abs(alpha) < WINDOW_OVERRIDE) && (abs(beta) <
WINDOW_OVERRIDE))
{
adjusting_score = 1;
alpha -= (alpha < static_evaluation_of_position);
beta -= (beta <= static_evaluation_of_position);
}
[/code]
The checkmate score is 30,000.
The "window override" is 29,000.
So if the absolute value of the score < 29,000 I apply the
Delayed Loss Bonus.
I use my lame "adjusting_score" variable to track when this is
the case.
So if your depth variable counts down to 0 like mine does:
[code]
if (depth <= 0)
{
best_score = quiesce(alpha, beta);
best_score += ((best_score < static_evaluation_of_position) &&
(adjusting_score == 1));
return best_score;
}
[/code]
It will only adjust the score if it is less than the static
evaluation and not a mating position. Otherwise:
[code]
if (!at_least_one_legal_move)
{
if (king_in_check)
{
best_score = (true_depth - INF);
return best_score;
}
else return 0;
}
[/code]
If there are no legal moves and your king is in check, return
the mating distance from the depth - infinity. Otherwise let the
stalemate score get returned as an unaltered zero.
And adjust alpha and beta according to these rules also:
[code]
if (current_position_score >= beta)
{
best_score = beta;
best_score += ((best_score < static_evaluation_of_position)
&& (adjusting_score == 1));
return best_score;
}
[/code]
This will always lead to fewer nodes needing to be examined to
reach a fixed depth, and the mate announcement will always be
correct as well.
#Post#: 638--------------------------------------------------
Planchet a Musketeer Chess Program
By: GothicChessInventor Date: March 25, 2018, 10:14 am
---------------------------------------------------------
Here is a the start of a Musketeer Chess game being played on
Jocly between Planchet and its opponent. It is Black to move:
HTML https://image.ibb.co/nCWj5S/Hawk_Trap_Black_To_move.jpg
HTML https://ibb.co/jVTWkS
Already at this early stage of the game there is a forced move
for Black.
1. Nf3 = H@g1 Nf6 = U@g8
2. Hg3
The two-fold threats by the Hawk at g3 are He5 checkmate and Hg5
threatening to capture the Queen on d8, which is blocked in.
The move 2...d6 is positively forced already.
The Planchet program must search to at least depth 11 to find
the correct play:
HTML https://preview.ibb.co/gvoHs7/depth_11_hawk_trap.jpg
HTML https://ibb.co/iyGgKn
You can see from the analysis that 2...d6 stops the checkmate
threat, but cannot stop 3. Hg5. But with the d-pawn pushed, the
Queen will be able to play ...Qd7 and avoid the Hxd8 capture.
However, the program does not "run away" after 3. Hg5 and
instead it finds 3...Uh5 to strike back with its own
mate-in-1-threat with the Unicorn. This, in turn, forces 4. d3
at which time 4...Qd7 etc.
However, I had my program set to search only 9-ply, so it could
not see all of that! Instead, the game progressed:
1. Nf3 = H@g1 Nf6 = U@g8
2. Hg3 Nc6? = H@b8
3. Hg5! Hb6!
This leads to the following interesting position (though Black
will eventually lose the Queen for a Hawk)
HTML https://image.ibb.co/ixTaC7/Hawk_Trap_Misplay_WTM_after_Hb6.jpg
HTML https://ibb.co/k9dxQS
If white takes the Queen with the Hawk, Black now has Hb4
checkmate. Easily dodged however. But the cascade of mate-in-1
threats are not yet finished:
1. Nf3 = H@g1 Nf6 = U@g8
2. Hg3 Nc6? = H@b8
3. Hg5! Hb6!
4. c3 He6!
HTML https://image.ibb.co/d0x7QS/Hawk_Trap_Misplay_WTM_after_He6.jpg
HTML https://ibb.co/iXjXs7
The Black hawk in the e-file is now threatening mate in 1.
1. Nf3 = H@g1 Nf6 = U@g8
2. Hg3 Nc6? = H@b8
3. Hg5! Hb6!
4. c3 He6!
5. d3 Hg4!
HTML https://image.ibb.co/gCLizn/Hawk_Trap_Misplay_WTM_after_Hg4.jpg
HTML https://ibb.co/jew1kS
And the last act of defiance, the program could only see this
far ahead from the opening, and the Hawk on g4 now threatens the
Queen on d1. The program "thought" with both queens under
attack, that 2...Nc6 was a safe move. It needed two more plies
of search to see the white Queen can move, and the black Queen
is still surrounded by its own forces.
An entertaining start to the game, although it is unlikely
Planchet will survive in the long run.
#Post#: 641--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 25, 2018, 1:59 pm
---------------------------------------------------------
There must be more to this, because from the position where
Planchet plays Nc6 the final position you show is only 7 ply
away. So if it really searches 9 ply, it should still see the
white Queen move to safety, and then, after any black move, HxQ
in Quiescence Search. Probably the branch is initially not PV,
and some of the non-captures get reduced.
This game demonstrates very well how pieces with range-3 leaps
are problematic, and lead to non-quiet initial positions. At
least for 'classical' initial positions with the Pawns on 2nd
rank, and all pieces trapped behind that. This is why such
distant leapers are not very popular in chess variants.
A program that has to deal with such pieces would probably
benefit a lot from recognizing 'suffocated threats' in its
evaluation. As long as an immovable Queen is attacked by a Hawk
(or Knight, but that is in general too difficult, and thus not
much of a problem), it really should be valued only as a Hawk.
This is a bit similar to the cases in orthodox Chess where a
white Bishop gets trapped on a7, by black Pawns on b6, c7. Or a
white Knight on a8, trapped by a black Pawn on a7. Strong
programs in general recognize such patterns, to discount the
doomed pieces, as when they don't, they will very frequently
lose by capturing Bxa7 or Nxa8 (and thus not be very strong).
Range-3 attacks on suffocated pieces would be another necessary
pattern, in games where such pieces occur.
#Post#: 650--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 26, 2018, 9:30 am
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg641#msg641
date=1522004361]
There must be more to this, because from the position where
Planchet plays Nc6 the final position you show is only 7 ply
away. So if it really searches 9 ply, it should still see the
white Queen move to safety, and then, after any black move, HxQ
in Quiescence Search. Probably the branch is initially not PV,
and some of the non-captures get reduced.
This game demonstrates very well how pieces with range-3 leaps
are problematic, and lead to non-quiet initial positions. At
least for 'classical' initial positions with the Pawns on 2nd
rank, and all pieces trapped behind that. This is why such
distant leapers are not very popular in chess variants.
A program that has to deal with such pieces would probably
benefit a lot from recognizing 'suffocated threats' in its
evaluation. As long as an immovable Queen is attacked by a Hawk
(or Knight, but that is in general too difficult, and thus not
much of a problem), it really should be valued only as a Hawk.
This is a bit similar to the cases in orthodox Chess where a
white Bishop gets trapped on a7, by black Pawns on b6, c7. Or a
white Knight on a8, trapped by a black Pawn on a7. Strong
programs in general recognize such patterns, to discount the
doomed pieces, as when they don't, they will very frequently
lose by capturing Bxa7 or Nxa8 (and thus not be very strong).
Range-3 attacks on suffocated pieces would be another necessary
pattern, in games where such pieces occur.
[/quote]
Part of the problem is that Planchet has both of its Musketeer
pieces deployed, while white is "down" a Unicorn until it gets
into play. So the program's alpha-beta routine "windows-out"
sequences where white has not equalized in material yet,
preferring to get the Unicorn into play. It sees no danger in
HxQ HxQ while ahead a Unicorn, and this line never makes it to
the pv at depth 9. It is not considered until the window fails
and a research is triggered at depth 11.
One way I am "curing" this is by selective application of the
null move to help reorder the move list so that the threat of an
early Hg3 might be realized sooner. But this is dangerous if
implemented incorrectly, so I am proceeding with caution.
#Post#: 652--------------------------------------------------
Re: Games against Programs
By: HGMuller Date: March 26, 2018, 10:28 am
---------------------------------------------------------
Evaluating pieces in hand as zero seems a mistake. The default
assumption (and in fact overwhelmingly likely) is that they will
be gated onto the board at some point, even if that is not
within the horizon. Unless the gating possibility has definitely
be destroyed.
In Seirawan Chess this is more subtle than in Musketeer Chess,
because you (initially) have a choice there where you will gate
the piece. So the general rule for the opening holds there that
it is better to postpone the decision where to develop the
piece, so the opponent cannot concentrate its efforts against
the choice you are going to make from an early stage on. (The
rule "develop Knights before Bishops" is based on this
principle.) Once only a single possibility is left, (as there is
in Musketeer Chess from the beginning), postponing the gating is
just bad, because the opponent knows where it is going to be
anyway, and in the mean time you run the risk he destroys the
possibility. But as long as there are more gating possibilities
than pieces in hand, this should give you a bonus for each extra
possibility. Of course a piece in hand is an undeveloped piece,
which should incur a penalty similar to what you typically gain
on developing back-rank pieces, so that the desire to keep the
options open will only will only cause the hand pieces to be
developed last, and not hold up their development indefinitely.
In Musketeer Chess I would think the 'piece-square' value for
pieces 'in hand' should be just a small positional penalty
smaller than the value of the piece on the back-rank square it
will be gated on. Otherwise the engine would just panic for no
reason if it cannot gate the pieces within the horizon, with
severe horizon effect as a result. And the compulsive need to
gate them would effectively eat away part of the search depth.
#Post#: 654--------------------------------------------------
Re: Games against Programs
By: GothicChessInventor Date: March 26, 2018, 8:05 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=56.msg652#msg652
date=1522078080]
In Musketeer Chess I would think the 'piece-square' value for
pieces 'in hand' should be just a small positional penalty
smaller than the value of the piece on the back-rank square it
will be gated on. Otherwise the engine would just panic for no
reason if it cannot gate the pieces within the horizon, with
severe horizon effect as a result. And the compulsive need to
gate them would effectively eat away part of the search depth.
[/quote]
The most extreme case I have found is what I call the Horizon
Postponement: The program will actually throw away a pawn, such
as e6? fxe6 for no reason other than to disallow a simple Nf6
which would allow the piece drop of a Musketeer piece, viewed as
a large gain. So sometimes throwing away 2 pawns stops an
8-point piece from coming on board, when really the piece can
deploy 1 move beyond the search horizon. It's a real problem.
It's too hard to implement the other idea: The Compound Piece.
Give the piece that introduces a Musketeer piece the sum of its
material value, and only subtract it if it is captured as an
undeveloped piece. The problem is, once it moves, the piece
values bifurcate: the developing piece loses material, the
introduced piece gains material, and the net sum is 0. I tried
it this way and the search becomes even more unstable with wild
Unicorn moves trying to hunt down a Dragon backed by a King: the
pv you see is absurd, yet logical, using the compound piece
construct.
The only true cure is more depth, so I'm just working to make
the program search deeper, faster. Sound familiar?
*****************************************************
DIR Previous Page
DIR Next Page