I'm happy to know that our numbers are the same. Henk is not generating check-evasions and that causes the difference.
QSearch perft
Moderators: hgm, Rebel, chrisw
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: QSearch perft
Ok so definitions of QPerft are different. Mine doing no check evasions.Joost Buijs wrote: ↑Fri May 24, 2019 3:20 pm You really have to generate check-evasions when the king is in check (blocking moves and king moves to get out of check) if you want to be correct.
Unfortunately I have to modify my code if I want to do it your way (to check if the king is captured), so it is not straightforward to compare our numbers.
Current QPerft:
Code: Select all
static public ulong Perft3(IChessPosition position, int depth, bool epMoves = true)
{
var moves = LegalMoveGenerator.ListLegalCaptures(position, epMoves);
if (depth == 1) return (ulong)moves.Count;
ulong count = 0;
var board = position.Board;
var other = board.Other;
foreach (MoveBase mv in moves)
{
var field = mv.GetCaptureLocation(position);
var capture = board.PieceSort(field);
mv.Apply(position);
count += Perft3(position, depth - 1, true);
mv.TakeBack(position, capture, field, other);
}
return count;
}
Compare with 'normal' perft (Not a QPerft! verified with standard results)
Code: Select all
public ulong Perft(int depth, bool epMoves = true)
{
var moves = ListLegalMoves(this, epMoves);
if (depth == 1) return (ulong)moves.Count;
ulong count = 0;
var other = Board.Other;
foreach (MoveBase mv in moves)
{
var field = mv.GetCaptureLocation(this);
var capture = Board.PieceSort(field);
mv.Apply(this);
count += Perft(depth - 1, Board.PieceKind(mv.End) == Pawn_Kind);
mv.TakeBack(this, capture, field, other);
}
return count;
}
Last edited by Henk on Fri May 24, 2019 3:43 pm, edited 1 time in total.
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: QSearch perft
By the way is doing check evasions in QSearch an elo gain?Joost Buijs wrote: ↑Fri May 24, 2019 3:33 pmI'm happy to know that our numbers are the same. Henk is not generating check-evasions and that causes the difference.
Maybe I should implement them too if I have time.
At this moment I don't call QSearch in normal search when in Check.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: QSearch perft
I assume it will gain something. Check evasions are usually just a few moves, and in your case you have to try all possible moves and check whether the king gets captured at the next ply, or something like this.Henk wrote: ↑Fri May 24, 2019 3:40 pmBy the way is doing check evasions in QSearch an elo gain?Joost Buijs wrote: ↑Fri May 24, 2019 3:33 pmI'm happy to know that our numbers are the same. Henk is not generating check-evasions and that causes the difference.
Maybe I should implement them too if I have time.
At this moment I don't call QSearch in normal search when in Check.
When there is only 1 checking piece, I try to capture that piece, if that doesn't work I try to move the king, when the checking piece is a slider I also try interposing moves. When it is double-check (dubbel-schaak) you only have to try captures and moves with the king.
Maybe it sounds complicated, but with bit-boards it is a piece of cake.
Code: Select all
template <int S>
void gen_captures_to_target(position_t *pos, bb_t tgt, move_t *&move)
{
bb_t src = bbRank<S, 6> & pos->pawns(S);
gen_promotion<S, mvNW>(pos, src, tgt, move, mtPromotion | mtCapture | mtPawn);
gen_promotion<S, mvNE>(pos, src, tgt, move, mtPromotion | mtCapture | mtPawn);
src = ~bbRank<S, 6> & pos->pawns(S);
gen_pawn<S, mvNW>(pos, src, tgt, move, mtCapture | mtPawn);
gen_pawn<S, mvNE>(pos, src, tgt, move, mtCapture | mtPawn);
if (pos->enpsqr() > 0)
{
bb_t epb = Bit(pos->enpsqr());
if (tgt & SHR<S, 8>(epb))
{
gen_pawn<S, mvNW>(pos, src, epb, move, mtCapture | mtEnpassant | mtPawn);
gen_pawn<S, mvNE>(pos, src, epb, move, mtCapture | mtEnpassant | mtPawn);
}
}
gen_piece<S, Knight>(pos, tgt, move, mtCapture);
gen_piece<S, Bishop>(pos, tgt, move, mtCapture);
gen_piece<S, Rook>(pos, tgt, move, mtCapture);
}
template <int S>
void gen_interpositions(position_t *pos, bb_t tgt, move_t *&move)
{
gen_promotion<S, mvFW>(pos, bbRank<S, 6> & pos->pawns(S), tgt, move, mtPromotion | mtPawn);
bb_t src = ~bbRank<S, 6> & pos->pawns(S);
gen_pawn<S, mvFW>(pos, src, tgt, move, mtQuiet | mtPawn);
gen_pawn<S, mvF2>(pos, src, tgt, move, mtQuiet | mtPawn | mtPawn2);
gen_piece<S, Knight>(pos, tgt, move, mtQuiet);
gen_piece<S, Bishop>(pos, tgt, move, mtQuiet);
gen_piece<S, Rook>(pos, tgt, move, mtQuiet);
}
template <int S>
void gen_evasion_captures(position_t *pos, move_t *&move)
{
gen_piece<S, King>(pos, pos->occupied(Opp(S)) & ~pos->attacked(), move, mtCapture | mtKing);
if (Popcount(pos->checkers()) == 1)
gen_captures_to_target<S>(pos, pos->checkers(), move);
}
template <int S>
void gen_evasion_moves(position_t *pos, move_t *&move)
{
gen_piece<S, King>(pos, pos->empty() & ~pos->attacked(), move, mtQuiet | mtKing);
if (Popcount(pos->checkers()) == 1 && (pos->checkers() & (pos->pawns(Opp(S)) | pos->knights(Opp(S)))) == 0)
gen_interpositions<S>(pos, masks::between[pos->kingsqr(S)][LSB(pos->checkers())], move);
}
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: QSearch perft
I tried to optimize king capture once. Was a failure and debugging with using only bitboards won't make it easier.Joost Buijs wrote: ↑Fri May 24, 2019 4:04 pmI assume it will gain something. Check evasions are usually just a few moves, and in your case you have to try all possible moves and check whether the king gets captured at the next ply, or something like this.Henk wrote: ↑Fri May 24, 2019 3:40 pmBy the way is doing check evasions in QSearch an elo gain?Joost Buijs wrote: ↑Fri May 24, 2019 3:33 pmI'm happy to know that our numbers are the same. Henk is not generating check-evasions and that causes the difference.
Maybe I should implement them too if I have time.
At this moment I don't call QSearch in normal search when in Check.
When there is only 1 checking piece, I try to capture that piece, if that doesn't work I try to move the king, when the checking piece is a slider I also try interposing moves. When it is double-check (dubbel-schaak) you only have to try captures and moves with the king.
Maybe it sounds complicated, but with bit-boards it is a piece of cake.
I guess you already know the bitboard value of say square e5 by heart. I remember h1 being 128.
By the way when doing check evasion is it allowed to stand pat that is doing no moves when in check?
I also don't understand futility pruning. Say at depth 1 it prunes a move that gives check while opening a diagonal for a bishop capturing the queen.
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: QSearch perft
No, I really don't know bitboard values by heart, I use these bitboard tools made by Julien Marcel BLH and BLH2.Henk wrote: ↑Fri May 24, 2019 4:17 pm I guess you already know the bitboard value of say square e5 by heart. I remember h1 being 128.
By the way when doing check evasion is it allowed to stand pat that is doing no moves when in check?
I also don't understand futility pruning. Say at depth 1 it prunes a move that gives check while opening a diagonal for a bishop capturing the queen.
When in check you are never allowed to stand pat, otherwise you will miss a lot of checkmates.
With futility pruning you say, 'my evaluation is so good and I'm on the move so I might as well return the evaluation immediately'. Of course this will make mistakes when there are threats or when there is 'zugzwang', but search is very permissive for an occasional error now and then. All these techniques are very dependent upon the quality of the evaluation function, when the evaluation function is bad futility will be bad too.
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: QSearch perft
if I change Qperft definition I get them too. So difference was definitely check evasions.abulmo2 wrote: ↑Fri May 24, 2019 3:24 pmI get the same number as you :Joost Buijs wrote: ↑Fri May 24, 2019 2:43 pm These are the counts I get per move at depth 4, maybe it helps.
g2h3: 381
d5e6: 436
e5g6: 495
e5d7: 642
e5f7: 475
e2a6: 343
f3h3: 397
f3f6: 521
Maybe somebody else can verify these numbers.
I think the difference is due to the fact that you don't generate check-evasions, because check-evasions will contain non captures too. So you have to generate evasions when the king is in check. You have to do this in quiescence too, otherwise your quiescence will make very big errors.Code: Select all
g2h3 381 d5e6 436 e5g6 495 e5d7 642 e5f7 475 e2a6 343 f3h3 397 f3f6 521 total : 3690 leaves
and at depth 5:Code: Select all
g2h3 2617 d5e6 3202 e5g6 3482 e5d7 4086 e5f7 2908 e2a6 2285 f3h3 2768 f3f6 3999 total : 25347 leaves
Code: Select all
static public ulong Perft3(IChessPosition position, int depth, bool epMoves = true)
{
var inCheck = position.InCheck(position.OpponentColor, King_Kind, position.CurPlayerColor, null);
var moves = inCheck ? LegalMoveGenerator.ListLegalMoves(position, epMoves): LegalMoveGenerator.ListLegalCaptures(position, epMoves);
if (depth == 1) return (ulong)moves.Count;
ulong count = 0;
var board = position.Board;
var other = board.Other;
foreach (MoveBase mv in moves)
{
var field = mv.GetCaptureLocation(position);
var capture = field == 0 ? none : board.PieceSort(field);
mv.Apply(position);
count += Perft3(position, depth - 1, true);
mv.TakeBack(position, capture, field, other);
}
return count;
}
-
- Posts: 1563
- Joined: Thu Jul 16, 2009 10:47 am
- Location: Almere, The Netherlands
Re: QSearch perft
Of course, if you generate ALL legal moves when in check you should get the same counts, it means that for kiwipete your move-gen and move-do/undo logic seems to work like it should.Henk wrote: ↑Fri May 24, 2019 7:26 pmif I change Qperft definition I get them too. So difference was definitely check evasions.abulmo2 wrote: ↑Fri May 24, 2019 3:24 pmI get the same number as you :Joost Buijs wrote: ↑Fri May 24, 2019 2:43 pm These are the counts I get per move at depth 4, maybe it helps.
g2h3: 381
d5e6: 436
e5g6: 495
e5d7: 642
e5f7: 475
e2a6: 343
f3h3: 397
f3f6: 521
Maybe somebody else can verify these numbers.
I think the difference is due to the fact that you don't generate check-evasions, because check-evasions will contain non captures too. So you have to generate evasions when the king is in check. You have to do this in quiescence too, otherwise your quiescence will make very big errors.Code: Select all
g2h3 381 d5e6 436 e5g6 495 e5d7 642 e5f7 475 e2a6 343 f3h3 397 f3f6 521 total : 3690 leaves
and at depth 5:Code: Select all
g2h3 2617 d5e6 3202 e5g6 3482 e5d7 4086 e5f7 2908 e2a6 2285 f3h3 2768 f3f6 3999 total : 25347 leaves
Code: Select all
static public ulong Perft3(IChessPosition position, int depth, bool epMoves = true) { var inCheck = position.InCheck(position.OpponentColor, King_Kind, position.CurPlayerColor, null); var moves = inCheck ? LegalMoveGenerator.ListLegalMoves(position, epMoves): LegalMoveGenerator.ListLegalCaptures(position, epMoves); if (depth == 1) return (ulong)moves.Count; ulong count = 0; var board = position.Board; var other = board.Other; foreach (MoveBase mv in moves) { var field = mv.GetCaptureLocation(position); var capture = field == 0 ? none : board.PieceSort(field); mv.Apply(position); count += Perft3(position, depth - 1, true); mv.TakeBack(position, capture, field, other); } return count; }
-
- Posts: 7218
- Joined: Mon May 27, 2013 10:31 am
Re: QSearch perft
QPerft extracted from my QSearch code was about 350 lines of code. So I can't publish it here.
Giving same results by the way after similar modifications that is generate ALL legal moves when in check.
Giving same results by the way after similar modifications that is generate ALL legal moves when in check.
-
- Posts: 558
- Joined: Sat Mar 25, 2006 8:27 pm
Re: QSearch perft
Do you have to do something to avoid a search explosion? It seems once you add non-capturing evasions, you open yourself up to perpetual checks.Joost Buijs wrote: ↑Fri May 24, 2019 2:43 pm
I think the difference is due to the fact that you don't generate check-evasions, because check-evasions will contain non captures too. So you have to generate evasions when the king is in check. You have to do this in quiescence too, otherwise your quiescence will make very big errors.