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

[agent-s]

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

[Neil Cerutti]

On 2007-02-12, James Stroud <js*****@mbi.uc la.eduwrote:

Paul Rubin wrote:

>"agent-s" <sh*******@gmai l.comwrites:

>>>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

[Hendrik van Rooyen]

"John Machin" <sj******@lexic on.netwrote:

Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
of 6 deadly sins :-)

Thou shallt not bit - bash

What are the other five?

- Hendrik

[John Machin]

On Feb 13, 4:57 pm, "Hendrik van Rooyen" <m...@microcorp .co.zawrote:

"John Machin" <sjmac...@lexic on.netwrote:

Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
of 6 deadly sins :-)

Thou shallt not bit - bash

What are the other five?

"""
.... regexes have their place, together with pointer arithmetic, bit
manipulations, reverse polish notation and goto. The problem is when
people use them inappropriately ...
"""

The sixth is never mentioned. Aliter: I can't count. Believe whichever
hypothesis you like :-)

[Hendrik van Rooyen]

"John Machin" <sjmac...@lexic on.netwrote:

On Feb 13, 4:57 pm, "Hendrik van Rooyen" <m...@microcorp .co.zawrote:

"John Machin" <sjmac...@lexic on.netwrote:

Now for the algorithm: all of that testing to see if you are about to
sail off the end of the world is a bit ugly and slow. You can use bit-
bashing, as Paul suggested, even though it's on Steven D'Aprano's list
of 6 deadly sins :-)

Thou shallt not bit - bash

What are the other five?

"""
... regexes have their place, together with pointer arithmetic, bit
manipulations, reverse polish notation and goto. The problem is when
people use them inappropriately ...
"""

I find this unsatisfactory - I was hoping for a five commandment
style of thing, setting out proper prohibitions against evil stuff.

It seems that I am a closet fundamentalist.

A sixth, btw is:

Thou shallt not use globals.

- Hendrik

[agent-s]

Thanks for the help guys but I'm a newbie at this and from what I
understand from the code, it looks like you guys are using a two
dimensional array. I am not using a two dimensional array. Basically,
it looks like this:

[
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' '],
[' ',' ',' ',' ',' ',' ',' ',' ']
]

above: a list of lists NOT a two-dimensional array

[agent-s]

OK I just realized that a list of lists can be accessed in the same
way a 2d array would be accessed. Thanks anyways guys.

[Gerard Flanagan]

On Feb 12, 1:27 am, "agent-s" <shanek...@gmai l.comwrote:

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

def iter_grid(cols) :
i=0
while True:
yield divmod(i,cols)
i += 1

def iter_adjacents( row, col):
gen = iter_grid(3)
for i in range(9):
x, y = gen.next()
if x == 1 and y ==1:
continue
else:
yield row - x + 1, col - y + 1

def make_grid_dict( rows, cols):
return dict( zip(iter_grid(c ols), ['#'] * (rows*cols)) )

def make_adjacent_l ist(row, col, row_length, col_length):
ret = []
for x, y in iter_adjacents( row, col):
if x -1 and y -1 and x < row_length and y < col_length:
ret.append((x,y ))
return ret

grid = make_grid_dict( 8, 8)
adjacents = dict(grid)
for x,y in sorted(adjacent s.keys()):
adjacents[x,y] = make_adjacent_l ist(x, y, 8, 8)
print '(%s, %s) - %s ' % (x, y, adjacents[x,y]
(0, 0) - [(1, 1), (1, 0), (0, 1)]
(0, 1) - [(1, 2), (1, 1), (1, 0), (0, 2), (0, 0)]
(0, 2) - [(1, 3), (1, 2), (1, 1), (0, 3), (0, 1)]
(0, 3) - [(1, 4), (1, 3), (1, 2), (0, 4), (0, 2)]
(0, 4) - [(1, 5), (1, 4), (1, 3), (0, 5), (0, 3)]
(0, 5) - [(1, 6), (1, 5), (1, 4), (0, 6), (0, 4)]
(0, 6) - [(1, 7), (1, 6), (1, 5), (0, 7), (0, 5)]
(0, 7) - [(1, 7), (1, 6), (0, 6)]
(1, 0) - [(2, 1), (2, 0), (1, 1), (0, 1), (0, 0)]
(1, 1) - [(2, 2), (2, 1), (2, 0), (1, 2), (1, 0), (0, 2), (0, 1), (0,
0)]
(1, 2) - [(2, 3), (2, 2), (2, 1), (1, 3), (1, 1), (0, 3), (0, 2), (0,
1)]
(1, 3) - [(2, 4), (2, 3), (2, 2), (1, 4), (1, 2), (0, 4), (0, 3), (0,
2)]
(1, 4) - [(2, 5), (2, 4), (2, 3), (1, 5), (1, 3), (0, 5), (0, 4), (0,
3)]
(1, 5) - [(2, 6), (2, 5), (2, 4), (1, 6), (1, 4), (0, 6), (0, 5), (0,
4)]
(1, 6) - [(2, 7), (2, 6), (2, 5), (1, 7), (1, 5), (0, 7), (0, 6), (0,
5)]
(1, 7) - [(2, 7), (2, 6), (1, 6), (0, 7), (0, 6)]
(2, 0) - [(3, 1), (3, 0), (2, 1), (1, 1), (1, 0)]
(2, 1) - [(3, 2), (3, 1), (3, 0), (2, 2), (2, 0), (1, 2), (1, 1), (1,
0)]
(2, 2) - [(3, 3), (3, 2), (3, 1), (2, 3), (2, 1), (1, 3), (1, 2), (1,
1)]
(2, 3) - [(3, 4), (3, 3), (3, 2), (2, 4), (2, 2), (1, 4), (1, 3), (1,
2)]
(2, 4) - [(3, 5), (3, 4), (3, 3), (2, 5), (2, 3), (1, 5), (1, 4), (1,
3)]
(2, 5) - [(3, 6), (3, 5), (3, 4), (2, 6), (2, 4), (1, 6), (1, 5), (1,
4)]
(2, 6) - [(3, 7), (3, 6), (3, 5), (2, 7), (2, 5), (1, 7), (1, 6), (1,
5)]
(2, 7) - [(3, 7), (3, 6), (2, 6), (1, 7), (1, 6)]
(3, 0) - [(4, 1), (4, 0), (3, 1), (2, 1), (2, 0)]
(3, 1) - [(4, 2), (4, 1), (4, 0), (3, 2), (3, 0), (2, 2), (2, 1), (2,
0)]
(3, 2) - [(4, 3), (4, 2), (4, 1), (3, 3), (3, 1), (2, 3), (2, 2), (2,
1)]
(3, 3) - [(4, 4), (4, 3), (4, 2), (3, 4), (3, 2), (2, 4), (2, 3), (2,
2)]
(3, 4) - [(4, 5), (4, 4), (4, 3), (3, 5), (3, 3), (2, 5), (2, 4), (2,
3)]
(3, 5) - [(4, 6), (4, 5), (4, 4), (3, 6), (3, 4), (2, 6), (2, 5), (2,
4)]
(3, 6) - [(4, 7), (4, 6), (4, 5), (3, 7), (3, 5), (2, 7), (2, 6), (2,
5)]
(3, 7) - [(4, 7), (4, 6), (3, 6), (2, 7), (2, 6)]
(4, 0) - [(5, 1), (5, 0), (4, 1), (3, 1), (3, 0)]
(4, 1) - [(5, 2), (5, 1), (5, 0), (4, 2), (4, 0), (3, 2), (3, 1), (3,
0)]
(4, 2) - [(5, 3), (5, 2), (5, 1), (4, 3), (4, 1), (3, 3), (3, 2), (3,
1)]
(4, 3) - [(5, 4), (5, 3), (5, 2), (4, 4), (4, 2), (3, 4), (3, 3), (3,
2)]
(4, 4) - [(5, 5), (5, 4), (5, 3), (4, 5), (4, 3), (3, 5), (3, 4), (3,
3)]
(4, 5) - [(5, 6), (5, 5), (5, 4), (4, 6), (4, 4), (3, 6), (3, 5), (3,
4)]
(4, 6) - [(5, 7), (5, 6), (5, 5), (4, 7), (4, 5), (3, 7), (3, 6), (3,
5)]
(4, 7) - [(5, 7), (5, 6), (4, 6), (3, 7), (3, 6)]
(5, 0) - [(6, 1), (6, 0), (5, 1), (4, 1), (4, 0)]
(5, 1) - [(6, 2), (6, 1), (6, 0), (5, 2), (5, 0), (4, 2), (4, 1), (4,
0)]
(5, 2) - [(6, 3), (6, 2), (6, 1), (5, 3), (5, 1), (4, 3), (4, 2), (4,
1)]
(5, 3) - [(6, 4), (6, 3), (6, 2), (5, 4), (5, 2), (4, 4), (4, 3), (4,
2)]
(5, 4) - [(6, 5), (6, 4), (6, 3), (5, 5), (5, 3), (4, 5), (4, 4), (4,
3)]
(5, 5) - [(6, 6), (6, 5), (6, 4), (5, 6), (5, 4), (4, 6), (4, 5), (4,
4)]
(5, 6) - [(6, 7), (6, 6), (6, 5), (5, 7), (5, 5), (4, 7), (4, 6), (4,
5)]
(5, 7) - [(6, 7), (6, 6), (5, 6), (4, 7), (4, 6)]
(6, 0) - [(7, 1), (7, 0), (6, 1), (5, 1), (5, 0)]
(6, 1) - [(7, 2), (7, 1), (7, 0), (6, 2), (6, 0), (5, 2), (5, 1), (5,
0)]
(6, 2) - [(7, 3), (7, 2), (7, 1), (6, 3), (6, 1), (5, 3), (5, 2), (5,
1)]
(6, 3) - [(7, 4), (7, 3), (7, 2), (6, 4), (6, 2), (5, 4), (5, 3), (5,
2)]
(6, 4) - [(7, 5), (7, 4), (7, 3), (6, 5), (6, 3), (5, 5), (5, 4), (5,
3)]
(6, 5) - [(7, 6), (7, 5), (7, 4), (6, 6), (6, 4), (5, 6), (5, 5), (5,
4)]
(6, 6) - [(7, 7), (7, 6), (7, 5), (6, 7), (6, 5), (5, 7), (5, 6), (5,
5)]
(6, 7) - [(7, 7), (7, 6), (6, 6), (5, 7), (5, 6)]
(7, 0) - [(7, 1), (6, 1), (6, 0)]
(7, 1) - [(7, 2), (7, 0), (6, 2), (6, 1), (6, 0)]
(7, 2) - [(7, 3), (7, 1), (6, 3), (6, 2), (6, 1)]
(7, 3) - [(7, 4), (7, 2), (6, 4), (6, 3), (6, 2)]
(7, 4) - [(7, 5), (7, 3), (6, 5), (6, 4), (6, 3)]
(7, 5) - [(7, 6), (7, 4), (6, 6), (6, 5), (6, 4)]
(7, 6) - [(7, 7), (7, 5), (6, 7), (6, 6), (6, 5)]
(7, 7) - [(7, 6), (6, 7), (6, 6)]