Oh, absolutely. I was talking about what happens after searching the hash-move(s) (and killers).
We need to scrap Perft()
Moderator: Ras
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: We need to scrap Perft()
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: We need to scrap Perft()
Is this also true in Lazy SMP?
I thought the whole trick there was to have multiple threads doing their own search. So a good move could still end up in TT?
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Daniel Inführ - Software Developer
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: We need to scrap Perft()
Why should any of this impact lazy SMP? The whole point of lazy SMP is that you don't have to change your search or anything, really. Just invoke the same search on the same node with multiple threads. Of course, you will still want to order your hash-moves first and killers second. If there is a cut-off save the move-generation entirely for the node...dangi12012 wrote: ↑Sat Dec 18, 2021 1:21 amIs this also true in Lazy SMP?
I thought the whole trick there was to have multiple threads doing their own search. So a good move could still end up in TT?
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: We need to scrap Perft()
How can you know if a capture is going to be winning or losing before you generate it?
I think staged move generation, trying the TT move first (if you have one) before even generating moves, is the biggest improvement with regard to move generation that can be made, precisely because you don't have to generate any moves if the TT move creates a cutoff.Or maybe completely different than that. But still in batches. Such that we save the time of move generation for a good bunch of moves completely, because they come after a cut-off. I actually do intend to switch to fully legal movegen at some point, but I would not even dream about getting twice the performance. That's simply a pipe-dream.
Because oft things like that, spending time to make a move generator fully legal (without using in_check() on every move) may even be a waste of time. It will speed up move generation and perft because there, you need all the moves. I think it wouldn't change the engine's overall speed by a lot.
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: We need to scrap Perft()
I can't - you're right about that. I should have written "probably winning/losing captures". "(probably) winning captures" are captures where the attacking piece is less valuable than the victim piece - this ensures that the moves which will be sorted first by MVV-LVA will be generated first, too.
I totally agree. In my engine I also try killers after the TT moves (those are stored in the killers table and do not need to be generated either). There's one caveat to this, though: to make it work really well you need to remember tactical killers as well (and search them before the quiet killers). For this reason I actually maintain two seperate killerslot lists: one for tactical killers and one for quiet killers. I consider extending that with another killerslot list for mate-killers, but haven't tried that yet.mvanthoor wrote: ↑Sat Dec 18, 2021 10:27 am I think staged move generation, trying the TT move first (if you have one) before even generating moves, is the biggest improvement with regard to move generation that can be made, precisely because you don't have to generate any moves if the TT move creates a cutoff.
Certainly not by the factor that Daniel is claiming. I think having a fully legal movegen might still be an advantage: it's probably still a tad faster, but the main argument for me is that with a fully legal movegen comes additional information stored in the board representation (like check-masks, pin-mask and the like) which should be useful in other places, too.mvanthoor wrote: ↑Sat Dec 18, 2021 10:27 am Because oft things like that, spending time to make a move generator fully legal (without using in_check() on every move) may even be a waste of time. It will speed up move generation and perft because there, you need all the moves. I think it wouldn't change the engine's overall speed by a lot.
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: We need to scrap Perft()
I still wonder if keeping those masks is actually faster than a call to is_square_attacked(us, king_square), which is just a bunch of chained OR's that return TRUE as soon as the first of them becomes true.R. Tomasi wrote: ↑Sat Dec 18, 2021 10:41 am Certainly not by the factor that Daniel is claiming. I think having a fully legal movegen might still be an advantage: it's probably still a tad faster, but the main argument for me is that with a fully legal movegen comes additional information stored in the board representation (like check-masks, pin-mask and the like) which should be useful in other places, too.
Is it really faster to go through all that to save putting some moves into the move list, compared to just calling this function when a move _is_ actually tried?
Code: Select all
pub fn square_attacked(&self, board: &Board, attacker: Side, square: Square) -> bool {
let attackers = board.bb_pieces[attacker];
let occupancy = board.occupancy();
let bb_king = self.get_non_slider_attacks(Pieces::KING, square);
let bb_rook = self.get_slider_attacks(Pieces::ROOK, square, occupancy);
let bb_bishop = self.get_slider_attacks(Pieces::BISHOP, square, occupancy);
let bb_knight = self.get_non_slider_attacks(Pieces::KNIGHT, square);
let bb_pawns = self.get_pawn_attacks(attacker ^ 1, square);
let bb_queen = bb_rook | bb_bishop;
(bb_king & attackers[Pieces::KING] > 0)
|| (bb_rook & attackers[Pieces::ROOK] > 0)
|| (bb_queen & attackers[Pieces::QUEEN] > 0)
|| (bb_bishop & attackers[Pieces::BISHOP] > 0)
|| (bb_knight & attackers[Pieces::KNIGHT] > 0)
|| (bb_pawns & attackers[Pieces::PAWN] > 0)
}
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: We need to scrap Perft()
It depends on the use-case I'd say and how efficient the legal-movegen implementation is. But the things I have in mind arent't things that can be solved by just checking if a square is attacked. For example, I would like to have an evaluation term that scores how many moves a piece is away from attacking a pinned piece - I'd need the entire pinmask for that.mvanthoor wrote: ↑Sat Dec 18, 2021 11:23 amI still wonder if keeping those masks is actually faster than a call to is_square_attacked(us, king_square), which is just a bunch of chained OR's that return TRUE as soon as the first of them becomes true.R. Tomasi wrote: ↑Sat Dec 18, 2021 10:41 am Certainly not by the factor that Daniel is claiming. I think having a fully legal movegen might still be an advantage: it's probably still a tad faster, but the main argument for me is that with a fully legal movegen comes additional information stored in the board representation (like check-masks, pin-mask and the like) which should be useful in other places, too.
Is it really faster to go through all that to save putting some moves into the move list, compared to just calling this function when a move _is_ actually tried?
I haven't tried it yet, but making the move generator fully legal is, to be honest, way down the list of things to do.Code: Select all
pub fn square_attacked(&self, board: &Board, attacker: Side, square: Square) -> bool { let attackers = board.bb_pieces[attacker]; let occupancy = board.occupancy(); let bb_king = self.get_non_slider_attacks(Pieces::KING, square); let bb_rook = self.get_slider_attacks(Pieces::ROOK, square, occupancy); let bb_bishop = self.get_slider_attacks(Pieces::BISHOP, square, occupancy); let bb_knight = self.get_non_slider_attacks(Pieces::KNIGHT, square); let bb_pawns = self.get_pawn_attacks(attacker ^ 1, square); let bb_queen = bb_rook | bb_bishop; (bb_king & attackers[Pieces::KING] > 0) || (bb_rook & attackers[Pieces::ROOK] > 0) || (bb_queen & attackers[Pieces::QUEEN] > 0) || (bb_bishop & attackers[Pieces::BISHOP] > 0) || (bb_knight & attackers[Pieces::KNIGHT] > 0) || (bb_pawns & attackers[Pieces::PAWN] > 0) }
Well, certainly not on top of my list either. Just so many other things do to currently, that spending time on a fully legal movegen is simply not what will advance my engine most (if at all).
Edit: I wanted to post the equivalent function from my engine here for comparision. Turns out I do not have any function that determines if a square is attacked or not (seems like I don't need it). Closest thing I have is a function that gives me a bitmask of all attackers:
Code: Select all
template<size_t ATTACKINGPLAYER>
static squaresType attackers(const boardType& position, const squareType square) noexcept
{
PYGMALION_ASSERT(square.isValid());
constexpr const playerType attacker{ static_cast<playerType>(ATTACKINGPLAYER) };
constexpr const squaresType none{ squaresType::none() };
squaresType attackers{ none };
const squaresType allowed{ ~position.totalOccupancy() };
attackers |= movegenKnight.attacks(square, allowed) & position.pieceOccupancy(knight);
attackers |= movegenKing.attacks(square, allowed) & position.pieceOccupancy(king);
const squaresType pawns{ position.pieceOccupancy(pawn) };
const squaresType piecemap{ squaresType(square) };
if constexpr (attacker == whitePlayer)
{
const squaresType temppiecemap{ piecemap.down() };
attackers |= (temppiecemap.left() | temppiecemap.right()) & pawns;
}
else
{
const squaresType temppiecemap{ piecemap.up() };
attackers |= (temppiecemap.left() | temppiecemap.right()) & pawns;
}
const squaresType slidersHV{ (position.pieceOccupancy(queen) | position.pieceOccupancy(rook)) };
const squaresType slidersDiag{ (position.pieceOccupancy(queen) | position.pieceOccupancy(bishop)) };
attackers |= movegenSlidersHV.attacks(square, allowed) & slidersHV;
attackers |= movegenSlidersDiag.attacks(square, allowed) & slidersDiag;
return attackers & position.playerOccupancy(attacker);
}
-
- Posts: 1960
- Joined: Tue Apr 19, 2016 6:08 am
- Location: U.S.A
- Full name: Andrew Grant
Re: We need to scrap Perft()
You are objectively wrong -- or at least no one else in the computer chess world has figured out how to make using a fully legal move generator faster than the alternative. Stockfish for example pre-computes pinners/pinned in each position. With that knowledge, as well as a Bitboard of checking pieces, its pretty easy to do virtually fully-legal move gen.dangi12012 wrote: ↑Fri Dec 17, 2021 10:20 pmYou generate them. You put them into the movelist. You sort the bigger movelist. Sometimes you even get to the point where you test them.Ras wrote: ↑Fri Dec 17, 2021 9:56 pmFirst, that's not true because most of the generated moves are never made. In an actual engine, you generate them to select the best one as per your move sorting and aim for an early beta cut-off. Second, you don't need make/in-check for the vast majority of the moves, i.e. moves other than king moves, en passant, or get-out-of-check moves, all of which are rather rare.dangi12012 wrote: ↑Fri Dec 17, 2021 5:34 pmWell first of all if your movegenerator is pseudolegal you are losing 50% of performance at least. You spend time to make unmake a move thats not possible.
Because in an actual engine, you would waste that effort on moves that will never even be tried.Why not make the case that every movegen should be legal in the first place?
Worst of all you need a seperate "IsLegal" call for every move. Even when they would legal to begin with.
So its not an argument that holds to scrutiny. It needs much more useless cpu time.
So a "larger" move list is not typical, and even then "testing" them all is not a given. Verifying legality after the fact by looking at the previous STM's king, is obviously effort that would ideally be cut out.
If you think you know a way to do fully legal generation, in the context of an engine, then I assure you the Stockfish team will merge your patch the moment it passes their testing for speedups. In lieu of that, it remains the case in computer chess that fully legal move generators are worse.
-
- Posts: 1062
- Joined: Tue Apr 28, 2020 10:03 pm
- Full name: Daniel Infuehr
Re: We need to scrap Perft()
Please use precice language. Objective is a word you have to back up with claims and studies which you didnt. Its your opinion. Absence of a an elo gaining branch for an alternative movegen is neither proof nor evidence against the validity. SF devs discussed it but increasing movegen speed by even 20% gains less than 3 Elo. So as long as tinkering elsewhere brings more elo/manhour that has the priority.AndrewGrant wrote: ↑Sat Dec 18, 2021 12:59 pm You are objectively wrong -- or at least no one else in the computer chess world has figured out how to make using a fully legal move generator faster than the alternative.
I dont know how you can come to the conclusion that having the cpu do useless work is better. But you do you...
Worlds-fastest-Bitboard-Chess-Movegenerator
Daniel Inführ - Software Developer
Daniel Inführ - Software Developer
-
- Posts: 307
- Joined: Wed Sep 01, 2021 4:08 pm
- Location: Germany
- Full name: Roland Tomasi
Re: We need to scrap Perft()
Yeah well... you claim 100% increase, not 20%. I'm pretty sure the SF team would merge a 3 ELO gain nevertheless. But if you talk about backing up claims, I'd say it's you who should back up your claimdangi12012 wrote: ↑Sat Dec 18, 2021 2:03 pmPlease use precice language. Objective is a word you have to back up with claims and studies which you didnt. Its your opinion. Absence of a an elo gaining branch for an alternative movegen is neither proof nor evidence against the validity. SF devs discussed it but increasing movegen speed by even 20% gains less than 3 Elo. So as long as tinkering elsewhere brings more elo/manhour that has the priority.AndrewGrant wrote: ↑Sat Dec 18, 2021 12:59 pm You are objectively wrong -- or at least no one else in the computer chess world has figured out how to make using a fully legal move generator faster than the alternative.
