50% Improvement in Perft Speed

I decided to see what Mavericks performance is like through the lens of a profiler.  I’m using CodeBlocks as my GCC IDE.  It was remarkably simple to get the profiler working.  The first thing I notices was the large amount of time taken to see if a move resulted in discovered check, and therefore illegal.  The time consumed by this one (small) procedure was almost as much as the move-generation code.  I thought something must be wrong.

After some prodding and poking of the code I realized there was a much better way to accomplish the same task.  In my original code I was doing a looking from the king through the “from_square” and seeing if there was a rook, bishop or queen on the relevant path.  This is what I did in Monarch but it’s really letter-box style thinking.  It’s much faster to calculate all of pins at the start of the move generation process and store them in a bitboard.  Then when you make the move you only need to check if there is a discovered check if the piece is pinned (a simple “AND”) – which is rare.  You still need to perform the check if the piece is pinned, it’s a king move or an en-passant move.  I also “inlined” the “is_in_check_after_move” procedure.

The result of these changes is a boost to the perft speed of about 50%.  Maverick now crunches 76 million nps on my humble 2.2 GHz i7 notebook. 

As an aside, my notebook is two years old.  On my wife’s newer 2.4 GHz i7 Maverick’s speed is 99 million nps. Somehow Maverick’s architecture is more suited to newer machines.  I assume it’s a bigger cache.

  • good job!

    I do something similar:
    – no need to check for discovered checks for pieces that are not pinned.
    – pinned pawns, rooks, bishops and queens can move only “in direction of pin”.
    – pinned knights can’t move.

    If you are still using 32 bit, switching to 64 bit is likely to give you another 2X improvement. I got ~2.2X improvement just by a 64 bit recompile.

  • Steve Maughan

    Thanks Ankan – I’m already using 64 bit! I quite happy with my times. I don’t want to optimize too much at this stage but the pinned pieces improvement was worthwhile.

    Steve

    • Marco Belli

      I’d like to try your engine, and study it.
      could you please provide the code? the link on the home page doesn’t seems to work for me

      • Steve Maughan

        Hi Marco – Maverick doesn’t yet play chess. It’s really in the early stages of development. You can access the files via this link:

        https://www.dropbox.com/sh/2o75xnyg6iklna5/rPrnH78Rla

        This is just a link to my source code DropBox folder. Once Maverick plays chess I’ll make it easier to download.

        • Marco Belli

          I have downloaded the code & compiled it. very fast indeed.
          good work 🙂

          • Steve Maughan

            Thanks Marco – in reality I think Maverick is just average when it comes to speed. There are faster Perft calculators out there (e.g. Ankan’s)

    • Zao Wu

      Hi Steve and Ankan – a question for the two of you (one year late on the scene)! How do you efficiently generate the pins (i.e. make the process faster than checking if the king is in check using a super piece)? I mean, apart from the improvement where you check to see if the king is on the same line as a sliding piece? I intend to use a 10×12 mailbox structure (newbie programmer), so is efficient pin detection only available to bitboards?

  • giuseppe

    hi Steve,
    If see only pinned pieces, what happens if the opponent checks?

    • Steve Maughan

      Hi Guiseppi,

      When you’re in check I use a different routine to generate the evade check moves.

      Discovered check can only happen if the piece is pinned.

      Hope this helps,

      Steve