Author: Bruce Moreland
Date: 11:59:33 07/08/98
Go up one level in this thread
On July 08, 1998 at 14:24:36, Robert Hyatt wrote: >On July 08, 1998 at 13:52:58, Tom Kerrigan wrote: > >>I'm starting to think that the best way to do this is as follows: >> >>int piece_list[2][16]; >>int piece_count[2]; >>int pawn_list[2][8]; >>int pawn_count[2]; >> >>The two-dimensional arrays wave a red flag at me, but I'm not sure anything can >>be done to avoid them... >again, why multiples? just piece_list[48], and have a board that points >into this list for removing pieces when they get captured... This way, >you capture pawns and everything the same way... I think that these piece list threads are over-specific. There is no one right way to do a chess program, and even if you carefully define the type of program that is desired, by specifying the amount of memory you have, the desired strength of the program, and the amount of complexity you are willing to have to put up with in order to implement the thing, I think that there are probably a lot of different ways to implement these first fiew data structures. Also, it is very difficult to discuss these data structures in a vacuum, because different implementations allow you to implement features that go beyond simply moving pieces around on the board. The data structures you choose will have an influence on your eval function, your move generation, your move ordering, and the type of quiescent search you do. Given Tom's specific implementation, he's apparently decided that he needs to be able to iterate pawns as distinct from pieces, for whatever reason, and that is why he has the distinct data structures. Regarding the two-dimensional array, these don't always have to be hideously bad. If you multiply the size of each element by the right-most of the two dimensions (for instance in "int array[X][Y]" I am talking about sizeof(int) * Y), and this is a power of two, the compiler can generate its final offset by using a shift instruction. Sometimes it is worth padding the right-most dimension in order that this optimization can happen. Shifts aren't great on Pentium architectures by they are better than multiplies. In other cases, when you specify a constant for the left-most dimension, you don't suffer any performance penalty at all (for instance "array[WHITE][i]"), of course. The use of a two-dimensional array doesn't prevent you from using more efficient accessing methods when you need to. I have these in my program, but I find ways to avoid over-using them in inner loops. I have noticed a lot of instances in Crafty where you make two seperately named tables, something like "white_passer_bonus[8]" and "black_passer_bonus[8]", and say something like if color == white use the white table, else use the black table. I've spoken to you about this and you defend doing it like this, but it still seems odd to me. You can get the exact same semantics by making a two-dimensional table and always using a constant as the left index into this, and you gain the extra flexibility of being able to use a variable index when you aren't in performance critcal situations. Also, "if" statements are pretty satanic, and I wonder if you'd go faster if you just removed a bunch of code in these cases? I have some cases in mine where I've asked the above question and come up with the answer, "no", and in those cases I have an include file that contains code in it, and I include it twice. I set up a bunch of preprocessor defines so that it's doing white, then include the file, then change them all so it's doing black. This is kind of ugly, but I've found that I've reduced the number of bugs I have due to cloning evaluation code and getting signs backwards, having bonuses for having passers move the wrong way, etc. bruce
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.