fast(er) movegen

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jackd
Posts: 25
Joined: Mon Dec 10, 2018 1:45 pm
Full name: jack d.

Re: fast(er) movegen

Post by jackd » Wed Dec 26, 2018 6:10 pm

hgm wrote:
Mon Dec 10, 2018 8:01 pm
Ratosh wrote:
Mon Dec 10, 2018 7:58 pm
HGM's move generation on qperft is a good reference for speed. If you want to change your board representation there is no doubt that bitboard representation is the fastest.
Actually I doubt that.
Shouldn't everything be faster with bit-boards?

-get a bit-board for the piece in question via bitscan

-get a bit board representing all places it could go on an empty board via table look up

-logical "and" the "to" bit-board with: A(not your sides pieces) B(the pin ray) C( ways to exit check: aka capture the piece giving check or get in the way of slider)

-index the bit in "from" and then each bit in "to" while appending moves to the movelist

A is readily available, B can C can be calculated quickly. Pawns can only be "anded" with C if it is a pawn capture or C is not a an enemy piece. Make un make( during movegen) can be done for king, EP and castle moves.

Edit:

Actually I meant get an index for the piece in question at first.

jackd
Posts: 25
Joined: Mon Dec 10, 2018 1:45 pm
Full name: jack d.

Re: fast(er) movegen

Post by jackd » Wed Dec 26, 2018 6:25 pm

C is just an "or" of the following:

pawns giving check, knights giving check, bishops and knights giving check along with all squares in between. If more than one piece is giving check king moves only.

To calculate B, first get a bit-board for all the pinned pieces on your side. Then when generating a specific piece, check if it is pinned. if it is you have four part switch statement to find B.

Harald
Posts: 264
Joined: Thu Mar 09, 2006 12:07 am

Re: fast(er) movegen

Post by Harald » Wed Dec 26, 2018 7:36 pm

Here is a little piece of history that partly matches this topic:

Search found 1 match: +Bitboard +methods +compared
with author Harald:
http://talkchess.com/forum3/viewtopic.p ... ed#p140111

Maybe I find an old zipped source of the old test engine Elephant 1.07 and can send it via e-mail on request.

Harald

User avatar
hgm
Posts: 23069
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: fast(er) movegen

Post by hgm » Thu Dec 27, 2018 9:47 am

jackd wrote:
Wed Dec 26, 2018 6:10 pm
hgm wrote:
Mon Dec 10, 2018 8:01 pm
Ratosh wrote:
Mon Dec 10, 2018 7:58 pm
HGM's move generation on qperft is a good reference for speed. If you want to change your board representation there is no doubt that bitboard representation is the fastest.
Actually I doubt that.
Shouldn't everything be faster with bit-boards?

-get a bit-board for the piece in question via bitscan

-get a bit board representing all places it could go on an empty board via table look up

-logical "and" the "to" bit-board with: A(not your sides pieces) B(the pin ray) C( ways to exit check: aka capture the piece giving check or get in the way of slider)

-index the bit in "from" and then each bit in "to" while appending moves to the movelist

A is readily available, B can C can be calculated quickly. Pawns can only be "anded" with C if it is a pawn capture or C is not a an enemy piece. Make un make( during movegen) can be done for king, EP and castle moves.

Edit:

Actually I meant get an index for the piece in question at first.
The point is that this is information that is not very useful, so it doesn't matter how fast or slow I can get it. I am seldomly interested in where a given piece can go. Most of the time I want to know which pieces can go to a given square. To get there from the way you describe, you would have to generate moves for all pieces, select those to the target, for each target.

flok
Posts: 55
Joined: Tue Jul 03, 2018 8:19 am
Full name: Folkert van Heusden
Contact:

Re: fast(er) movegen

Post by flok » Fri Jan 11, 2019 2:53 pm

Ronald wrote:
Thu Dec 20, 2018 7:54 pm
Afterthought: The latest Embla version I have is version 1.0.1. I ran a perft 6 with Embla and it took Embla 107.3 seconds to finish. That is 128 times slower than rofChade. I don't know how far the perft routines are comparable and if the current version takes the same amount of time, but maybe there is some serious elo gain for Embla with a faster movegen :lol:
Current version, 2.0.6, does it in 7.78s. 2.0.5 in 37s. There was a deficiency in the perft implementation.
www.vanheusden.com: Embla / PuppetMaster / DeepBrutePos / Pos / Feeks

Post Reply