searching a list of lists as a two-dimensional array?

[Neil Cerutti]

On 2007-02-12, James Stroud <jstroud at mbi.ucla.edu> wrote:
> Paul Rubin wrote:
>> "agent-s" <shanekwon at gmail.com> 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