If you aren't keen on doing the bitwise comparisons yourself, and can hook into a C++ DLL, you can use a vector<bool> -- it's a special combination that only uses one bit per element, and gives you access to the individual elements via the at or [] operator just like normal.
[.net] I need a 256-bit integer
Quote:Original post by taby
If you aren't keen on doing the bitwise comparisons yourself, and can hook into a C++ DLL, you can use a vector<bool> -- it's a special combination that only uses one bit per element, and gives you access to the individual elements via the at or [] operator just like normal.
Um...?! Sorry but thats just completly rediclous. In any case, System.Collections.BitArray does that anyway. And second of all, if he was to go that route in the first place, an array to store those numbers would end up as around about... ooo... 618970019642690137449562112 Terra bytes.
So what really needs to be done is to use a Hash code and comparable structure, and stick them into a hashtable as they are generated.
The structure may only need to store 3 integers, say, for bad example, named A,B,C.
struct blag
{
public int A,B,C;
}
then the hash code returned could just be A^B^C. That would be pretty straight forward, and be a good approximation.
Then finally, the comparable implementation is blindingly simple too, but works fine:
ie,
public int CompareTo(blag a)
{
if (a.A != A)
return a.A - A;
if (a.B != B)
return a.B - B;
return a.C - C;
}
very very simple yet does everything you need.
}
Quote:Original post by NexusOne
Actually, it's for a Chess AI, for storing a unique ID to a chess board state. I need at least 132 bits even after using Huffman encoding to completely represent a board in int form, which means even a 128-bit int is too small.
Wtf?
Chess ai's only need 64 bits AT THE MOST!
You don't need a perfect hash, an imperfect one would probably be better. (for this purpose)
From,
Nice coder
Author
64 bits? That's 1 bit per square, how does that store what type of piece is on that square? I need 4 bits per square to adequately describe every square. If I used Huffman encoding, with 0 for empty, 101 for pawn, 100 for enemy pawn, and 11.. for all other pieces (I optimized it) I still end up with 132 bits for just the starting location. In weird situations with multiple queens I may need more than that, but either way that's already well over 64.
I understand that the hash will have collision-- I don't have 10^50 or whatever bytes to use, but I need to store a unique ID at every hash element so that I know when collision between two different game states occurs in the hash. I'm using this struct/big int for the ID, not for the key, which I realize needs only 32 bits since my hash table is NOT going over 4 gb.
I understand that the hash will have collision-- I don't have 10^50 or whatever bytes to use, but I need to store a unique ID at every hash element so that I know when collision between two different game states occurs in the hash. I'm using this struct/big int for the ID, not for the key, which I realize needs only 32 bits since my hash table is NOT going over 4 gb.
Are you using System.Collections.Hashtable? Assuming your "state" object implements IComparable (or you pass an appropriate IComparer into the constructor)+ then the Hashtable class will handle collisions for you as needed.
+ You've got to do one of these things anyway, or the Hashtable is useles...
+ You've got to do one of these things anyway, or the Hashtable is useles...
System.Collections.Hashtable is not very fast. I tried it for my Checkers applcation, and found it was better to just use an array and handle collisions within my alpha-beta function.
What Nice Coder means, is:
You need one 64-bit int for each piece-type on the chess-board. Each int will answer a certain question. For example, an int might answer the question: "where are the black pawns?"
This opens all kind of doors to serious and fast bitwise operators ;)
So you will need 12 (right?) * 64 bit for chess, and 4 * 32 bit for checkers (because you only use half the board).
Hope this helps
Edo
Quote:Original post by NexusOne
64 bits? That's 1 bit per square, how does that store what type of piece is on that square? I need 4 bits per square to adequately describe every square. If I used Huffman encoding, with 0 for empty, 101 for pawn, 100 for enemy pawn, and 11.. for all other pieces (I optimized it) I still end up with 132 bits for just the starting location. In weird situations with multiple queens I may need more than that, but either way that's already well over 64.
I understand that the hash will have collision-- I don't have 10^50 or whatever bytes to use, but I need to store a unique ID at every hash element so that I know when collision between two different game states occurs in the hash. I'm using this struct/big int for the ID, not for the key, which I realize needs only 32 bits since my hash table is NOT going over 4 gb.
You're doing this wrong. I've written 2 chess engines, and can tell you that yours will be slow using 256 bit integers. Rather, use 4 64 bit integers.
Google bitboards. You don't have one board describing everything. You have multiple boards, one describing one thing specifically.
PM me if you want source so you can see how to efficiently do what you are aiming for.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement