What modules should I use to create a game tree?
Question: I'm writing a project for a Python coding class and I have a question. I'm
writing a [Reversi](http://en.wikipedia.org/wiki/Reversi) engine that will
look several moves ahead in a game and then pick the move that it thinks is
best. While I understand that python isn't an ideal language for this (because
it's not as fast as some other languages), I think that it's possible to write
code that is at least functional while still maybe being a little slow.

That being said, I am in the process of trying to create two tables: a game
board (think a matrix) and a game tree that will hold integers. I want to use
something memory-efficient and fast to append, delete, and read entries.

The board that I am using right now is not very efficient. I wanted to ask
what modules anyone would suggest (with instructions on how to use them) to
write something that would make an equivalent of this but lighter on memory
(examples: array, numpy; except I don't know how to use either of these):

    
    
    self.board = [[0, 0, 0, 0, 0, 0, 0, 0,],
                  [0, 0, 0, 0, 0, 0, 0, 0,],
                  [0, 0, 0, 0, 0, 0, 0, 0,],
                  [0, 0, 0, 1, 2, 0, 0, 0,],
                  [0, 0, 0, 2, 1, 0, 0, 0,],
                  [0, 0, 0, 0, 0, 0, 0, 0,]
                  [0, 0, 0, 0, 0, 0, 0, 0,],
                  [0, 0, 0, 0, 0, 0, 0, 0,]]
    

For the game tree I have ideas depending on how lightweight a list of lists
should be. An idea that I'm working with written in standard python is similar
to:

    
    
    tree_zero = %
    
    tree_one =  [%, %, %]
    
    tree_two = [[%, %, %], [%, %, %], [%, %, %]]
    
    tree_thre = [[[%, %, %], [%, %, %], [%, %, %]],
                 [[%, %, %], [%, %, %], [%, %, %]],
                 [[%, %, %], [%, %, %], [%, %, %]]],
    
    tree_four = [[[[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]]],
    
                 [[[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]]],
    
                 [[[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]],
                  [[%, %, %], [%, %, %], [%, %, %]]]]
    

Where each % would be one of the boards given above (and is more than ideal:
not every turn has exactly three options). But this is a slow and heavy object
that is difficult for python to use memory-efficiently (especially if I go
deeper than 4-ply).

If anyone has worked with programs like this before or has ideas of efficient
modules to import let me know!

For an example of a game tree, think of the [wikipedia
page](http://en.wikipedia.org/wiki/Game_tree) and especially the first picture
on the page.

EDIT: Ideally, I would like to look further than four moves ahead, this is
just an example of how the first four levels would look. Also, there will be
multiple copies of the given trees floating around for use. Speed is important
for something that grows exponentially like this.


Answer: In my opinion, Python is utterly perfect for this sort of work! That is, I had
a tremendously fun and productive time doing AI for a board game using Python.

My first recommendation is to explore [Bit
Boards](http://www.fzibi.com/cchess/bitboards.htm). Though the application
example here is for chess, the concept is perfectly transferable to Reversi.
Using zeroes and ones to represent the presence of pieces on a set-sized board
not only has the advantage of lower memory footprint, it has the advantage of
increased speed of calculating (bitwise operations are faster than equality
ones).

In addition, you should redesign your model to somehow implement recursion
(facilitated by a scoring function). Such an implementation means you can
write a single function and allow it to scale infinite move depth (or rather,
unlimited by your design, limited only by resources) rather than anticipate
and hard-code the logic for 1,2,3,4 moves. A well-designed function to this
effect works for both sides (players) and can then be halted to choose the
best options that fit within a threshold (halted by any criteria you choose,
positions calculated/real-time spent).

For reference, here is the github for a [board game called
Thud](https://github.com/hexparrot/thudgame) I made with almost exactly the
same requirements as your program. Here, I worked with a 17x17 board, three
different pieces and two different strategies--which we both can see is
already more complex than Reversi's rules.

Oh, and a good recursive model also accommodates multi-threading!

