On 2007-02-12, James Stroud <[EMAIL PROTECTED]> wrote: > Paul Rubin wrote: >> "agent-s" <[EMAIL PROTECTED]> writes: >>>Basically I'm programming a board game and I have to use a >>>list of lists to represent the board (a list of 8 lists with 8 >>>elements each). I have to search the adjacent cells for >>>existing pieces and I was wondering how I would go about doing >>>this efficiently. Thanks >> >> You're getting a bunch of Pythonic suggestions which are easy >> to understand though not so efficient. If you're after >> efficiency you might look at a book like Welsh and Baczynskyj >> "Computer Chess II" for some techniques (warning, this is a >> rather old book though) and program in a closer-to-the-metal >> language. One common approach these days is "bit boards". >> Basically you represent the board state as a bunch of 64-bit >> words, one bit per square. So for checking occupancy, you'd >> have a word having the bits set for occupied squares. If you >> only want to check adjacent squares (king moves), you could >> have a bunch of bit masks (one for each square) with bits set >> only for the adjacent squares (similarly for bishop moves, >> rook moves, etc.) Then to check adjacency you'd mask off the >> appropriate bits for that square, then AND it against the >> occupancy word. Normally you'd have separate occupancy words >> for your own pieces and your opponent's. > > In defense of the less efficient suggestions, he did say he had > to use a list of lists. But what you describe is pretty cool.
Precomputing and storing the adjecent indexes for each square would be a possible hybrid solution. In effect every square would contain pointers to all its neighbors. -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list
