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

Python lists are good objects if all you want is random access to one of its items and lists of lists. You could create a tree object yourself that allows you to retrieve a leaf node or a subtree in a more readable form. A module is a file containing Python definitions and declarations. The module is Python code that can be called from other programs for commonly used tasks, without having to type them in every program that uses them.

Let us discuss this with an example when you call “matplotlib.plot”, you are calling a package module. If you are not having this module you would have to define the plot functionality in every program that used a plot graph.

Bit Boards application is a perfect example based on 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 the lower memory footprint, but it also has the advantage of increased speed of calculating (bitwise operations are faster than equality ones).