What's the fastest move generator?

[mfournier]

Hello,
reading the bitboard thread, I was thinking about what would be the fastest move generator.

I know there are severaly ways of generating moves: 0x88, move table (IIRC Bruce Moreland used that), bitboard, ecc.

Has anyone ever compared them? What would be the fastest one on todays hardware?

[hgm]

I would expect a mostly branchless 0x88 generator like employed by GNU Chess (I was told). This is based on a table

nextToSqr = table[pieceType][fromSqr][toSqr][board[toSqr]==Empty];

Of course the question is a bit ill defined; the answer depends a lot on what the purpose of the move generator is. In perft you always want to generate all moves, but in an engine you almost always want to generate only captures. In the latter case bitboard can easily outcompete a naive mailbox generator. Probably mailbox with incrementally updated attack map would be fastest for that purpose.

[Desperado]

Hello,
reading the bitboard thread, I was thinking about what would be the fastest move generator.

I know there are severaly ways of generating moves: 0x88, move table (IIRC Bruce Moreland used that), bitboard, ecc.

Has anyone ever compared them? What would be the fastest one on todays hardware?

Hello Marcel,

i dont know nothing about your intention behind the question,
but i ithink it is necessary to answer in an adequat way.

Bitboarders for example like to differ between
"move generation" and "attack getter" functions.

Although these functions generally are doing the same stuff,
the goal from bitboards is not only to get a fast move generation
code but also to be very efficient in other places like evaluation.
In other words to get a general faster code for an engine playing
chess.

Of course there can be other goals like an extremly fast perft
program or whatever.

Another option can be to mix technologies of course.

Now, imo for a chess playing software bitboards are the preferable
choice nowadays. Especially "Magic Bitboards" are very fast and
can be handled in a very elegant way.

Having the evaluation fuctions in mind, you can compute attacks(moves)
very fast and mask whatever you like to mask then. The serializing of
the piece bitboards and computing or simply looking up
the current attack bitboard is the most costly operation normally,
the rest is very efficient ANDing,ORing,XORing, so most of the time
extremly fast logical processor operations.
So, the more stuff you include into your evaluation the more you
will profit from bitboard technologies. Just think of pin computations,
or checking file,ranks and other groups of squares, which you can
handle with only one logical operation and a mask. All this sums together.

Further, imo , the period of really "cheap evaluation" has elapsed, like
we could see it in Fruit's period. The capabilities of today's search
methods simply need more accurate and simply more evaluation features.

eg: a material+pst searcher has clearly limits, doesnt matter how good
the search is, you need knowledge to improve and this knowledge should
be integrated in the cheapest way possible.

Finally, IMO , it is very hard to reach the same performance with
other technologies than bitboards, if not today already, then tomorrow.

So, if your intention is to get a high performance for a chess engine
to be competitive tomorrow, just go with bitboards.


Just my 2 cents , and i know it will not last long, somebody will
tell you sth into the opposite direction, lol...

regards, Michael

[diep]

My move generator i open sourced a year or 10 ago.

It's fast. About 2.2x faster than crafty for generating semi
legal moves in a list i benchmarked it at the time.

It's 32 bits of course.

At old K7 2.1Ghz i searched 2.5 million nps with a chessprogram with it, using a small evalution function and Diep's SEE functions.

Please note move generation doesn't eat all system time. Evaluation does.

Incremental attacktables i use in Diep, that's fastest in 32 bits and not in bitboards.

Bitboards are fast if you can do with 1 bit of information. In my attacktables i want however how many attackers attack a specific square and which one.

So 1 bit is not enough then. In such case of course 32 bits is faster. To do the same thing in bitboards is about a factor 4 slower. Which is logical if you think about it, as in 32 bits you just do what you need to do, that's update the fields you want to update. Doing that in bitboards is kind of a non-incrementa proces, then you have to get out the bits and combine them, which is massive shifting, obviously that's a LOT slower.

In general spoken, if you have to convert the 1 bit of information that bitboards hold to something, say a square, then we can prove bitboards are quite slow. If you need more than 1 bit of information you have the same problem.

In fact even bitshifting is not perfectly fast at core2/i7, it just has 2 units that can do that, out of the 4 it has for simple instructions.

Most processors can issue more 32 bits instructions per cycle than for 64 bits. Don't forget this. So the discussion on the hardware side we soon can close in favour of 32 bits. This won't change of course for CPU's.

GPU's are entirely 32 bits. To do things 64 bits they need to combine all sorts of 32 bits logics, that's up to factor 4 slower not seldom.

Try bitshifting at a gpu in 64 bits. Won't happen.

Regardless whether you use bitboards or 32 bits, knowing what you are doing is most important. In both bitboards as well as 32 bits you will end up with total unreadable patterns in evaluation if you want the ultimate speedmonster. How do you debug it then and improve it and maintain it?

For bitboards the slow thing is getting bits out of the bitboard. It's a sequential proces and not all units on processor can execute this instruction.

Some people also use magics. However processor is duck slow for multiplication. Out of the 4 execution units (so to speak) of core2/i7 only 1 unit of them can do multiplication and you can issue 1 integer multiplication every 3.75 cycles. Usually the other units get blocked as well when it is doing a multiplication.

In 32 bits you just loop and directly have the move stored. In 3.75 cycles in 32 bits you generate already 3 moves or so...

So that's always faster of course for generating the moves.

Realize in 90s the assembler engines were very fast. Schach 3.0 was under 600 cycles per node. This was at a pentium processor.

A pentium processor is really bad compared to todays core2/i7 processor.

A pentium processor can execute at most 2 instructions at the same time in a limited manner. i7 can do 4 easily in 32 bits.

Yet 0 of todays bitboard engines achieve this speed of under 600 cycles a node.

It's trivial 8+32 bits is faster even today, yet of course the only thing you can get for free is the move generator, the rest you have to build yourself.

This is why bitboards got popular together with some not realizing the reality at assembler level.

For the bitboard guys, they could cut'n paste 99% of their datastructure easily from the many posters on it online.

I only offer the move generator for free, the rest you have to make yourself. 99.99% of todays cloners are too lazy for that.

They do some postings to get a discussion here and further do nothing except cut'n paste something and 'be part of the community on paper'.

If you want worlds fastest engine, then assembler is the language and it'll be 8+32 bits. Unsigned of course.

At those speedy levels most dudes in this forum test, a huge hashtable is total useless anyway, so the 32 bits limit of RAM is no big deal.

The fanboys here just could cut'n paste things easily on bitboards. There never were discussions on 'how to do things faster in 32 bits' discussions over here of course - as that is what everyone was using a few years ago.

My pawns i always implemented in a bitboard type array, around 1994. Not 64 bits yet 32 bits. So i never needed bitboards for that in the first place.

If you search for fast solutions in 8+32 bits, you'll find them, yet not many will be helping you as they made BIG CASH with this.

[smatovic]

My move generator i open sourced a year or 10 ago.

Where to get?

--
Srdja

[Don]

Hello,
reading the bitboard thread, I was thinking about what would be the fastest move generator.

I know there are severaly ways of generating moves: 0x88, move table (IIRC Bruce Moreland used that), bitboard, ecc.

Has anyone ever compared them? What would be the fastest one on todays hardware?

The answer depends a lot on what you want the move generator to do. If it's for a chess program it's much faster to build a capture only generator and then a second generator which generates all non-captures, but that is not the fastest way if you want all the moves at once.

Also, do you want legal moves or pseudo legal moves? If you want a move generator that generates ALL the legal moves as fast as possible including testing for illegal moves due to moving into check (or failing to move out of check) it's s totally different thing that you might use in a chess program. Also to be considered is legal castling. Most program do not try to generated a legal castling move, they wait util it's time to actually execute a castling move then test - it's faster because many times you get a cutoff before getting to the castling move.

So your question is rather ill-defined.

If you are building a move generator for a user interface and want it to be fast you probably want to produce a list of fully legal move and also have check information because presumably you will use this to also produce fuly verified SAN notation.

Most chess programs have several move generators in them - to be fast in specific situations like for getting out of check.

[rreagan]

Hello,
reading the bitboard thread, I was thinking about what would be the fastest move generator.

I know there are severaly ways of generating moves: 0x88, move table (IIRC Bruce Moreland used that), bitboard, ecc.

Has anyone ever compared them? What would be the fastest one on todays hardware?

If you are planning on creating your own chess engine, my advice is, do not worry about which method is fastest. Just pick one and get a working engine that plays 100% legal chess. Only then should you go back and clean it up and make it faster.

For example, if you chose bitboards, there are dozens of ways to implement a bitscan function. Your first bitscan should look like this:

Code: Select all

int bitscan (Bitboard b) {
    for &#40;int i = 0; i <64; i++) &#123;
        if &#40;b & mask&#40;i&#41;)
            return i;
&#125;

You can make if fast later, after you know everything is working (running perft, etc).

If you worry about how fast everything is before you have something working, your program will have bugs. You will waste a lot of time tracking them down. You will also waste a lot of time piddling with trying to make it faster, and making it faster is very, very far down the list of things that are important to making a good chess engine.

[kbhearn]

With how frequent serialising a bitboard happens, i'd have to disagree with that being your 'first bitscan', especially when your compiler probably offers an intrinsic that will happily compile to a hardware bitscan (and then instead you can worry about compatibility with ancient systems later if you ever care).

[stegemma]

I wrote an old move generator in C, then some other in assembly. They all use the same approach (see the Drago sources and an old post about Raffaela move generator). The assembly one was the fastest. Recently i've tried a C++ move generator. So, from the language point of view, my euro cents are all for assembly. Debugging assembly program is hardest, so maybe a C program is better. In fact, my last program is written in C++ and the move generator is more like C than C++ (but written in C++). The C++ one (with polymorphism and so on) was too slow.

In the old Drago and previous experiment, i've tried 0x88 generation, in Raffaela and Freccia was a little different but still not bit board. Bitboard is usefull for further evaluation but is not the best choice for fast full pseudo legal move generators IMHO. A complete program is not only move generator, so you have to choose the best solution, despite from generator speed. That's why my new program uses something like bitboard: the board is a map of 64 bit and so the position of every kind of piece. I use this structure:

u64 boMyPieces, boOtherPieces, boKings, boQueens, boRooks, boBishops, boKnights, boPawns;

then i use normal shifts and test, to generates move. In fact, is more similar to Drago move generator than to bitboard. I don't use table of precompiled move attacks, for now. The program is enough fast for my needs.

So, first draw in your mind the whole program, then choose a move generator or invent your own and be ready to change it during development (as i've done with my slow C++ generator).

[diep]

My move generator i open sourced a year or 10 ago.

Where to get?

--
Srdja

email?