Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


#ActualÁlvaro

Posted 27 June 2013 - 07:18 AM


Your advice is confusing. I shouldn't call anyone an authority but I should implicitly trust you based on the fact that I don't even know you?

 

No, you shouldn't trust me. You should only believe what I say because it's convincing. But I have a decent track record of getting things right. The reputation score in these forums is an imperfect indication of that. For people that have been around here long enough, they probably [hopefully] have had good experiences with my suggestions before. It's rather annoying that you would claim it can't be done with 49 bits when I think I just explained how it's done.

 

But let's get back to the technical details, which is what really matters.

 

 


Anyways, this is a place where we should be trying to clarify. I am still not understanding your approach. If we marked the highest bit with a single 1, we couldn't differentiate between each player. If you're feeling threatened/impatient perhaps you could just link to the original implementation? I tried googling around for it, briefly, but couldn't find it.

 

Perhaps Paradigm Shifter's explanation is clear to you. Just in case, I'll try to explain it in a different way.

 

Take a connect-4 position on a 7x6 board, with white and black pieces. Extend the board to be a 7x7 board by adding an extra row at the top. Now drop a blue piece on top of each column as a marker of how filled the column is. I claim that the set of squares occupied by either a white or a blue piece completely describes the position.

 

If you are given the set of squares described above, you can deduce that a square was occupied by a piece originally if and only if it is below some square in the set. If one of those squares is in the set itself, it must have contained a white piece; otherwise, it must have contained a black piece.

 

I should mention that one should be careful when using this value to compute indices into a hash table. If the hash table has a size that is a power of 2, only the low bits of the key will be used to determine where in the table to store the position. With this particular hash, the content of the leftmost columns completely determines the low bits, so there would be tons of collisions and the performance of the hash table would suffer. There are a couple of ways to solve this problem:

  1. Use a table whose size is not a power of 2. Some people like to use a prime number for this, although what really matters is that you pick a number N such that all the powers of 2 are different modulo N. For instance, Mersenne primes are bad choices.
  2. Do some bit-mixing on the key, like adding some constant, multiplying by some odd constant and flipping the top and bottom 32 bits. Notice that all those operations are invertible, so the key is still unique.

I recommend going with 2.


#1Álvaro

Posted 27 June 2013 - 07:17 AM


Your advice is confusing. I shouldn't call anyone an authority but I should implicitly trust you based on the fact that I don't even know you?

 

No, you shouldn't trust me. You should only believe what I say because it's convincing. But I have a decent track record of getting things right. The reputation score in these forums is an imperfect indication of that. For people that have been around here long enough, they probably [hopefully] have had good experiences with my suggestions before.

 

But let's get back to the technical details, which is what really matters.The point is that it's rather annoying that you would claim it can't be done with 49 bits when I think I just explained how it's done.


Anyways, this is a place where we should be trying to clarify. I am still not understanding your approach. If we marked the highest bit with a single 1, we couldn't differentiate between each player. If you're feeling threatened/impatient perhaps you could just link to the original implementation? I tried googling around for it, briefly, but couldn't find it.

 

Perhaps Paradigm Shifter's explanation is clear to you. Just in case, I'll try to explain it in a different way.

 

Take a connect-4 position on a 7x6 board, with white and black pieces. Extend the board to be a 7x7 board by adding an extra row at the top. Now drop a blue piece on top of each column as a marker of how filled the column is. I claim that the set of squares occupied by either a white or a blue piece completely describes the position.

 

If you are given the set of squares described above, you can deduce that a square was occupied by a piece originally if and only if it is below some square in the set. If one of those squares is in the set itself, it must have contained a white piece; otherwise, it must have contained a black piece.

 

I should mention that one should be careful when using this value to compute indices into a hash table. If the hash table has a size that is a power of 2, only the low bits of the key will be used to determine where in the table to store the position. With this particular hash, the content of the leftmost columns completely determines the low bits, so there would be tons of collisions and the performance of the hash table would suffer. There are a couple of ways to solve this problem:

  1. Use a table whose size is not a power of 2. Some people like to use a prime number for this, although what really matters is that you pick a number N such that all the powers of 2 are different modulo N. For instance, Mersenne primes are bad choices.
  2. Do some bit-mixing on the key, like adding some constant, multiplying by some odd constant and flipping the top and bottom 32 bits. Notice that all those operations are invertible, so the key is still unique.

I recommend going with 2.


PARTNERS