Fredrik Lundh wrote: >>>Christoph Zwerschke wrote: >>Using linear arrays to represent chess boards is pretty common in >>computer chess. Often, the array is made larger than 64 elements to make >>sure moves do not go off the board but hit unbeatable pseudo pieces >>standing around the borders. But in principle, linear arrays of that >>kind are used, and for good reasons. > > really? a quick literature search only found clever stuff like bitboards, > pregenerated move tables, incremental hash algorithms, etc. the kind > of stuff you'd expect from a problem domain like chess.
I don't know where you googled, but my sources do not say that bitboards are the *only* possible or reasonable representation: http://chess.verhelst.org/1997/03/10/representations/ http://en.wikipedia.org/wiki/Computer_chess#Board_representations http://www.aihorizon.com/essays/chessai/boardrep.htm http://www.oellermann.com/cftchess/notes/boardrep.html Many programs still use the array representation. For example: http://www.nothingisreal.com/cheops/ http://groups.msn.com/RudolfPosch/technicalprogamdescription1.msnw Even GNU Chess did not use bitboards before version 5. Here is an example in Python: http://www.kolumbus.fi/jyrki.alakuijala/pychess.html I did not say that there aren't more sophisticated and elaborate board representations than linear or two-dimensional arrays. But they are the simplest and most immediate and intuitive solution, and they have indeed been used for a long time in the 8-bit aera. Bitboards may be more performant, particularly if you are directly programming in assembler or C on a 64 bit machine, but not necessarily in Python. But they are also more difficult to handle. Which representation to use also depends on the algorithms you are using. You wouldn't write a performant chess engine in Python anyway. But assume you want to test a particular chess tree pruning algorithm (that does not depend on board representation) and write a prototype for that in Python, later making a performant implementation in assembler. You would not care so much about the effectivity of your board representation in the prototype, but rather about how easy it can be handled. I think it is telling that you have to resort to a debate about bitboards vs. arrays in order to dismiss my simple use case for index() and count() as "unreal". -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
