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.

image.png

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. image.png 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

Recommended Posts

Algorithm learned with Python 14th: Tic-tac-toe (ox problem)
Algorithm learned with Python 9th: Linear search
Algorithm learned with Python 7th: Year conversion
Algorithm learned with Python 8th: Evaluation of algorithm
Algorithm learned with Python 4th: Prime numbers
Algorithm learned with Python 19th: Sorting (heapsort)
Algorithm learned with Python 6th: Leap year
Algorithm learned with Python 12th: Maze search
Algorithm learned with Python 11th: Tree structure
Algorithm learned with Python 13th: Tower of Hanoi
Algorithm learned with Python 16th: Sorting (insertion sort)
Algorithm learned with Python 15th: Sorting (selection sort)
Algorithm learned with Python 17th: Sorting (bubble sort)
Algorithm learned with Python 18th: Sorting (stack and queue)
Algorithm learned with Python 2nd: Vending machine
Algorithm learned with Python 3rd: Radix conversion
Solving the Python knapsack problem with the greedy algorithm
The first algorithm to learn with Python: FizzBuzz problem
The 14th offline real-time writing reference problem with Python
ABC163 C problem with python3
[Python3] Dijkstra's algorithm with 14 lines
ABC188 C problem with python3
ABC187 C problem with python
[Python] Object-oriented programming learned with Pokemon
Perceptron learning experiment learned with Python
Python data structures learned with chemoinformatics
Efficient net pick-up learned with Python
1. Statistics learned with Python 1-1. Basic statistics (Pandas)
Implementation of Dijkstra's algorithm with python
The 16th offline real-time how to write problem was solved with Python
The 16th offline real-time how to write reference problem to solve with Python
[AtCoder] Solve ABC1 ~ 100 A problem with Python
1. Statistics learned with Python 1-3. Calculation of various statistics (statistics)
The 19th offline real-time how to write reference problem to solve with Python
The 15th offline real-time how to write problem was solved with python
Let's develop an investment algorithm with Python 1
I tried it with SymPy Live, Wolfram Alpha and google with reference to "Algorithm learned with Python 4th: Prime numbers".
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
1. Statistics learned with Python 1-2. Calculation of various statistics (Numpy)
The 18th offline real-time writing problem in Python
Use Python and word2vec (learned) with Azure Databricks
1. Statistics learned with Python 2-1. Probability distribution [discrete variable]
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
The 19th offline real-time writing problem in Python
Find the shortest path with the Python Dijkstra's algorithm
"Principle of dependency reversal" learned slowly with Python
FizzBuzz with Python3
Scraping with Python
Python memorandum (algorithm)
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Play with 2016-Python
AES256 with python
Tested with Python
python starts with ()
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
Excel with Python