Author: Travers Waker
Date: 02:30:34 04/03/01
Hi I am trying to find some free info on how 0x88 board representation works, but there seems to be hardly anything about it on the web. Is 0x88 obsolete, replaced by bitboard? Actually, I don't see these two (0x88 and bitboard) as competing with each other - to me it looks like they could be used together. Let me explain: Firstly, it seems to me to make no sense to store each individuals piece type's current positions as a bitmap. By this I mean, for example, representing the current postition as a set of bitboards: WhiteKnights, BlackKnights, WhiteBishops, BlackBishops, etc... This just makes it more difficult to extract the position of a particular piece, even using the famous x^(x-1) trick. For example, when generating moves for the white knight, one first has to determine the number of the square it is on (using x^(x-1) trick on the WhiteKnight bitboard) and then use this number to reference some pre-computed array of knight attack boards. What was gained by having the current position of the white knight represented by a bitboard? Using a scheme like having a list of piece types and the square they currently occupy seems to make more sense to me. No x^(x-1) wizardry required. I think I read somewhere that Chess 4.5 did something like this. So what bitboards would be useful as part of the current position? I think it may make sense to have BlackPawns and WhitePawns bitboards because you can generate all the moves for all the pawns of a particular colour at once using simple bit shifts (I think that's from David Eppstein's course). I also think the pawn bitboards could be useful in the avaluation function because it may be easier to detect particular pawn patterns in the position using bitboards (I haven't started writing my evaluation functions yet, so this is just a suspicion). You also definitely need two of AllPieces, WhitePieces and BlackPieces (the third one can be generated from any of the other two at little cost). These are used to & (bitwise AND) with the attackboards that you look up in your pre-computed arrays so that you can determine which moves are captures and ignore illegal moves that involve capturing your own pieces. I think those should be the only bitboards in the current position representation. All the rest of the piece positions should be represented in some other way in which it is easier to extract the current sqaure number of a piece (i.e. no x^(x-1) required). Am I wrong? One possible candidate for storing the postitions of the other pieces (all except the pawns) is 0x88, although I can't find enough info on this to decide wether it's useful or not. The other method I can think of, which I've mentioned already, is keeping a list of piece types and the square numbers they currently occupy, I think this is from Chess 4.5, but I also remember reading something about how this program implemented the list as an array, and could not handle promotions properly because it assumed that there would never be more pieces of a particular type than had started on the board at the beginning of the game. Using a more dynamic linked list instead of an array could address this problem. Does anyone have any other ways of solving this? Another thought: In this email I've assumed that everyone pre-computes arrays of attack bitboards. Does anyone precompute moves and store them in some other way (i.e. not bitboards)? One attractive thing about using arrays of bitboards is that all the possible moves from a particular square can always fit into 64 bits. This is particularly important for a piece like the Queen, which may be able to move to many different squares from its current position. For this reason, I assume that there's no other viable pre-computation scheme, or am I wrong? One last thought: There seems to be lots of info on the web about game-tree search algorithms, but almost nothing about evaluation functions. I guess this is because search algorithms are of general academic interest while evaluation functions are not. I also suspect that people regard evaluation functions as more of a secret. Can anyone point me to (or email me) any useful articles going into depth about evaluation functions? Yes, I know the source of various programs is downloadable, but that's hardly easy reading, and its also an aim of mine to produce an entirely original program based entirely on what I understand. I fear I might be tempted to implement various things purely because I saw them in someone else's code, rather than discussing and understanding these things. I also don't want to end up with a clone of another program, or a hybrid of several other programs, so I'd prefer to avoid anything more than illustrative code snippets. Maybe the things I'm asking are dealt with in the ICCA Journals, but unfortuanately I can't possibly afford to get all the back-issues of this. Maybe someone who has a full collection of ICCA Journals can answer this question for me: How many of these contain information which is of great use to a beginner/intermediate chess programmer? Maybe someone should publish (on the web) a list of which articles (and which volume/issue) they consider to be of great use to someone like myself. If it's no more that 5 or 6 journals that cover the core isssues, then I would be able to afford it. Also on this topic, what are the chances of ICCA ever having online journals, like the ACM has? This should make it a lot cheaper and a lot more accessible to people like myslef. Thanks for any help. Travers
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.