[Tutor] tic tac toe data structure

[Remco Gerlich]

On Sat, Jun 03, 2000 at 10:46:55PM -0500, Timothy Wilson wrote:
> The frequency of my posts to the list lately is directly proportional to my
> enthusiasm with learning Python! I'm really looking forward to this summer
> when I'll have some real concentrated time to learn. It's going to be lots
> of Python and Zope for me until the kids come back to school in Sept.
> 
> Anyway, I was talking with a couple of our AP C++ students the other day,
> and they showed me the tic tac toe program they'd written. I immediately
> thought that it would be a fun little program to write in Python. I've been
> pondering a bit and wonder if anyone could offer a couple suggestions.
> 
> 1. The tic tac toe "board" is a 3x3 matrix. What would be the best data
> structure for representing the board? I know that NumPy (I think that's the
> name) does matrices, but that seems like overkill. Would a list of lists
> work?
> 
> e.g.,  board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Probably. I played a bit with chess things recently and I just use one list
with length 64. That's a bit easier to index, and a square index is just one
index instead of a tuple (I have a module squares.py that basically does 
a1 = 0, b1 = 1, c1 = 2, a2 = 8 etc so I can use position.get_square(a3) and
so on).

But it doesn't really matter, tic tac toe is easy, just use what you think
is the cleanest way to do it :)

> 2. I have yet to fully wrap my brain around OOP. Would this be a good chance
> to attempt an OO approach?

Yes. Make a Position class, legal_moves() methods and so on. I overdid it a
bit with chess - Move was also a class, instead of using simple tuples for
moves. That meant that it was somewhat slow, it needs to instantiate thousands
of Moves quickly. I need to get back to it someday.

> 3. Is there an accepted method of handling game-type logic? I've never
> programmed a game before. What's the best way to organize the computer's
> playing strategy?

It's called "minimax searching" on a tree of legal moves. There's an
optimization on it called "alpha beta pruning". If you do a search on Google
for those terms I bet you'll find a lot of information.

-- 
Remco Gerlich,  scarblac@pino.selwerd.nl