Faster Movelist in Mailslot Engines?

[dangi12012]

There is no reason to prepare a list; the squares along the ray can be generated incrementally by just adding the step to the to-square (rather than incrementing the list index and fetching the next square). This is what micro-Max does. Basically this is directly searching the moves that come out of the move generator, as this is how the inner loop of the move generator generated the to-squares.

I just tested it. memcpy into a buffer seems to be faster than a step by step solution. This allows sorting. I will share it soon but I think I found something completely new in mailslots. A way to generate moves in a mailslot board representation without a single if statement.

The algorithms now seem to be:
Mailslot O(n) - raywalking
Bitboard O(1) - fancy hashing/pext

I have found it this week: A mailslot algorithm that is O(1)!
The wiki is missing a comparison between slider algorithms that state the O notation and Memory consumption in a table to compare algorithms

[Ras]

memcpy into a buffer seems to be faster than a step by step solution. This allows sorting.

Every move needs to have some sort of static ranking info like MVV/LVA, depth killers, and history. It has to be ranked as per the board situation where the move was generated, so just copying the generated move into a list is not good enough. This is totally obvious to anyone who has actually worked on a chess engine and not just a move generator.

I have found it this week: A mailslot algorithm that is O(1)!

The Big Oh notation doesn't even mean anything with small N. That's really basic.

[dangi12012]

memcpy into a buffer seems to be faster than a step by step solution. This allows sorting.

Every move needs to have some sort of static ranking info like MVV/LVA, depth killers, and history. It has to be ranked as per the board situation where the move was generated, so just copying the generated move into a list is not good enough. This is totally obvious to anyone who has actually worked on a chess engine and not just a move generator.

I have found it this week: A mailslot algorithm that is O(1)!

The Big Oh notation doesn't even mean anything with small N. That's really basic.

When stockfish does:

Code: Select all

*moveList++ = make_move(to - UpRight, to);

You are telling everyone here that Stockfish developers do it wrong?

Your comment must be a bad joke.
Troll be gone.

Also when finding a better O for a problem your first instinct is to comment O notation doesnt matter because N is... "just" 27?
This will be a whole new board state algorithm - that make many difficult tasks faster than both bitboards and mailslots.

[Ras]

You are telling everyone here that Stockfish developers do it wrong?

No, I'm telling you that the obvious consequence is that you have to loop through the move list at some other place to assign the scores if you don't do that in the generator itself (MovePicker in case of Stockfish), so it's still not constant time. Moving the effort elsewhere is not eliminating the effort.

For the Big Oh, read up on second semester math stuff from back then, that's too elementary to even discuss.

[dangi12012]

You are telling everyone here that Stockfish developers do it wrong?

No, I'm telling you that the obvious consequence is that you have to loop through the move list at some other place to assign the scores if you don't do that in the generator itself (MovePicker in case of Stockfish), so it's still not constant time. Moving the effort elsewhere is not eliminating the effort.

For the Big Oh, read up on second semester math stuff from back then, that's too elementary to even discuss.

RAS: You dont have to loop twice - thats an improvement. SF and your engine and everyone elses does *movelist++ = ... and loops somewhere else a second time as you have discovered. Its possible to skip loop nr. 1.

I really think you either dont know how O notation works or you dont understand implications regarding memory size. Since its also important to stay in L1 for real life and not academic performance. You cannot even write it correctly - there is no such thing as Oh.

You are doing nuance trolling. You see my point - I think you are smart enough to understand it - but your comments pick one word and pretend you didnt understand me and you try to see it wrong.

I am saying there is a way that makes mailslot slider lookups as fast or even faster than bitboards. The algorithm I discovered is not described in the wiki and will be something new.

[connor_mcmonigle]

...
I really think you either dont know how O notation works or you dont understand implications regarding memory size. Since its also important to stay in L1 for real life and not academic performance. You cannot even write it correctly - there is no such thing as Oh.

Let P be the set of legal chess positions. Observe that ||P|| is finite.
Let M be some legal move generator program defined on input of P with finite runtime for all x \in P.
Observe that there exists some constant T = max runtime of M on P.
Therefore, all move generators with finite runtime for all P are constant time (M \in O(1)) as any move generator's runtime can be upperbounded by some constant T.

It's evident you don't understand big O notation. Ras is correct.

[dangi12012]

...
I really think you either dont know how O notation works or you dont understand implications regarding memory size. Since its also important to stay in L1 for real life and not academic performance. You cannot even write it correctly - there is no such thing as Oh.

Let P be the set of legal chess positions. Observe that ||P|| is finite.
Let M be some legal move generator program defined on input P with finite runtime for all P.
Observe that there exists some constant T = max run time of M on P.
Therefore, all move generators with finite runtime for all P are constant time (M \in O(1)) as any move generator's runtime can be upperbounded by some constant T.

It's evident you don't understand big O notation. Ras is correct.

Wow are you serious? Its about the sliding piece lookup where:
You either have algorithms that depend on how many squares to walk like a simple for loop. Or you do not like a hashing algorithm. The first depends on N (the squares to walk). and the second does not. I use O notation like it is defined correctly... and I use it like everyone else in the industry.


I dont know where you went to school. Lets apply to sorting algorithms I just changed a few words and you will see why I am tired of the quarter knowledge you people have:

Let P be a set of numbers. Observe that ||P|| is finite.
Let M be some sorting program defined on input P with finite runtime for all P.
Observe that there exists some constant T = max run time of M on P.
Therefore, all sorting algorithms with finite runtime for all P are constant time (M \in O(1)) as any sorting algorithm runtime can be upperbounded by some constant T.

You say: "I can upperbount it with T so it is O(1)"
No. No it is not. You accuse me of getting the basics wrong and then you go ahead to embarass yourself. I am tired of this. Every comment is like yours. Totally wrong.

[Ras]

Let P be a set of numbers. Observe that ||P|| is finite.

It's not because N is not bounded. That's the point of Big Oh. Elementary.

[dangi12012]

Let P be a set of numbers. Observe that ||P|| is finite.

It's not because N is not bounded. That's the point of Big Oh. Elementary.

You know connor_mcmonigle told me that all sorting algorithms are O(1) because and I quote now:

Observe that there exists some constant T = max run time of M on P.
Therefore, all algorithms with finite runtime for all P are constant time (M \in O(1)) as any algorithm runtime can be upperbounded by some constant T.

If you are working in IT I would be happy if you quit now before breaking something important.
I cannot take either of you seriously. Not even a little bit. Stop trolling.

[connor_mcmonigle]

...

I dont know where you went to school. Lets apply to sorting algorithms I just changed a few words and you will see why I am tired of the quarter knowledge you people have:

Let P be a set of numbers. Observe that ||P|| is finite.
Let M be some sorting program defined on input P with finite runtime for all P.
Observe that there exists some constant T = max run time of M on P.
Therefore, all sorting algorithms with finite runtime for all P are constant time (M \in O(1)) as any sorting algorithm runtime can be upperbounded by some constant T.

You say: "I can upperbount it with T so it is O(1)"
No. No it is not. You accuse me of getting the basics wrong and then you go ahead to embarass yourself. I am tired of this. Every comment is like yours. Totally wrong.

Wow. Your failure to understand my very simple proof is astounding. The set of possible inputs to a sorting algorithm is not finite so there is no upper bound on the runtime. The same trick doesn't work.

This is really elementary stuff.