DIR Return Create A Forum - Home
---------------------------------------------------------
The Chess Variant Forum
HTML https://chessvariantforum.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Correspondence Game Requests
*****************************************************
#Post#: 344--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: GothicChessInventor Date: February 1, 2018, 2:29 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=53.msg318#msg318
date=1517420712]
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...
[/quote]
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]unsigned char capture_priority_index;[/code]
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]
#define TOTAL_PIECE_TYPES 6
#define PAWN 0
#define KNIGHT 1
#define BISHOP 2
#define ROOK
#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]);
}
}
}
[/code]
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.
#Post#: 346--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: Greg Strong Date: February 1, 2018, 10:10 pm
---------------------------------------------------------
[quote author=HGMuller link=topic=53.msg334#msg334
date=1517475213]
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).
[/quote]
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.
#Post#: 347--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: Greg Strong Date: February 1, 2018, 10:48 pm
---------------------------------------------------------
[quote author=GothicChessInventor link=topic=53.msg344#msg344
date=1517516983]
No, NEVER run the move generator twice!
[/quote]
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 ...
#Post#: 349--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: HGMuller Date: February 2, 2018, 1:59 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.
#Post#: 353--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: GothicChessInventor Date: February 2, 2018, 8:35 am
---------------------------------------------------------
[quote author=Greg Strong link=topic=53.msg347#msg347
date=1517546916]
Please note that my suggestion was intended purely in the
context of Fairy-Max, which specifically aims for simplicity
over strength...
[/quote]
Oh OK, then that make sense.
#Post#: 366--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: ebinola Date: February 2, 2018, 4:02 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.
#Post#: 368--------------------------------------------------
Re: Gothic Chess Correspondence Game
By: GothicChessInventor Date: February 2, 2018, 4:37 pm
---------------------------------------------------------
[quote author=ebinola link=topic=53.msg366#msg366
date=1517608945]
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.
[/quote]
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 :)
HTML https://www.youtube.com/watch?v=prVYwsBpHb8
*****************************************************
DIR Previous Page
DIR Next Page