Generate list of possible moves Python Tic-Tac-Toe

Question

I am currently working on a project for one of my classes where I have to implement an AI opponent to play tic-tac-toe using minmax and Alpha-Beta minmax algorithms to determine the moves.

The problem I am having however is attempting to generate a list of possible moves for a board.

My problem code is as follows

def genMoves(genBoard, turnNumber):
    moveList = []

    print "inMovesList"
    #Figure out if X or O go now

    if turnNumber % 2 == 0:
        moveChar = "O"
    else:
        moveChar = "X"

    i = 0;

    while i < 9:
        tempBoard = genBoard
        if tempBoard[i] == "*":
            #set tempBoard[i] to X or O
            tempBoard[i] = moveChar
            #append move, new board
            moveList.append((i, tempBoard))

        i+=1

    print "MovesList: "
    print moveList
    return moveList

My board is represented as a list of 9 strings initialized to ["*", "*", "*", "*", "*", "*", "*", "*", "*"].

My goal is to have move list return a list of tuples with the first element of the tuple being i (Where the X or O was inserted) and the second element being the resulting board.

The problem I have is that I will recieve a list with the correct number of possible moves (Eg: If I manually play the first 4 moves for both sides it will only give me 5 possible moves) however it will place the same move in each location that contains a *. (So it ends up generating something like X,O,O,O,O,O,O,O,O for possible second moves)

This is not the first time I have had to use minmax but it is the first time I've had to do it in python.

Any suggestions for how to get around this issue would be helpful!

Thanks!

Answer 1

This line is a problem:

tempBoard = genBoard

After this line, you seem to think that you have two lists -- the original, still referenced by genBoard, and a new one, now referenced by tempBoard. This is not the case.

This line does not create a copy of the list. Instead, it binds the name tempBoard to refer to the same object that genBoard is bound to.

Consequently, subsequent references to tempBoard[i] also affect genBoard[i].

Try one of these instead:

tempBoard = list(genBoard)
tempBoard = genBoard[:]
tempBoard = copy.copy(genBoard)

Each of these lines creates a new list, the initial contents of which is the same as genBoard. tempboard is bound to this new list, while genboard remains bound to the old list.

If the object in question were more complicated than a list of strings, you might need to do this:

tempBoard = copy.deepcopy(genBoard)

Answer 2

I belive Python does not create a copy of your Board but just points to the original version. therefore your printout is:

"MovesList: " [[0,(X,O,O,O,O,O,O,O,O)],[1,(X,O,O,O,O,O,O,O,O)],[2,(X,O,O,O,O,O,O,O,O)], etc.

and your genBoard, variable is changed.

to test that add

print genBoard

directly before the end of your method

if that was indeed the problem try to google how to create a copy of your Board instead of referencing to it.