2
\$\begingroup\$

I made a tic tac toe win checker that represents a 3 x 3 board as a list of list with variables X O B as 'X', 'O' and ' '. However the input can be any valid and invalid board of tic tac toe game. e.g.

board = [[X,X,X],
         [X,X,X],
         [O,O,B]]
board = [[X,O,X],
         [X,O,X],
         [O,O,B]]

I've created a checker that works perfect for ever possible board however it's very inefficient and long. I've tried to simplify it myself with limited succes. Any help making it more compact and effienct would be much appreciated.

#    'X wins''O wins''draw''no winner'
X,O,B = 'X', 'O', ' '
def tictactoe(board):
    N = 'no winner'
    D = 'draw'
    # row operation
    for i in range(0,3): 
        if (board[i][0]==board[i][1]==board[i][2]) and board[i][0] is not B:
            for k in range(0,3):
                if i!=k and (board[k][0]==board[k][1]==board[k][2]) and board[k][0] is not B:
                    if (board[0] == board[1] and not board[2][0]==board[2][1]==board[2][2] and board[2][0] is not B)\
                        or (board[1] == board[2] and not board[0][0]==board[0][1]==board[0][2] and board[0][0] is not B)\
                        or (board[0] == board[2] and not board[1][0]==board[1][1]==board[1][2] and board[1][0] is not B):
                        return(board[i][0]+" wins")
                    return D
            return(board[i][0]+" wins")
    # changes the columns to rows - needed for the column operation    
    boardc = [[board[0][0], board[1][0], board[2][0]],
          [board[0][1], board[1][1], board[2][1]],
          [board[0][2], board[1][2], board[2][2]]]
    # column operation
    for j in range(0,3):
        if (board[0][j]==board[1][j]==board[2][j]) and board[0][j] is not B:
            for l in range(0,3):
                if j!=l and (board[0][l]==board[1][l]==board[2][l]) and board[0][l] is not B: 
                    #does the same as above in the row operation but uses the rotated board
                    if (boardc[0] == boardc[1] and not boardc[2][0]==boardc[2][1]==boardc[2][2] and boardc[2][0] is not B)\
                        or (boardc[1] == boardc[2] and not boardc[0][0]==boardc[0][1]==boardc[0][2] and boardc[0][0] is not B)\
                        or (boardc[0] == boardc[2] and not boardc[1][0]==boardc[1][1]==boardc[1][2] and boardc[1][0] is not B):
                        return(board[0][j]+" wins")
                    return D
            return(board[0][j]+" wins")
    #diagonal winners
    if (board[0][0]==board[1][1]==board[2][2]) and board[0][0] is not B:
        return(board[0][0]+" wins")
    if (board[2][0]==board[1][1]==board[0][2]) and board[2][0] is not B:
        return(board[2][0]+" wins")
    #no winner - if there's no winner yet and there's empty spaces
    for a in range(0,3):
        for b in range(0,3):
            if board[a][b] == B:
                return N
    #where the came has finished and it's a draw 
    else: 
        return D

I tried to simplify the row and column operation that differenciates the double line win from the double line draw using for loops however it came out longer than the current solution.

I'm very new to coding and a friend told me of possible way to do it with arrays. Would this be possible?

\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

The current code is repetitive and difficult to read. You are correct in sensing that your current code is "inefficient". More specifically, it it repetitive (checks for horizontal and vertical wins are similar), verbose (long, complex lines of conditional code), and therefore difficult to read and reason about.

Don't return presentation-oriented strings from algorithmically-oriented functions. Checking for tic-tac-toe wins is an algorithmic process: receive a grid, do a bunch of logic, and return a winner. Rather than returning the ultimate message that you might print for an end-user (e.g., "X wins" or "Draw"), functions like that should generally focus on returning data-centric answers. For example, one natural approach for a win-checking function is to return either the winning player or None. Leave the creation of user-facing messages to a different part of the program.

Transposing a matrix. With those preliminaries out of the way, let's start with your best idea, where you create boardc, which in your words "changes the columns to rows". The more technical term for this operation is transpose, and we could pull that operation out into a separate function. While we're at it, we could do the same for your horizontal-win checking logic:

def transpose(board):
    # Your code moved to a function.
    return [
        [board[0][0], board[1][0], board[2][0]],
        [board[0][1], board[1][1], board[2][1]],
        [board[0][2], board[1][2], board[2][2]],
    ]

def tictactoe_horiz(board):
    # Your code moved to a function.
    for i in range(0,3):
        if (board[i][0]==board[i][1]==board[i][2]) and board[i][0] is not B:
            for k in range(0,3):
                if i!=k and (board[k][0]==board[k][1]==board[k][2]) and board[k][0] is not B:
                    if (board[0] == board[1] and not board[2][0]==board[2][1]==board[2][2] and board[2][0] is not B)\
                        or (board[1] == board[2] and not board[0][0]==board[0][1]==board[0][2] and board[0][0] is not B)\
                        or (board[0] == board[2] and not board[1][0]==board[1][1]==board[1][2] and board[1][0] is not B):
                        return(board[i][0])
                    return None
            return(board[i][0])
    return None

We have made real progress. With those two functions in place, our tic-tac-toe function is much nicer. Also notice how this code is simpler because our row-checking function returns data (winner or None) rather than user-facing messages. That behavior allows us to take advantage of boolean short-circuiting to combine different checks easily.

def tictactoe(board):
    # Checks for horizontal and vertical wins.
    return (
        tictactoe_horiz(board) or
        tictactoe_horiz(transpose(board))
    )

Simplifying row-checking. So far so good, but the row-checking itself is pretty verbose and therefore requires quite careful reading to confirm its correctness. One key problem with your current approach is accessing the matrix value via list indexes rather than taking full advantage of Python's iteration capabilities. More specifically, if you have a matrix, you can iterate over the rows directly, without using list indexes, and the same thing applies to iterating over the cells within a row. For example, one might write the following code to check for a horizontal win. There are certainly more compact ways to do this, but this approach has the virtue of being super easy to understand.

def tictactoe_horiz(board):
    for row in board:
        if all(cell == X for cell in row):
            return X
        if all(cell == O for cell in row):
            return O
    return None

Simplifying diagonal-checking. One way to simplify diagonal checks is to build on the idea behind transpose() and figure out another data transformation that would allow use to reuse the row-checking logic. The details are explained here, but the short version is that the trick is to shift and pad the rows before doing the transposing. But taking that approach requires further adjustments: for example, we need to filter out the pad values before applying the row-checking function; and our transposing function would need to be generalized rather than using hard-coded indexes. A simpler approach that sticks closer to your current code is just to move the diagonal checks to their own function:

def tictactoe_diag(board):
    # Your code moved to a function.
    if (board[0][0]==board[1][1]==board[2][2]) and board[0][0] is not B:
        return board[0][0]
    if (board[2][0]==board[1][1]==board[0][2]) and board[2][0] is not B:
        return board[2][0]
    return None

def tictactoe(board):
    # Now checks for all types of wins.
    return (
        tictactoe_horiz(board) or
        tictactoe_horiz(transpose(board)) or
        tictactoe_diag(board)
    )

In partial defense of hard-coding: an alternative. As you know, your current code takes a very hard-coded approach to the board indexes. Much of your logic is devoted to examining specific cells in the matrix, via their indexes. What would happen if we fully embraced hard-coded indexes -- but in a more purposeful way by putting the hard-coded values in a data structure? The outcome is quite nice. We define a single constant, the checking logic is simple, and we write very little algorithmic code:

X, O, B = ('X', 'O', ' ')

WINNERS = (
    [(0, 0), (0, 1), (0, 2)], # Horizontal
    [(1, 0), (1, 1), (1, 2)],
    [(2, 0), (2, 1), (2, 2)],
    [(0, 0), (1, 0), (2, 0)], # Vertical
    [(0, 1), (1, 1), (2, 1)],
    [(0, 2), (1, 2), (2, 2)],
    [(0, 0), (1, 1), (2, 2)], # Diagonal
    [(0, 2), (1, 1), (2, 0)],
)

def tictactoe_alt(board):
    for indexes in WINNERS:
        row = [board[r][c] for r, c in indexes]
        if all(cell == X for cell in row):
            return X
        if all(cell == O for cell in row):
            return O
    return None
\$\endgroup\$
1
\$\begingroup\$

I think you’re over thinking the problem. This is tic-tac-toe after all.

All you need is one of the following: A list of 9 items or if you want to use half the memory 66 bytes instead of 128 on my machine with python 3.96. You could use just a string and treat it like a list. I will use a list but you can easily replace it with a string like:

    Board “ “*9 

If you don’t know that format that makes a string of length 9 and all spaces. I am going to do the same thing with a list here:

    Board=[‘ ‘]*9

If I was going to write the game fully though I would do it with a bitmap to store everything including player, state of board, and both X and O positions. That could all be stored in one of python’s integers because python uses 24 bits on my machine to store an integer. You only need 16 bits to store board state and one bit to store turn and maybe 1 bit to denote whether the game is running or not. You could totally get rid of the lists and strings and just do this with one integer. Then it would only be One loop and 8 tests and you know if you have a winner and who it is, win, loose or draw. If you search online I am sure you can find someone to show you how to do that.

Let’s do this the easiest way with a python list though. You can modify this to work with your list of lists but that is more complicated than this.

I have created a display_board function to show the board. Then I have created the check_board function. You will notice I don’t use all the transforming and just use list slicing and comparison. For example something like this:

    Board[‘X’,’ ‘,’ ‘,’ ‘,’X’,’ ‘,’ ‘,’ ‘,’X’]

Is a winning down slope in tic tac toe. To test this you can simply do:

    Board[::4]==[‘X’]*3

Will return true so you can do slices to test just against another array which I made with [‘X’]*3.

First I wanted to be able to look at the board so I made a board display function first. Even though I am sure it could be made with loops it is a simple function so I wrote it without and added it to the post since I made it with the checker.

Second I created the check_winner function with all four checks. As the comment says it returns ‘X’, ‘O’ if either win, it returns ‘ ‘ if there are still moves, and finally 0 if a draw, and The entire function without comments is 11 lines of code.

I followed that up with tests for all possibilities to make sure my function worked and that is also below. You can block and copy this into a source file and run it.

    #tic-tac example
    # create blank board
    board = [" "] * 9
    
    
    def display_board():
        """this function displays a board define in a single list"""
        temp_board = board[:]
        for i in range(len(temp_board)):
            if temp_board[i] == " ":
                temp_board[i] = i + 1
        print(f"{temp_board[0]} | {temp_board[1]} | {temp_board[2]}")
        print(f"--|---|--")
        print(f"{temp_board[3]} | {temp_board[4]} | {temp_board[5]}")
        print(f"--|---|--")
        print(f"{temp_board[6]} | {temp_board[7]} | {temp_board[8]}")
    
    
    def check_winner():
        """checks for a winner
        *  returns
          'X' for X wins
          *  'O' for O wins
          *  ' '  for no winner yet
          * 0 for draw
        """
        # first row check
        for i in range(0, 9, 3):
            if board[i : i + 3] == ["X"] * 3 or board[i : i + 3] == ["O"] * 3:
                return board[i]
    
        # now column check
        for i in range(3):
            if board[i::3] == ["X"] * 3 or board[i::3] == ["O"] * 3:
                return board[i]
    
        # now test         down slope
        if board[0::4] == ["X"] * 3 or board[0::4] == ["O"] * 3:
            return board[0]
    
        # now test up slope
        if board[2:7:2] == ["X"] * 3 or board[2:7:2] == ["O"] * 3:
            return board[2]
    
        # now test if there are more moves possible.
        if " " in board:
            return " "
    
        # now return a draw
        return 0
    
    
    # X win tests
    board = ["X", "X", "X", " ", " ", " ", " ", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", " ", "X", "X", "X", " ", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", " ", " ", " ", " ", "X", "X", "X"]
    print(f"{check_winner()} is the winner.")
    board = ["X", " ", " ", "X", " ", " ", "X", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", "X", " ", " ", "X", " ", " ", "X", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", "X", " ", " ", "X", " ", " ", "X"]
    print(f"{check_winner()} is the winner.")
    board = ["X", " ", " ", " ", "X", " ", " ", " ", "X"]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", "X", " ", "X", " ", "X", " ", " "]
    print(f"{check_winner()} is the winner.")
    
    
    # tests 'O' wins
    board = ["O", "O", "O", " ", " ", " ", " ", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", " ", "O", "O", "O", " ", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", " ", " ", " ", " ", "O", "O", "O"]
    print(f"{check_winner()} is the winner.")
    board = ["O", " ", " ", "O", " ", " ", "O", " ", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", "O", " ", " ", "O", " ", " ", "O", " "]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", "O", " ", " ", "O", " ", " ", "O"]
    print(f"{check_winner()} is the winner.")
    board = ["O", " ", " ", " ", "O", " ", " ", " ", "O"]
    print(f"{check_winner()} is the winner.")
    board = [" ", " ", "O", " ", "O", " ", "O", " ", " "]
    print(f"{check_winner()} is the winner.")
    # test draw
    board = ["X", "O", "X", "O", "X", "O", "O", "X", "O"]
    print(f"{check_winner()} is a draw")
    
    # test still moves to go
    board = [" ", "O", "X", "O", "X", "O", "O", "X", "O"]
    print(f"{check_winner()} is still more spaces")

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer. \$\endgroup\$ Nov 24, 2022 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.