Algorithm learned with Python 14th: Tic-tac-toe (ox problem)

#Algorithm learned in Python <Tic-tac-toe (ox problem)>

Introduction

Implement the basic algorithm in Python to deepen your understanding of the algorithm. As the 14th bullet, we deal with tic-tac-toe (ox problem).

Tic-tac-toe (ox problem)

The victory condition is to place o and x alternately in the $ 3 \ times3 $ square and arrange them vertically, horizontally, or diagonally first. When executing to a program, it must be treated as a numerical value. First, consider each cell as follows.

It is expressed as a 9-digit binary number in the order of A to I. As an example, the following figure shows the array when o satisfies the victory condition and the binary number corresponding to them. As mentioned above, there are eight winning conditions for $ 3 \ times3 $.

If all the squares are filled before the victory condition is met, it will be a draw. With these victory conditions and draws as the end conditions, o and x are repeatedly placed alternately. This time, we consider that computers compete according to random numbers. Next, the implementation code and the output at that time are shown. We also tried visualization.

Implementation

In the program shown below, the arrangement of o and x is expressed by the 9-digit binary number explained earlier.

code

tick_tac_toe1.py

"""
2021/01/02
@Yuya Shimizu

Tic-tac-toe
"""
import random

#Victory conditions
#Upper 3 columns, middle 3 columns, lower 3 columns, left end 3 rows, center 3 rows, right end 3 rows, lower right diagonal, upper right diagonal
finish = [
                0b111000000, 0b000111000, 0b000000111, 0b100100100,
                0b010010010, 0b001001001, 0b100010001, 0b001010100
            ]

#Victory judgment
def check(player):
    for mask in finish:
        if player == mask:
            return  True
    return False

#Put o and x alternately
def play(player1, player2):
    if check(player2):
        print([bin(player1), bin(player2)])
        return  #End

    board = player1 | player2

    if board == 0b111111111:    #If all the squares are filled, end with a draw
        print([bin(player1), bin(player2)])
        return  #End

    #Find a place to put it
    putable = [i for i in range(9) if (board & (1 << i)) == 0]
    #Try to put it randomly
    r = random.choice(putable)
    
    play(player2, player1 | (1 << r))   #Recursion

if __name__ == '__main__':
    play(0,0)   #Give the initial situation;Still, the situation where neither player has placed either

output

['0b110001010', '0b1110101']

Next, the program code and output that visualize the status of the board are shown.

tick_tac_toe1_1.py

"""
2021/01/02
@Yuya Shimizu

Tic-tac-toe (visualization)
"""
import random

#Victory conditions
#Upper 3 columns, middle 3 columns, lower 3 columns, left end 3 rows, center 3 rows, right end 3 rows, lower right diagonal, upper right diagonal
finish = [
                0b111000000, 0b000111000, 0b000000111, 0b100100100,
                0b010010010, 0b001001001, 0b100010001, 0b001010100
            ]

#Game board initialization'* 'Represents a blank
Board = {
        'turn':'turn : 1 \n\n',
        1:'* ', 2:'* ', 3:'* ', 'z1':'\n',
        4:'* ', 5:'* ', 6:'* ', 'z2':'\n',
        7:'* ', 8:'* ', 9:'* '
        }

#Visualization function
def draw(player1, player2, turn):
    show_board = "" #output data(letter)Initialize the variable that stores

    #turn(Odd)Is player1, turn(Even)Is player2
    #0 turn only start
    if turn % 2 == 1 and turn != 0:
        Board['turn'] = f"\n\nturn : {turn}  (player1) \n"
        #Board 1 is player2, board 2 is player1(This is because the argument player changes every turn.)  
        board1 = str(bin(player2))[2:]
        board2 = str(bin(player1))[2:]
    elif turn % 2 == 0 and turn != 0:
        Board['turn'] = f"\n\nturn : {turn}  (player2) \n"
        #Board 1 is player1, board 2 is player2(This is because the argument player changes every turn.)  
        board1 = str(bin(player1))[2:]
        board2 = str(bin(player2))[2:]
    else:
        Board['turn'] = f"\n\nstart \n"
        #The board is suitable. I'm just trying not to give an error. There is no other meaning
        board1 = str(bin(player1))[2:]
        board2 = str(bin(player2))[2:]
        
    #player1(o)Reflected on the game board
    for i in range(1, len(board1)+1):
        if  board1[-i] == '1' and Board[10-i] == '* ':
            Board[10-i] = 'o '
    #player2(x)Reflected on the game board
    for i in range(1, len(board2)+1):
        if board2[-i] == '1' and Board[10-i] == '* ':
            Board[10-i] = 'x '

    #Generate character array for updated game board visualization
    for i in Board:
        show_board += Board[i]

    #Visualization
    print(show_board)

#Victory judgment
def check(player):
    for mask in finish:
        if player & mask == mask:
            return  True
    return False

#Put o and x alternately
def play(player1, player2, turn = 0):
    result = draw(player1, player2, turn)   #Visualize the situation every turn

    #Victory judgment
    if check(player2):
        #turn(Odd)Player1 wins when finished with
        if turn % 2 == 1:
            print(f"player1 WIN")
            return  #End
        
        #turn(Even)Player2 wins when finished with
        else:
            print(f"player2 WIN")
            return  #End

    board = player1 | player2       #o,Generate board status with x placed
    if board == 0b111111111:    #If all the squares are filled, end with a draw
        print(f"DRAW")
        return  #End
    
    #Find a place to put it
    putable = [i for i in range(9) if (board & (1 << i)) == 0]
    #Try to put it randomly
    r = random.choice(putable)
    
    turn += 1   #Add turn
    
    play(player2, player1 | (1 << r), turn = turn)  #Recursion(Repeat turns) 

if __name__ == '__main__':
    play(0,0)   #Give the initial situation;Still, the situation where neither player has placed either

output

start 
* * * 
* * * 
* * * 


turn : 1  (player1) 
* * * 
* * o 
* * * 


turn : 2  (player2) 
* * x 
* * o 
* * * 


turn : 3  (player1) 
* * x 
* * o 
* o * 


turn : 4  (player2) 
* * x 
* x o 
* o * 


turn : 5  (player1) 
* o x 
* x o 
* o * 


turn : 6  (player2) 
* o x 
x x o 
* o * 


turn : 7  (player1) 
* o x 
x x o 
* o o 


turn : 8  (player2) 
* o x 
x x o 
x o o 
player2 WIN

Impressions

There is also a knapsack problem that I will share at a later date, but I feel that I have become accustomed to expressing a certain situation using binary numbers. Also, I'm getting used to recursion a little, and when I return something with return, it becomes None, and I need to use print to display it. I also found out. This time, I also tried visualization. Visualization has been a little difficult. The factor was that the arguments were swapped during recursion. Therefore, at first, it was only o, or it was not displayed well. In addition, when visualizing the board, the correspondence between the player's placement conditions and the board placement was reversed, so in the for statement, from the end such as -i and 10-i. It was necessary to perform an array operation with or difference. I managed to visualize it on my own. I think it's going to be a little more organized, but I think I've learned about the tic-tac-toe algorithm and its implementation.

References

Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha