hybrid-board-representation

[likeawizard]

Try if a hybrid board representation could speed up movegen

[jw1912]

In terms of speeding up move generation, branchless code is the way as missed branch prediction causes huge slowdown. For example, in your move generator

pieces = b.Pieces[b.Side][QUEENS]
for pieces > 0 {
    from = pieces.PopLS1B()
    attacks = GetQueenAttacks(from, b.Occupancy[BOTH]) & ^b.Occupancy[b.Side]
    for attacks > 0 {
        to = attacks.PopLS1B()
        move = Move(to|from<<6) | (5+offset)<<12
        if b.Occupancy[b.Side^1].Get(to) != 0 {
            move |= IS_CAPTURE
        }
        moves = append(moves, move)
    }
}

But it could be made completely branchless, by writing instead

pieces = b.Pieces[b.Side][QUEENS]
for pieces > 0 {
    from = pieces.PopLS1B()
    attacks = GetQueenAttacks(from, b.Occupancy[BOTH]) & ^b.Occupancy[b.Side]
        enemies = b.Occupancy[b.Side^1]
        captures = attacks & enemies
        quiets = attacks & ^enemies
    for quiets > 0 {
        to = quiets.PopLS1B()
        move = Move(to|from<<6) | (5+offset)<<12
        moves = append(moves, move)
    }
        for captures > 0 {
        to = captures.PopLS1B()
        move = Move(to|from<<6) | (5+offset)<<12 | IS_CAPTURE
        moves = append(moves, move)
    }
}

This can be done similarly for every other piece, including pinned/unpinned pieces and pawns that can either promote or double push.

[likeawizard]

@JacquesRW, thank you for your input. Not sure how I missed this comment. I am aware of the branch prediction issue and have worked on it in the past. I really appreciate your comment it makes sense. I had not touched the movegen for quite a bit. The quiet and capture splitting might come in handy when/if making a staged move generator.

For pinned pieces I tried that approach in my legal movegen but it seemed that pseudolegal was faster as I verify the legality only in the search reoutine. As many moves are not played at all due to cut-offs postponing that check seemed to have an overall increase in performance since many times it wasn't necessary to check.

[jw1912]

@likeawizard, I can confirm that pseudo-legal movegen is faster for actual search, and only gets better as the branching factor improves, provided the make/unmake functions are sufficiently fast (matters a lot more than movegen imo, especially with incrementally updated hashes, psts, etc that generally cause a 20-25% drop in perft performance on their own).

I also wrote a legal move generator for my first engine, but now am using a pseudo legal one in my second, not only for the speed, but also for much simpler code and less generics bloat. For pinned pieces I found that it was around the same speed to generate pseudo-legally, except for pawn pushes which was quite a bit worse than generating them pseudo-legally.