Author Topic: Games against Programs  (Read 318 times)

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #15 on: February 04, 2018, 10:05:03 am »
It doesn't, because it isn't. You can interpose the Queen instead of the Bishop.

But this isn't something that needs to be 'tried'. It is how all my engines work, since ~1980. It is a 'proven technology', which I conceived when I had improved he first Chess engine I ever wrote to the point where it could see mate in 2, with as a result that it couldn't win KQK anymore. Because it consistently preferred the mate in 2 over mate in 1.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #16 on: February 04, 2018, 01:48:09 pm »
It doesn't, because it isn't. You can interpose the Queen instead of the Bishop.

But this isn't something that needs to be 'tried'. It is how all my engines work, since ~1980. It is a 'proven technology', which I conceived when I had improved he first Chess engine I ever wrote to the point where it could see mate in 2, with as a result that it couldn't win KQK anymore. Because it consistently preferred the mate in 2 over mate in 1.

I know it is not a mate in 2, which is why I asked.

When I leave in my "mate - distance" code, it plays the queen intervention.
When I implement your suggestion with the alpha-beta modification, it thinks there is a mate in 2.

So I must not be implementing your coding idea properly.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #17 on: February 04, 2018, 04:21:04 pm »
This is typically what happens if the correction of bestScore after the search completed can shift a score that is a bound back into the original window. The code I posted should not suffer from that, however. (If inserted in the right place.) What also can go wrong is that your Search() routine can return from multiple places, (for exceptional conditions), where some bypass the incrementing of bestScore.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #18 on: February 04, 2018, 11:09:49 pm »
This is typically what happens if the correction of bestScore after the search completed can shift a score that is a bound back into the original window. The code I posted should not suffer from that, however. (If inserted in the right place.) What also can go wrong is that your Search() routine can return from multiple places, (for exceptional conditions), where some bypass the incrementing of bestScore.

Yes I will have to look at your code more closely. It was hard to pay attention while GETTING READY FOR THE EAGLES TO WIN THE SUPERBOWL!!!!

Yessssssssssssssssssssssssssssssss!!!!!!!!!!!!!!!!!


GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #19 on: February 06, 2018, 12:58:28 pm »
This is typically what happens if the correction of bestScore after the search completed can shift a score that is a bound back into the original window. The code I posted should not suffer from that, however. (If inserted in the right place.) What also can go wrong is that your Search() routine can return from multiple places, (for exceptional conditions), where some bypass the incrementing of bestScore.

Now I see why it will not work with my code.

I probe the TABLEBASES in RAM, so I need to return "mate - tablebase distance - depth from root including quiescence - 1" whenever I encounter a tablebase win. So if I hit a 5-piece tablebase result and it is white to move and win in 535-ply from the ending of Queen + Pawn vs. Queen, and it was found at nominal depth 11 that hit depth 37 during the search, the winning distance overall is 535 + 37 - 1 = 571-ply. So I return the score of 20000 - 571 = 19,429 for that position.

The reason why I subtract 1 is this: Suppose at depth 1 it is white to move and the tablebase says it is the win in 535-ply. Well depth = 1, so 535 + 1 would not be correct, since that is a "loss in 536 ply." So the true depth is always tablebase depth + search depth - 1.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #20 on: February 06, 2018, 01:47:18 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.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #21 on: February 06, 2018, 04:43:54 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.

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?

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #22 on: February 07, 2018, 03:43:26 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.)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #23 on: February 07, 2018, 10:16:21 am »
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.

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!

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #24 on: February 19, 2018, 01:27:41 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);

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.

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: [Select]
#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);
}

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: [Select]
if (depth <= 0)
{
best_score = quiesce(alpha, beta);
best_score += ((best_score < static_evaluation_of_position) && (adjusting_score == 1));
return best_score;
}

It will only adjust the score if it is less than the static evaluation and not a mating position. Otherwise:

Code: [Select]
if (!at_least_one_legal_move)
{
if (king_in_check)
{
best_score = (true_depth - INF);
return best_score;
}
else return 0;
}

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: [Select]
if (current_position_score >= beta)
{
best_score = beta;
best_score += ((best_score < static_evaluation_of_position) && (adjusting_score == 1));
return best_score;
}

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.
« Last Edit: February 19, 2018, 09:29:50 am by GothicChessInventor »

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Planchet a Musketeer Chess Program
« Reply #25 on: March 25, 2018, 11:14:35 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:



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:



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)



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!




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!




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.
« Last Edit: March 25, 2018, 11:41:39 am by GothicChessInventor »

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #26 on: March 25, 2018, 02:59:21 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.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #27 on: March 26, 2018, 10:30:30 am »
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.

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.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 122
    • View Profile
Re: Games against Programs
« Reply #28 on: March 26, 2018, 11:28:00 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.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Games against Programs
« Reply #29 on: March 26, 2018, 09:05:13 pm »

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.

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?