# [Tutor] tic tac toe data structure

Robin B. Lake rbl@hal.cwru.edu
Sun, 4 Jun 2000 09:59:44 -0400 (EDT)

```Good solution.  What struck me as a possible structure was a list
of all possible winning lines (some tic-tac-toe games allow 4 corners
as a winning "line").  I think the Python expression of a strategy
may be easier with that "line" perspective.

FWIW,
Rob Lake
rbl@hal.cwru.edu

> From tutor-admin@python.org Sun Jun  4 05:46:24 2000
> Delivered-To: tutor@python.org
> To: tutor@python.org
> Subject: Re: [Tutor] tic tac toe data structure
> Mime-Version: 1.0
> X-BeenThere: tutor@python.org
> X-Mailman-Version: 2.0beta3
> List-Id: Discussion for learning programming with Python <tutor.python.org>
>
> 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
>
> _______________________________________________
> Tutor maillist  -  Tutor@python.org
> http://www.python.org/mailman/listinfo/tutor
>

```