Author Topic: Gothic Chess Correspondence Game  (Read 215 times)

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #15 on: January 31, 2018, 04:57:54 pm »
Note that Fairy-Max is what I consider a weak program. It is derived from micro-Max by just changing the possible board sizes and piece moves, and micro-Max was optimized for being small (maximum Elo per character) rather than for being strong. As a result virtually all Chess knowledge was culled out of it, and the search algorithms are also pretty basic.

I would like to add here that I believe MicroMax may hold the "world record" for fewest characters for a fully-functioning chess program forever. I have tried my own minimal character count just to try and get close to what H.G. achieved, and I couldn't get better than 2.2 times his code length. This is a remarkable achievement of H.G.'s and it should be recognized for what it is!

Furthermore, there seems to be a strategic aspect to 10x8 Chess that is not very important in orthodox Chess, and makes it relatively easy for Humas that know the trick to beat most programs. So using the same algoritm as an orthodox engine, just enlarging the board size, does not automatically preserve the strength.

This is 100% true and 200% true if you are talking about Gothic Chess. In part of my game design process, I wanted players to be "torn" between having to make one of two irreversible move choices that would influence the play into the "forever future."  Examples:

1. d4 d5 2. Nh3 g6

Now what for white? If 3. Nc3 then 3...Nc6 strikes twice at the d4 pawn, so do you play 3. c3 here? Let's see:

3. c3 Nh6 4. g3 Nc6 5. Bg2 looks fine.

Let's try Nc3 instead.

3. Nc3 Nc6 4. g3 and now white tasks black with the same dilema: what to do about the d-pawn under double attack?

4...Nxd4 5. e3! Nc6 and white has a few ways to recapture.

The idea being, players can choose a line of play with strategic aims right from the opening, and this influences the entire nature of the game. It is BEYOND the scope of what computers can determine, even if they could complete a 30-ply search, it would barely scratch the surface of white lies beneath.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #16 on: January 31, 2018, 05:01:24 pm »
1. d4 h6
2. h3

Sure this thread is fine. Thanks for accepting. Good luck.

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #17 on: January 31, 2018, 05:18:01 pm »
I would like to add here that I believe MicroMax may hold the "world record" for fewest characters for a fully-functioning chess program forever. I have tried my own minimal character count just to try and get close to what H.G. achieved, and I couldn't get better than 2.2 times his code length. This is a remarkable achievement of H.G.'s and it should be recognized for what it is!
Tough luck, but the micro-Max record is already beaten: Oscar Toledo G. wrote a Chess program that is only about 1280 characters, while the smallest micro-Max version was at about 1480, IIRC. I believe the program is called Toledo nano-Chess. It is much weaker than micro-Max, however. I never was aiming to be absolutely the smallest, because that will unavoidably lead to something that is also asymptotically weak, barely better than a random-move generator. And that is not very interesting. So I always optimized Elo/char, allowing me to add extra characters if they coded for a feature that would bring enough Elo. Nevertheless I did hold the record for being smallest for some time. And using some of Oscar's tricks could also shave many characters of micro-Max.

In Fairy-Max I no longer care much about Elo/char, and many characters were added just to expand the type of moves it can support, without this bringing any Elo in variants that do not involve such strange moves like hoppers or bent sliders. This added some 30% extra code lines in the AI. But the evaluation remained minimalistic, and it is a miracle it plays as well as it does. Having no knowledge is often better than having wrong knowledge, and I guess that is what saves the day. Many muh more complex programs are weaker because some of the knowledge they have is wrong.

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #18 on: January 31, 2018, 11:13:06 pm »
I guess the most limiting factor for it is poor move ordering (hash move, and then the rest of the move in move-genration order).

Ouch.  Yeah, that would hurt.  I bet just trying captures before non-captures would make a huge difference.  Even if it meant running the move generator twice, once for captures, and then again for non-captures (if there is no cut-off), I bet that would still be a win, and would keep your code fairly simple.  Or you could consider doing this only at likely cut-nodes...

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #19 on: February 01, 2018, 03:53:33 am »
Well, in a sense it does search captures before non-captures, because of the IID, which starts at QS depth, where all non-captures are skipped. So obvious material gains (i.e. visible in QS) will be preferred as cut-moves over non-captures. And before the QS iteration the IID even does an MVV/LVA iteration, to select the best capture to start the QS iteration with. For each iteration it runs the move generator again, as there is no storage of moves. It only remembers which move is best (so the next iteration can start with it).

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #20 on: February 01, 2018, 03:29:43 pm »
Even if it meant running the move generator twice, once for captures, and then again for non-captures (if there is no cut-off), I bet that would still be a win, and would keep your code fairly simple.  Or you could consider doing this only at likely cut-nodes...

No, NEVER run the move generator twice!

All you need to do, since you are generating every pseudo-legal move anyway before determining if there is a check, is store what piece captured which enemy piece and RANK the differences. Store that result, and sort by the best capture (like pawn x queen) to worst capture (queen x pawn). Best capture is smallest material taking most material and worst is the opposite.

Here is how I do it:

Code: [Select]
unsigned char capture_priority_index;
You need that field in your "position" structure. It's only one byte.

Understand that this is an index and not a score. Lower indices mean a better candidate capture was made. Higher indices mean a worse capture was made. Initialize it to 255. If it is 255, that means no capture occurred in the position just generated by the move generator.

So an index of 1 means your move generator played Pawn x Queen. You can't get much better than that. So now you need a 2-dimensional array to store which type of piece did what.

Next, you need this

Code: [Select]
#define TOTAL_PIECE_TYPES 6

#define PAWN 0
#define KNIGHT 1
#define BISHOP 2
#define ROOK 3
#define QUEEN 4
#define KING 5

unsigned char piece_trade_hierarchy[TOTAL_PIECE_TYPES][TOTAL_PIECE_TYPES];

void initialize_piece_values_and_capture_hierarchy(void)
{
unsigned short i, j, sorted_index, best_i, best_j;
signed short piece_trade_differences[TOTAL_PIECE_TYPES][TOTAL_PIECE_TYPES];
char piece_name[TOTAL_PIECE_TYPES][2];
unsigned short piece_value[TOTAL_PIECE_TYPES]
signed short best_so_far;

memset(piece_trade_differences, 0, sizeof(piece_trade_differences));
memset(piece_value, 0, sizeof(piece_value));
memset(piece_trade_hierarchy, 0, sizeof(piece_trade_hierarchy));

piece_value[PAWN] = 100;
piece_value[KNIGHT] = 300;
piece_value[BISHOP] = 300;
piece_value[ROOK] = 500;
piece_value[QUEEN] = 900;

strcpy(piece_name[PAWN], "P");
strcpy(piece_name[KNIGHT], "N");
strcpy(piece_name[BISHOP], "B");
strcpy(piece_name[ROOK], "R");
strcpy(piece_name[QUEEN], "Q");
strcpy(piece_name[KING], "K");

piece_value[KING] = 0;

for (i = PAWN; i <= KING; i++)
{
for (j = PAWN; j <= KING; j++)
{
piece_trade_hierarchy[i][j] = 0;

// difference in material if piece "i" captures piece "j"
if ((i == KING) || (j == KING))
piece_trade_differences[i][j] = -9999;
else
piece_trade_differences[i][j] = piece_value[j] - piece_value[i];
}
}

// we want to make a list such that the "best material gains" are tried first (lowest indices) by the move generator
// so sort the list from largest to smallest

sorted_index = 0;

while (1)
{
best_so_far = -10000;
best_i = 99;
best_j = 99;
sorted_index++;

for (i = PAWN; i <= KING; i++)
{
for (j = PAWN; j <= KING; j++)
{
if (piece_trade_differences[i][j] > best_so_far)
{
best_so_far = piece_trade_differences[i][j];
best_i = i;
best_j = j;
piece_trade_hierarchy[i][j] = sorted_index;
}
}
}

if (best_so_far == -10000) break;
else
{
// the trade that was the best will never be the best again
piece_trade_differences[best_i][best_j] = -10001;
printf("  %s captures %s is now ranked %03d\n", piece_name[best_i], piece_name[best_j], piece_trade_hierarchy[best_i][best_j]);
}
}
}

For Archbishop and Chancellor you use 5 and 6, make KING 7, and set TOTAL_PIECE_TYPES to 8.

Put whatever you what in for the piece values.

The idea being, when you are finished running initialize_piece_values_and_capture_hierarchy() at startup, you have a global, 2-dimensional array named piece_trade_hierarchy[][] where you pass into it the type of piece capturing in the first dimension, and the type of piece captured in the second dimension, and out comes a "priority index" where lower values are best. I make sure I don't return a 0 so that if I see it return 0 I know something went wrong.

piece_trade_hierarchy[PAWN][QUEEN] should return 1.

How to use it:

As you generate your legal moves, stuff the piece capturing and piece captured into piece_trade_hierarchy[][] and what comes out should go into the capture_priority_index field of your position record. When you are done generating all moves, sort the moves from smallest to largest by the capture_priority_index field and pass them in that order. You should almost ALWAYS get a cutoff on your first move!

This requires only 1 call to your move generator, 1 additional byte per position, and produces cutoffs like 99.999% of the time.
« Last Edit: February 01, 2018, 03:40:02 pm by GothicChessInventor »

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #21 on: February 01, 2018, 11:10:16 pm »
Well, in a sense it does search captures before non-captures, because of the IID, which starts at QS depth, where all non-captures are skipped. So obvious material gains (i.e. visible in QS) will be preferred as cut-moves over non-captures. And before the QS iteration the IID even does an MVV/LVA iteration, to select the best capture to start the QS iteration with. For each iteration it runs the move generator again, as there is no storage of moves. It only remembers which move is best (so the next iteration can start with it).

Interesting.  So do you do IID at every node?  Usually there are some restrictions, like not in check, eval within a margin of beta, etc.

Greg Strong

  • Newbie
  • *
  • Posts: 21
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #22 on: February 01, 2018, 11:48:36 pm »
No, NEVER run the move generator twice!

Please note that my suggestion was intended purely in the context of Fairy-Max, which specifically aims for simplicity over strength, and has basically no move ordering at all (beyond TT move.)  I was suggesting that a simple thing like doing captures before non-captures should be a huge improvement.  Running the generator twice was just a suggestion of how that might be accomplished without adding more than a couple lies of code.  But of course running the generator twice is not ideal.  Based on H.G.'s follow-up, though, it seems he's about to accomplish a similar effect with very aggressive use of IID.  Although each IID iteration is another call to the move generator, so it seems he is, in fact, running the move generator repeatedly on the same positions to get better ordering...

While my code is different than yours, what I accomplish is similar.  I run the move generator once and give a score every move (capture or otherwise.) Whenever it's time to play a move, a scan the for the one with the highest eval, move it to the end of the array and decrement the array length so I won't try it again, and then play it.  In a cut-node, hopefully I get a cut-off after the first move.

I assign the scores such that it goes: PV/TT move, winning or equal captures, killer moves, bad captures, other moves.  Captures are scored in MVV/LVA order (I'll always grab the most valuable victim first, starting with the least valuable attacker.)  If the attacker is more valuable than the victim, I use SEE to determine if it's a "bad" capture.  Other moves are scored based on history and PST.  And, actually, I was just looking at the code while writing this to refresh my memory and found a bug!  I wasn't disabling SEE in games that can't handle it.  (My static exchange evaluator isn't going to do the right thing in games with chinese chess cannons, for example.)  Gotta fix that ...

HGMuller

  • Global Moderator
  • Full Member
  • *****
  • Posts: 121
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #23 on: February 02, 2018, 02:59:58 am »
The point is that the micro-Max/Fairy-Max move generator is completely trivial, just 3 nested loops, over pieces, over directions and over range. Most moves in Chess are slider moves, and generated by just doing one more iteration of the inner (range) loop. That is not more than adding the step vector to the to-square of the previous move, checking if you are still on board, and checking the board in that location to see if there isn't anything there that blocks you. That isn't really any slower than incrementing a move index, checking if you reached the end of a list of pre-stored moves, fetching the move from the list and decoding it. So there isn't any speed penalty. The down-side is just that you cannot arbitrarily re-order the moves, like you could when they were kept in a list.

IID is indeed done in every node. And it is done even in steps of 1 ply, while most engines increase the depth in larger steps. But in the overwhelming majority of nodes it is only a formal thing, because the required depth is only one higher than the result stored in the hash table (left there from the previous root iteration). So it just has to add a single 'iteration' to that, at the requested depth, so that the IID loop isn't really looped over at all. The hash hit replaces the first N-1 iterations.

So the only real penalty is that in QS (where no hash hit is usually available, as it breaks new ground at the tips of the tree) Fairy-Max does 2 iterations, one MVV/LVA iteration, where the score is set to pieceValue minus pieceType (and one hopes that the piece types are numbered in order of increasing value), and then a 1-ply search skipping all non-captures. This has quite a lot of overhead, because only few of the moves are captures, and you run through all moves twice to fish them out, while you could have remembered them after the first time. Finding the MVV-wise best capture to start with it is necessary in an all-captures QS to prevent search explosion by plunder raids, however. (And it is a general problem in mail-box engines that there is no trivial way to generate only captures.) Early versions of micro-Max had no real QS, but just extended recapture (to the same square). But a full capture search, although more complex, did add enough Elo to justify the extra code needed for it.

In simple engines where code size is not an issue, I typically use a 'two-sided' move list, where I add generated non-captures to the end, and generated captures at the beginning, as a pre-sort. So that the sorting of captures only has to look at the beginning of the list. In engines that I want to be really fast I do selective generation of captures, and even of captures to a given square, so that the captures are already generated in MVV order, and each new batch of moves only has to be sorted by LVA.
« Last Edit: February 02, 2018, 03:03:14 am by HGMuller »

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #24 on: February 02, 2018, 09:35:42 am »
Please note that my suggestion was intended purely in the context of Fairy-Max, which specifically aims for simplicity over strength...

Oh OK, then that make sense.

ebinola

  • Jr. Member
  • **
  • Posts: 77
  • Location: nowhere in particular
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #25 on: February 02, 2018, 05:02:25 pm »
2. g6

To be honest, I'm not all that familiar with 10x8 boards, so it'd be interesting to hear your feedback after the game.
Chess player, amateur writer and on the side shitposter extraordinaire.

GothicChessInventor

  • Full Member
  • ***
  • Posts: 176
    • View Profile
Re: Gothic Chess Correspondence Game
« Reply #26 on: February 02, 2018, 05:37:19 pm »
2. g6

To be honest, I'm not all that familiar with 10x8 boards, so it'd be interesting to hear your feedback after the game.

1. d4 h6
2. h3 g6
3. Cf3

Well the good news is you made the same first two moves Grandmaster Susan Polgar made against me in 2006.
The bad news is I had over 10 years to analyze the play :)

https://www.youtube.com/watch?v=prVYwsBpHb8
« Last Edit: February 02, 2018, 05:41:56 pm by GothicChessInventor »