Transposition Tables

[bob]

Basically... I have a 4 bit number castRights=ABCD..

if a piece is moved from/to a1, then castRights &= 1101 (13)
if a piece is moved from/to h1, then castRights &= 1110 (14)
if a piece is moved from/to e1, then castRights &= 1100 (12)

So by looking at bits C and D, we can determine if castling is allowed long or short for white.

And similarly for black...
if a piece is moved from/to a8, then castRights &= 0111 (7)
if a piece is moved from/to h8, then castRights &= 1011 (11)
if a piece is moved from/to e8, then castRights &= 0011 (3)

So by looking at bits A and B, we can determine if castling is allowed long or short for black.

And if a piece is moved to/from any other square castRights &= 1111 (15)

So ultimatley I have an array
7 15 15 15 3 15 15 11
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
15 15 15 15 15 15 15 15
13 15 15 15 12 15 15 14

Hope that helps

Yes, you are right about the 4-bit value. This is actually what I do myself. I think that array is a bit of an overkill, though. I am not sure the extra memory will translate into saved time, compared to just updating the respective flag when the rooks or king move for the first time (and somehow remember it; I don't do unmake yet, so I haven't thought about that part yet).

I do it the simple and direct way. 2 bits per side. When I make a king move, I set that side's status to 0. If I move or capture either rook, I just AND that bit to zero. On unmake I just restore the status I had saved when I reached this ply. This is only done in the parts of MakeMove() that move rooks or the king, or captures a rook.

[hgm]

I suppose you can point to a post where I said "a single conditional jump wrecks performance"????

A single conditional jump certainly affects performance. Although here I believe we are talking about far more than a single conditional jump...

I can do even better than that, I can quote from it:

You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).

So why bother to react, if you have not the slightest idea what people are talking about, and can only argue from your own irrelevant pre-concptions and prejudices? What do you want to prove? That you are unable to understand pseudo-code?

Perhaps that I am unable to stand a lot of gibberish thrown in. Alpha/Beta is a well-known algorithm. With no "stop the search just because a value is outside the window" exceptions thrown in. So, perhaps I am guilty of thinking about the algorithm I thought we all used, and am guilty of that.

However, the idea is still defective from a performance perspective, which is why nobody does it.

Then is the code you posted earlier wrong? You had this line twice:

if (eval >= beta) go to cutoff
eval = search()
if (eval >= beta) go to cutoff

That is not "zero cost". And for a case that is very rarely happening at that...

Seems to me you are clearly complaining about the occurence of a single extra if-goto (which I hope you agree _is_ a single conditional jump). You consider the presence of that if-statement "so defective from a performance perspective that nobody uses it". I don't think the way a paraphrased your point of view does it any unjustice.

It is abundantly clear to everyone that still bothers reading this thread, that you habitually don't bother to read the postings that you are supposed to be answering. When I write that I prefer a different way to handle the mating-distance problem, and give pseudo-code to exactly point out how it works, you first go harassing me for a dozen posts about that it is in error, without having the slightest idea what it is about. If it finally turns out it is _you_ who is in error, you start complaining that you could not expected to understand that it was different from what everyone does, (which is exactly why I said I posted it. When I discuss in minute detail an example of how my pseudo-code would lead to branches being pruned due to mate-distance _you_ claim that this cannot happen because it is not what alpha-beta would do, and when it finally dawns on you that it is what I do, you come with wild accusations that _I_ am not using standard terminology and talk gibberish (while I only gave pseudo-code and never did mention alpha-beta), etc.

Stop trying to shift the blame for your own inadequacies to others! I am sick and tired of it!

If you think that my algorithm is a sub-optimal trade-off between speed and performance, you could have said it on page 3 of this discussion. I happen to think differently, as I care about my engines not looking stupid by needing 2 minutes to perform a mate-in-1 as much as you care about yours resigning. Stressing the 0.1% performance hit after 20 postst with extremely thick and inane comments as a justification for it all is, in view of the "1% performance improvement is not worth it" stance on underpromotions a total farce.

[hgm]

For under-promotions this is not quite the case, but under conditions where not only the speed, but also the size is important, under-promotion is truly defective: these rules offer resigning as a fully legal alternative.

So it is your belief that not doing underpromotions is actually going to let you perform _better_?

What exactly does 'not' mean in your 30+ year-old CS/AI dictionary?

Fortunately, I stick with "standard definitions" of the words I use... So it means _exactly_ what it usually means and I don't need to pause and give a definition since I am not changing it.

So which part of the 'not' in my post was it that you did not understand?

So best case saved about 1/2 second out of 50. Barely 1%. In a simple ending. In the other more normal positions, it saves zero.

Do you really believe that that tiny speedup is going to produce any measurable Elo gain? Do you also believe that not handling underpromotions is never going to cause you to lose a game or miss winning a game?

This is indeed a truly remarkable statement, for someone that just argued that the presence of a single if statement, which he (mistakenly) thought would cause an overhead of 0.1% in a search routine, was such a ridiculous performance breaker that he could not possibly be expected to understand the pseudo-code.

That's because you want to intentionally draw some tangential conclusion that was not intended. I'm going to make it as clear as possible:

(1) including under-promotions has _zero_ impact on your program's Elo, particularly since Elo is an integer value. I had to pick a simple endgame to see any effect in speed at all. And if you look at the times I posted and the nodes searched, the majority of that 1% time change apparently was unrelated to the underpromotion removal because the nodes searched did not change significantly. What it was, I don't care at the moment.

(2) Not including under-promotions is going to result in lost games here and there. I have seen them in 5-round ACM events, I have seen them in WCCC events. And even though the effect is small, it is not nearly as small as the tiny gain one gets by omitting them.

Therefore, including them will win a game here and there. Excluding them will not win a thing. Which, then, do you choose? for me the choice is obvious. And since I am really trying to write a program to play the game of chess as defined by the official rules, it is a no-brainer. I'd like to exclude en passant captures, they require extra handling that is far more invasive and costly than the code to handle under-promotions. I'd even like to exclude castling. More special case code to generate a two-piece move, not to mention dealing with castling status throughout the tree. But the rules of chess define the moves and I go by that...

For under-promotions, I don't worry about a single branch. Because there is no branch needed to exclude them. I just commented that code _out_ in my test. For hashing, you are doing more than a single jump. You are modifying the bounds at every point in the tree. Which is going to have a L1 hit (if lucky) or a L2 hit penalty at every last ply. On my 2ghz laptop, where I search about 2M nodes per second, that turns into about 1000 clocks / node. I don't want to add X clocks to that, even if X is somewhere in the 4-20 range, if I can avoid it altogether.

So can we get back to reality, and stop making outrageous statements about what I am claiming, and stick to _exactly_ what I am saying. I notice you seem to not like it when I provide _real_ data. I ran a longer test last night using a set of positions I often run just as a sanity check after making a significant change. Omitting under-promotions had no effect whatsoever in almost all of them. Only in simple endgames was there any difference and the difference was always well under the 1% in my example I posted here.

You can, if you want, actually _run_ these tests for yourself, and then you won't be guessing, postulating, pontificating, and exaggerating about what will happen. Then you will actually _know_. In the case of under-promotions, I am not guessing about what it costs. I actually _know_. Simply because I ran the test to see what it does...

Can we now move on since it is obvious that omitting them is a bad idea with no gain whatsoever, and a very real problem in some games?

[bob]

I suppose you can point to a post where I said "a single conditional jump wrecks performance"????

A single conditional jump certainly affects performance. Although here I believe we are talking about far more than a single conditional jump...

I can do even better than that, I can quote from it:

You are correct. It never occurred to me that one would make a basic change to alpha/beta that hurts everywhere but when dealing with mates (probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).

So why bother to react, if you have not the slightest idea what people are talking about, and can only argue from your own irrelevant pre-concptions and prejudices? What do you want to prove? That you are unable to understand pseudo-code?

Perhaps that I am unable to stand a lot of gibberish thrown in. Alpha/Beta is a well-known algorithm. With no "stop the search just because a value is outside the window" exceptions thrown in. So, perhaps I am guilty of thinking about the algorithm I thought we all used, and am guilty of that.

However, the idea is still defective from a performance perspective, which is why nobody does it.

Then is the code you posted earlier wrong? You had this line twice:

if (eval >= beta) go to cutoff
eval = search()
if (eval >= beta) go to cutoff

That is not "zero cost". And for a case that is very rarely happening at that...

Seems to me you are clearly complaining about the occurence of a single extra if-goto (which I hope you agree _is_ a single conditional jump). You consider the presence of that if-statement "so defective from a performance perspective that nobody uses it". I don't think the way a paraphrased your point of view does it any unjustice.

It is abundantly clear to everyone that still bothers reading this thread, that you habitually don't bother to read the postings that you are supposed to be answering. When I write that I prefer a different way to handle the mating-distance problem, and give pseudo-code to exactly point out how it works, you first go harassing me for a dozen posts about that it is in error, without having the slightest idea what it is about. If it finally turns out it is _you_ who is in error, you start complaining that you could not expected to understand that it was different from what everyone does, (which is exactly why I said I posted it. When I discuss in minute detail an example of how my pseudo-code would lead to branches being pruned due to mate-distance _you_ claim that this cannot happen because it is not what alpha-beta would do, and when it finally dawns on you that it is what I do, you come with wild accusations that _I_ am not using standard terminology and talk gibberish (while I only gave pseudo-code and never did mention alpha-beta), etc.

Stop trying to shift the blame for your own inadequacies to others! I am sick and tired of it!

If you think that my algorithm is a sub-optimal trade-off between speed and performance, you could have said it on page 3 of this discussion. I happen to think differently, as I care about my engines not looking stupid by needing 2 minutes to perform a mate-in-1 as much as you care about yours resigning. Stressing the 0.1% performance hit after 20 postst with extremely thick and inane comments as a justification for it all is, in view of the "1% performance improvement is not worth it" stance on underpromotions a total farce.

Aha, so yet another definition. "probably doesn't hurt a lot" is defined as "wrecks performance". I'm slowly catching on here. What I write means what _you_ want it to mean, not what the usual definitions of the individual words would lead the _normal_ person to conclude???

Here's the part of the first post you seem to be referencing:

(probably doesn't hurt a lot, but every branch is bad and every bit of code that gets executed at every node is bad when it is ineffective at most).

So that is "wrecks" (probably doesn't hurt a lot, but does hurt) in the "new vocabulary" we have to use? Also this:

However, the idea is still defective from a performance perspective, which is why nobody does it.

So "defective from a performance perspective" is equivalent to "wrecks performance"???

and of course, we can't skip this:

That is not "zero cost". And for a case that is very rarely happening at that...

So "not zero cost" is the same as "wrecks performance"??? Ever get the idea that you are "putting words into my mouth?" If not, you should. What you imagine I write and what I really write are two _completely_ different things.

So either let's us normal definitions here or give up. "wrecks" means "destroys" or "seriously damages". Etc. I didn't say "wrecks". Nor did I even imply it.

[bob]

For under-promotions this is not quite the case, but under conditions where not only the speed, but also the size is important, under-promotion is truly defective: these rules offer resigning as a fully legal alternative.

So it is your belief that not doing underpromotions is actually going to let you perform _better_?

What exactly does 'not' mean in your 30+ year-old CS/AI dictionary?

Fortunately, I stick with "standard definitions" of the words I use... So it means _exactly_ what it usually means and I don't need to pause and give a definition since I am not changing it.

So which part of the 'not' in my post was it that you did not understand?

The part about "not quite". Which is not the same as "not".

So best case saved about 1/2 second out of 50. Barely 1%. In a simple ending. In the other more normal positions, it saves zero.

Do you really believe that that tiny speedup is going to produce any measurable Elo gain? Do you also believe that not handling underpromotions is never going to cause you to lose a game or miss winning a game?

This is indeed a truly remarkable statement, for someone that just argued that the presence of a single if statement, which he (mistakenly) thought would cause an overhead of 0.1% in a search routine, was such a ridiculous performance breaker that he could not possibly be expected to understand the pseudo-code.

That's because you want to intentionally draw some tangential conclusion that was not intended. I'm going to make it as clear as possible:

(1) including under-promotions has _zero_ impact on your program's Elo, particularly since Elo is an integer value. I had to pick a simple endgame to see any effect in speed at all. And if you look at the times I posted and the nodes searched, the majority of that 1% time change apparently was unrelated to the underpromotion removal because the nodes searched did not change significantly. What it was, I don't care at the moment.

(2) Not including under-promotions is going to result in lost games here and there. I have seen them in 5-round ACM events, I have seen them in WCCC events. And even though the effect is small, it is not nearly as small as the tiny gain one gets by omitting them.

Therefore, including them will win a game here and there. Excluding them will not win a thing. Which, then, do you choose? for me the choice is obvious. And since I am really trying to write a program to play the game of chess as defined by the official rules, it is a no-brainer. I'd like to exclude en passant captures, they require extra handling that is far more invasive and costly than the code to handle under-promotions. I'd even like to exclude castling. More special case code to generate a two-piece move, not to mention dealing with castling status throughout the tree. But the rules of chess define the moves and I go by that...

For under-promotions, I don't worry about a single branch. Because there is no branch needed to exclude them. I just commented that code _out_ in my test. For hashing, you are doing more than a single jump. You are modifying the bounds at every point in the tree. Which is going to have a L1 hit (if lucky) or a L2 hit penalty at every last ply. On my 2ghz laptop, where I search about 2M nodes per second, that turns into about 1000 clocks / node. I don't want to add X clocks to that, even if X is somewhere in the 4-20 range, if I can avoid it altogether.

So can we get back to reality, and stop making outrageous statements about what I am claiming, and stick to _exactly_ what I am saying. I notice you seem to not like it when I provide _real_ data. I ran a longer test last night using a set of positions I often run just as a sanity check after making a significant change. Omitting under-promotions had no effect whatsoever in almost all of them. Only in simple endgames was there any difference and the difference was always well under the 1% in my example I posted here.

You can, if you want, actually _run_ these tests for yourself, and then you won't be guessing, postulating, pontificating, and exaggerating about what will happen. Then you will actually _know_. In the case of under-promotions, I am not guessing about what it costs. I actually _know_. Simply because I ran the test to see what it does...

Can we now move on since it is obvious that omitting them is a bad idea with no gain whatsoever, and a very real problem in some games?

No comment on the main part of my comments???

[hgm]

Of course not. It contains nothing I didn't know myself, or have anything to add to. It is exactly what "not quite" means. "Not, but only by a small margine".

And, like I mentioned, if strength is not your sole concern, but Elo/size, or if you would be forced to squeeze your engine into a 4KB microcontroller chip for in a toy, it is enough to tip the balance.

So I hope you were writing this for others, or you have been wasting your time by, as we say in Dutch, "trying to batter down an open door".