We need to scrap Perft()

[R. Tomasi]

Many engines generate moves in batches.

The easiest and probably most bang for the buck trick is not generating moves if you have a validated hash move because that has at least 90% odds of generating a beta cut-off.

Oh, absolutely. I was talking about what happens after searching the hash-move(s) (and killers).

[dangi12012]

Many engines generate moves in batches.

The easiest and probably most bang for the buck trick is not generating moves if you have a validated hash move because that has at least 90% odds of generating a beta cut-off.

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?

[R. Tomasi]

Many engines generate moves in batches.

The easiest and probably most bang for the buck trick is not generating moves if you have a validated hash move because that has at least 90% odds of generating a beta cut-off.

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?

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...

[mvanthoor]

Why do you think that pseudo-legal movegen engines must generate _all_ moves at once? Many engines generate moves in batches. Like winning captures first, then quiet moves, then losing captures.

How can you know if a capture is going to be winning or losing before you generate it?

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.

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.

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.

[R. Tomasi]

Why do you think that pseudo-legal movegen engines must generate _all_ moves at once? Many engines generate moves in batches. Like winning captures first, then quiet moves, then losing captures.

How can you know if a capture is going to be winning or losing before you generate it?

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 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.

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.

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.

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]

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.

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.

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)
    }
    

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.

[R. Tomasi]

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.

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.

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)
    }
    

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.

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.

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);
}

[AndrewGrant]

Well 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.

First, 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.

Why not make the case that every movegen should be legal in the first place?

Because in an actual engine, you would waste that effort on moves that will never even be tried.

You generate them. You put them into the movelist. You sort the bigger movelist. Sometimes you even get to the point where you test them.
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.

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.

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.

[dangi12012]

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.

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.

I dont know how you can come to the conclusion that having the cpu do useless work is better. But you do you...

[R. Tomasi]

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.

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.

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 claim