I'm working on programming a go-player. I hope to make use of variable-sized bitmaps, as for example:
a bitmap showing 1's for black stones here, 0's if not, shifted up one row--'and'ed with another showing 1's for white stones, shifted left one column
would show 1's for all points with a black stone below and a white stone to the right.
This has the potential of generating maps showing very complex properties--and could be quite fast in C, but my attempts to use it have gotten very long & buggy.
Python is a lot more conceptionally straightforward, but likely to be slower.... so I was wondering about using python L integers as bitmaps. Instead of worrying about where one 19 bit row fits into an array of 32 bit integers, I could just code a row as 0xffffe (20 bits, one extra to mark the topological gap between the rightmost bit here and the leftmost in the next row...)
but then, if I left shift this 20 * n bits to slide it into the nth row up, what happens when I 'or' it with an (n-1)*20 bit map?
I imagine the 'or' operation could be performed in a way that ignores whole 32-bit chunks of 0's-- or I could imagine it being done using the whole 19 rows. That version would make changing a bit in the 20 * j + kth bit (adding one stone to the board, for example) a major operation, not so good! Or picking out one row, let alonge reading one particular bit, same problem.
So am I going to have to work this using arrays of 32-bit integers? (Faster, but it would be nice to avoid those complications!)
Me again. Lacking the know-how to find the address of individual chunks of a python long... last night I set to implementing go bitmaps with four integers and a list.
Wasteful, but amazingly easy to code! Four numbers for the upper left corner coordinates, height, & width, plus a list of 'height' integers representing the actual map.
Rather than shifting entries or moving them up or down, most of the time, I can just move the starting corner. I don't need to do the actual and's, or', xor's etc unless two maps are actually overlapping on the board; the result of any interaction is a <= size map for the area where they actually overlap-- or is simply 'False' if they don't. Such a nice language for an old spaghetti-era geezer! It probably isn't doing as much as fast as my old c version, but what it's doing has got to be smarter!
(I would still like to know if anyone knows a good way to simply manipulate individual 32 bit chunks of python longs.)
Previous Topic
