Sorry for this *useless* post, but I couldn't resist posting this. Yaka's movegen was rewritten yet again, and this time with legal move generation. Have a look:
Stockfish is about 3 times faster than this, and qperft is about 2.7 times faster. I use completely legal move generation, and like Texel 1.01, in case of a move of pinned piece, I simply make and unmake the move to check if the position is legal. I'm not extremely worried about speed, but I plan to add pinned piece detection scheme after it plays its first game
At least legal moves generation is much simpler than pseudo legal move generation. Today and yesterday I got trouble with solving most simple mate in N problems. So I am going to use legal moves generation only. Less trouble the better.
vittyvirus wrote:Sorry for this *useless* post, but I couldn't resist posting this. Yaka's movegen was rewritten yet again, and this time with legal move generation. Have a look:
Congratulations! The biggest trap next is to spend time on making it faster. Being within a factor 3 is great already, but most important is to have peace of mind that this part is correct, so you can focus on the evaluation and SEE+search first.
Have you noted that your generator is relatively fast in the more complex position? In my program, it is the opposite...
[d] r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq -
vittyvirus wrote:Sorry for this *useless* post, but I couldn't resist posting this. Yaka's movegen was rewritten yet again, and this time with legal move generation. Have a look:
Congratulations! The biggest trap next is to spend time on making it faster. Being within a factor 3 is great already, but most important is to have peace of mind that this part is correct, so you can focus on the evaluation and SEE+search first.
Have you noted that your generator is relatively fast in the more complex position? In my program, it is the opposite...
[d] r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq -
I see many more speedups in my movegen, especially when it comes to removing illegal moves. I guess my movegen removes illegal moves quickly when in check or in case of pinned pieces. Here's the code:
template <bool in_check>
inline void remove_illegal(Position& pos)
{
square_t ksq = pos.king_square();
Bitboard katk = AttackGen::bishop_attacks(ksq, pos.all_pieces())
| AttackGen::rook_attacks(ksq, pos.all_pieces());
// bishop_attackes() and rook_attackes() of a square automatically masks
// potential king and pawn attacks.
if (in_check)
katk |= AttackGen::attacks_by<Piece::KNIGHT>(ksq);
size_t len = 0;
GameLine gl;
bool is_legal;
for (size_t i = 0; i < size_; ++i) {
Move &m(move_stack[i]);
if ((m.get_from_sq() != ksq) && ((katk & Bitboards::SquareMask[in_check ?
m.get_to_sq() : m.get_from_sq()]) == 0) && (m.get_type() != Move::ENPASSANT))
is_legal = !in_check;
else {
pos.make_move(m, gl);
is_legal = pos.is_legal();
pos.unmake_move(m, gl);
}
if (is_legal)
move_stack[len++] = m;
}
size_ = len;
}
make_move() is quite expensive, so I guess the obvious speed up would be to use a special make_move() function that simply updates the Bitboards to check whether the other king is attacked (the position is illegal).
vittyvirus wrote:
I see many more speedups in my movegen, especially when it comes to removing illegal moves. I guess my movegen removes illegal moves quickly when in check or in case of pinned pieces. Here's the code:
template <bool in_check>
inline void remove_illegal(Position& pos)
{
square_t ksq = pos.king_square();
Bitboard katk = AttackGen::bishop_attacks(ksq, pos.all_pieces())
| AttackGen::rook_attacks(ksq, pos.all_pieces());
// bishop_attackes() and rook_attackes() of a square automatically masks
// potential king and pawn attacks.
if (in_check)
katk |= AttackGen::attacks_by<Piece::KNIGHT>(ksq);
size_t len = 0;
GameLine gl;
bool is_legal;
for (size_t i = 0; i < size_; ++i) {
Move &m(move_stack[i]);
if ((m.get_from_sq() != ksq) && ((katk & Bitboards::SquareMask[in_check ?
m.get_to_sq() : m.get_from_sq()]) == 0) && (m.get_type() != Move::ENPASSANT))
is_legal = !in_check;
else {
pos.make_move(m, gl);
is_legal = pos.is_legal();
pos.unmake_move(m, gl);
}
if (is_legal)
move_stack[len++] = m;
}
size_ = len;
}
make_move() is quite expensive, so I guess the obvious speed up would be to use a special make_move() function that simply updates the Bitboards to check whether the other king is attacked (the position is illegal).
If you are calling make-move and then checking for legality, is this really a legal move generator at all, in the usual sense of the term?
BTW, what is the CPU? And I assume you are bulk-counting at leaf nodes?
vittyvirus wrote:
I see many more speedups in my movegen, especially when it comes to removing illegal moves. I guess my movegen removes illegal moves quickly when in check or in case of pinned pieces. Here's the code:
template <bool in_check>
inline void remove_illegal(Position& pos)
{
square_t ksq = pos.king_square();
Bitboard katk = AttackGen::bishop_attacks(ksq, pos.all_pieces())
| AttackGen::rook_attacks(ksq, pos.all_pieces());
// bishop_attackes() and rook_attackes() of a square automatically masks
// potential king and pawn attacks.
if (in_check)
katk |= AttackGen::attacks_by<Piece::KNIGHT>(ksq);
size_t len = 0;
GameLine gl;
bool is_legal;
for (size_t i = 0; i < size_; ++i) {
Move &m(move_stack[i]);
if ((m.get_from_sq() != ksq) && ((katk & Bitboards::SquareMask[in_check ?
m.get_to_sq() : m.get_from_sq()]) == 0) && (m.get_type() != Move::ENPASSANT))
is_legal = !in_check;
else {
pos.make_move(m, gl);
is_legal = pos.is_legal();
pos.unmake_move(m, gl);
}
if (is_legal)
move_stack[len++] = m;
}
size_ = len;
}
make_move() is quite expensive, so I guess the obvious speed up would be to use a special make_move() function that simply updates the Bitboards to check whether the other king is attacked (the position is illegal).
If you are calling make-move and then checking for legality, is this really a legal move generator at all, in the usual sense of the term?
BTW, what is the CPU? And I assume you are bulk-counting at leaf nodes?
Hi,
I call make_move(), and then if the king is attacked, the position is illegal and the move is removed. This allows perft termination at depth == 1. I'm using a very poor Intel Core i5-2430M @ 2.4 GHz with 64-bit compile, -Ofast optimization, with g++ 4.8.1 and Windows 8 64-bit.
vittyvirus wrote:
I see many more speedups in my movegen, especially when it comes to removing illegal moves. I guess my movegen removes illegal moves quickly when in check or in case of pinned pieces. Here's the code:
template <bool in_check>
inline void remove_illegal(Position& pos)
{
square_t ksq = pos.king_square();
Bitboard katk = AttackGen::bishop_attacks(ksq, pos.all_pieces())
| AttackGen::rook_attacks(ksq, pos.all_pieces());
// bishop_attackes() and rook_attackes() of a square automatically masks
// potential king and pawn attacks.
if (in_check)
katk |= AttackGen::attacks_by<Piece::KNIGHT>(ksq);
size_t len = 0;
GameLine gl;
bool is_legal;
for (size_t i = 0; i < size_; ++i) {
Move &m(move_stack[i]);
if ((m.get_from_sq() != ksq) && ((katk & Bitboards::SquareMask[in_check ?
m.get_to_sq() : m.get_from_sq()]) == 0) && (m.get_type() != Move::ENPASSANT))
is_legal = !in_check;
else {
pos.make_move(m, gl);
is_legal = pos.is_legal();
pos.unmake_move(m, gl);
}
if (is_legal)
move_stack[len++] = m;
}
size_ = len;
}
make_move() is quite expensive, so I guess the obvious speed up would be to use a special make_move() function that simply updates the Bitboards to check whether the other king is attacked (the position is illegal).
If you are calling make-move and then checking for legality, is this really a legal move generator at all, in the usual sense of the term?
BTW, what is the CPU? And I assume you are bulk-counting at leaf nodes?
Hi,
I call make_move(), and then if the king is attacked, the position is illegal and the move is removed. This allows perft termination at depth == 1.
Yes, I can read the code. I guess to me what you're doing is not "legal move generation" but rather "pseudo-legal move generation with filtering". Not sure I understand the advantage of removing the illegal moves during generation, rather than later ...
vittyvirus wrote:
I see many more speedups in my movegen, especially when it comes to removing illegal moves. I guess my movegen removes illegal moves quickly when in check or in case of pinned pieces. Here's the code:
template <bool in_check>
inline void remove_illegal(Position& pos)
{
square_t ksq = pos.king_square();
Bitboard katk = AttackGen::bishop_attacks(ksq, pos.all_pieces())
| AttackGen::rook_attacks(ksq, pos.all_pieces());
// bishop_attackes() and rook_attackes() of a square automatically masks
// potential king and pawn attacks.
if (in_check)
katk |= AttackGen::attacks_by<Piece::KNIGHT>(ksq);
size_t len = 0;
GameLine gl;
bool is_legal;
for (size_t i = 0; i < size_; ++i) {
Move &m(move_stack[i]);
if ((m.get_from_sq() != ksq) && ((katk & Bitboards::SquareMask[in_check ?
m.get_to_sq() : m.get_from_sq()]) == 0) && (m.get_type() != Move::ENPASSANT))
is_legal = !in_check;
else {
pos.make_move(m, gl);
is_legal = pos.is_legal();
pos.unmake_move(m, gl);
}
if (is_legal)
move_stack[len++] = m;
}
size_ = len;
}
make_move() is quite expensive, so I guess the obvious speed up would be to use a special make_move() function that simply updates the Bitboards to check whether the other king is attacked (the position is illegal).
If you are calling make-move and then checking for legality, is this really a legal move generator at all, in the usual sense of the term?
BTW, what is the CPU? And I assume you are bulk-counting at leaf nodes?
Hi,
I call make_move(), and then if the king is attacked, the position is illegal and the move is removed. This allows perft termination at depth == 1.
Yes, I can read the code. I guess to me what you're doing is not "legal move generation" but rather "pseudo-legal move generation with filtering". Not sure I understand the advantage of removing the illegal moves during generation, rather than later ...
Actually, the advantage is that you only need to check the possibly pinned piece moves are legal or not... You don't have to check whether each and every move is legal or not.
mvk wrote:Congratulations! The biggest trap next is to spend time on making it faster.
Words of wisdom. When I got started, I got stuck in this trap and ended up throwing out my 0x88 board in favor of bitboards, all because I wanted faster perft.
In retrospect, switching to a bitboard representation was a good thing... but even after that, I found myself trying to get perft even faster.
Had to stop and remind myself of my original goal.
mvk wrote:Congratulations! The biggest trap next is to spend time on making it faster.
Words of wisdom. When I got started, I got stuck in this trap and ended up throwing out my 0x88 board in favor of bitboards, all because I wanted faster perft.
In retrospect, switching to a bitboard representation was a good thing... but even after that, I found myself trying to get perft even faster.
Had to stop and remind myself of my original goal.
I foucus on clean, concise, and easy to understand code more than speed. My make_move() is only ~140 lines of code, and unmake_move() around 80 lines. My whole movegen stuff (not including initialization code for magic bitboards) is ~300 lines of code. In my first engine, all this used to be 2000+ lines.
Although I'd forget about small efficiencies almost all the time, I wouldn't compromise on speed when it gets, say, 5% down. After Yaka plays its first game, I _will_ try to speed up its perft...
