Bits and more bits, chess, bit boards and tidbits.

Join Date
Apr 2002
Location
No income tax, no capital gains tax. Freedom!
Posts
8,351
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?
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.
 
i don't see a problem... (or i'm not reading it right)

this is how things are stored/processed in the graphic cards for faster access and easier manipulation (planes of bits - or groups of bits, one pixel is then presented by information from multiple planes).

each square can be addressed by just 6-bit, another 6-bit is enough to hold information about any given piece (black or white, king, queen, rook, pawn, queened pawn...).

and if i read it right there is mention of twelve 64-bit sets that together make one full chess board with all pieces.

graphic card designers/programmers know more tidbits and tricks than chess programmers...;)
 
What are you thinking?

panic mode said:
i don't see a problem... (or i'm not reading it right)

this is how things are stored/processed in the graphic cards for faster access and easier manipulation (planes of bits - or groups of bits, one pixel is then presented by information from multiple planes).

each square can be addressed by just 6-bit, another 6-bit is enough to hold information about any given piece (black or white, king, queen, rook, pawn, queened pawn...).

and if i read it right there is mention of twelve 64-bit sets that together make one full chess board with all pieces.

graphic card designers/programmers know more tidbits and tricks than chess programmers...;)
The graphics card designers have special hardware that allows them do it differently. Chess programming and graphics programming are two different things. They are writing colors mulitple of 8 bits at a time which is a lot easier than shifting bit fields of 6 bit. 6 bits doesn't even go into 32 or 64 bits evenly.
 
I never enjoyed chess (too slow for a game).

The way I read the original post, this is challenge to present a chessboard. Same post (second half of it) explains how it could be done. I was suggesting that 12 bits could be enough to hold all information of each piece (even queened pawn) by enumerating piece types instead of having separate bitmap for each information. this requires more processing though...
 
Last edited:

Similar Topics

How does one find the least significant bit WITHOUT: 1 checking for a bit being set in each bit position. 2 looping. 3 using lookup tables. 4...
Replies
19
Views
5,787
Assume there is a set of 16 bits in N7:0. What is the result in N7:1 SUB 0 N7:0 N7:1 AND N7:0 N7:1 N7:1
Replies
8
Views
5,581
Hi I am being given several fault words (as a DINT) from a Drive that I am receiving into a Compactlogix L33ER controller. I have a small...
Replies
12
Views
1,101
Dear Fellows; I am working on a very old machine which is designed in GE 90-30 PLC system. I have some difficulties like 1. How a force to...
Replies
3
Views
298
Hi All, I am trying to write some simulation logic for an existing project im working on. Does anyone know if this is possible to write to...
Replies
6
Views
1,259
Back
Top Bottom