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).
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.
In the program shown below, the arrangement of o and x is expressed by the 9-digit binary number explained earlier.
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
['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
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
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.
Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha
Recommended Posts