Peter Nachtwey
Member
I didn't want to hijack the thread so I started this one. It isn't strictly related to PLC but the techniques could be useful in PLCs too.
Quote:
Originally Posted by Peter Nachtwey
The data width should be 32 bit minimum but 64 bits is prefered. I can represent a chess board with 64 bits representing sets of pieces. I used to write othello and chess programs for a hobby. I came in 7th in the world first international computer and human Othello tournament ( 1980). No one help me there either. I had to read between the lines to figure the search, evalution and hash table routines.
Ok, I'm trying to figure out how to represent a chess board in 64 bits.
I started with 32 (pieces) x 64 squares. 64 = 2^6, so 6 bits to address each square. That gives 192 bits.
I'm shure that you could optimize the data in some ways (ie. you don't have to differentiate between individual pieces of the same type, bishops are limited to half of the board, etc.). However, there is additional data required for some special cases (ie. whether pawns have been queened or not).
hmm, sounds like an interesting problem.
Can you provide any more info?
Quote:
Originally Posted by Peter Nachtwey
The data width should be 32 bit minimum but 64 bits is prefered. I can represent a chess board with 64 bits representing sets of pieces. I used to write othello and chess programs for a hobby. I came in 7th in the world first international computer and human Othello tournament ( 1980). No one help me there either. I had to read between the lines to figure the search, evalution and hash table routines.
Ok, I'm trying to figure out how to represent a chess board in 64 bits.
I started with 32 (pieces) x 64 squares. 64 = 2^6, so 6 bits to address each square. That gives 192 bits.
I'm shure that you could optimize the data in some ways (ie. you don't have to differentiate between individual pieces of the same type, bishops are limited to half of the board, etc.). However, there is additional data required for some special cases (ie. whether pawns have been queened or not).
hmm, sounds like an interesting problem.
Can you provide any more info?
I did say sets of pieces. A set is a bit board of 64 bits . A bit board may have the set of all white pawns, or the set of all white nights. It takes 12 sets or 12 64 bit words to represent the chess board. What is cool is how one can maniplate the bits by using and, or and not functions. If one has the set of white knights then one can shift the white knight bit board by 17, 15, 6, 10, -6, -10, -15 and -17 to find all the locations the white knights can move to. If you and this set with the set of black pieces you have the set of black pieces you can capture with the white knight. Since these sets are very small they are pre calcuated as much as possible. For every type of piece there is an array of bit boards pre calculate so a white pawn at E4 ( (4-1)*8+'E'-'A' = 28 ) look into the WPmove[28] and find the set of places it can move to. If it ands that location the set of all pieces then result is not zero then the square in front of the pawn is occupied and the pawn can't move. If it ands the WPcap[28] with the set of black pieces and the result is not zero then the pawn can capture a white piece. You can see this is much faster than treating the chess board as an array.
Now think of those algorithms that we have discussed on this forum about counting bits and finding the least significant bit etc. All these tricks are used by the people that write computer chess programs.