Posts: 51
Threads: 6
Joined: Dec 2022
Mar-28-2023, 10:42 AM
(This post was last modified: Mar-28-2023, 10:42 AM by freethrownucleus.)
Okay, great, but what if I want, let's say, to combine 3 or 4 in a row for a win?
3 in a row on one board or 4 in a row on combining 2 or more boards?
That's why I had an idea to write all the combos by hand (the code that I sent, your old code version).
Furthermore, I want all these squares to have same width and height, not to look like rectangles. I tried to add new variable "height" to constructor but there's obivously no height option in entry. Is it fixable with the grid somehow?
Posts: 6,823
Threads: 20
Joined: Feb 2020
Posts: 51
Threads: 6
Joined: Dec 2022
How exactly should I use images? Because if you see the start of this thread, I tried to load images for boards and it didn't go well ...
Posts: 6,823
Threads: 20
Joined: Feb 2020
Mar-28-2023, 09:12 PM
(This post was last modified: Mar-28-2023, 09:12 PM by deanhystad.)
Did you look at all for how to use images in tkinter? You can put images in buttons and other tkinter widgets. When the button only contains an image, the default size of the button is set by the size of the image. To use images, Square would set the button image instead of the button text. Since the "X" and "O" images have their own color, you don't have to change the button color. Actually makes the program easier to write if you use images. I don't use images in my example because I want to post runnable code. You cannot run code that uses images unless you have the image files or make your own.
Using images, the Square looks like this:
class Square(tk.Button):
"""Special button for playing tic-tac-toe."""
def __init__(self, parent, index):
super().__init__(parent, image=images[None])
self.index = index
self._mark = None
@property
def mark(self):
"""What marker appears in square."""
return self._mark
@mark.setter
def mark(self, mark):
self._mark = mark
self["image"] = images[mark]This maks a dictionary mapping 'X', 'O', None to images
images = {}
class TicTacToe(tk.Tk):
"""A funky TicTacToe game. Use map to make any shape board you want."""
def __init__(self, map_):
super().__init__()
# Define images used by squares.
image_dir = Path(__file__).parent
images["X"] = tk.PhotoImage(file=image_dir / "x.png")
images["O"] = tk.PhotoImage(file=image_dir / "o.png")
images[None] = tk.PhotoImage(file=image_dir / "empty.png")
self.title("Tic Tac Toe")
self.player = "X"
...Since you cannot (easily) change the color of the mark images, I modified the code to highlight the winner by changing the Square background color.
Now that you've seen how to make a tic-tac-toe board in tkinter you should have a good idea how you could do the same thing in pygame. You would have an X image and an O image. You would make a sprite for each square. On a mouse click you would check if the click was in any of the squares. If you clicked on a square you would play that square. When playing the square you would change the image of the Square/sprite to show the appropriate image. A lot of the code could be structured exactly the same as it is in tkinter. The main difference is pygame sprites don't have a click callback.
Posts: 51
Threads: 6
Joined: Dec 2022
Posts: 51
Threads: 6
Joined: Dec 2022
Apr-27-2023, 10:51 PM
(This post was last modified: Apr-27-2023, 10:52 PM by freethrownucleus.)
I want to change this 2-player game into a game against computer. I tried to implement this minimax algorithm that's in the first class in my code but I can't make it work. I tried a couple of options but I can't handle it.
I would appreciate some help!
Here's the old code version without my silly tries (XD) and class Robot with the minimax function that I'm trying to implement and adapt in the beginning of the code:
import tkinter as tk
#TRYING TO IMPLEMENT CLASS ROBOT
#START
class Robot:
def __init__(self, cube):
self.boards = cube.boards
def get_scores(self, board):
"""Get scores for all open squares on a board"""
def minimax(mark, square, alpha=-1000, beta=1000, depth=0):
"""minimax algorithm with alpha/beta pruning"""
# Place the mark and check for a win
square.mark = mark
if square.check_win():
# Give extra weight to earlier wins/losses
score = 10 - depth if mark is ROBOT else depth - 10
board.depth = min(board.depth, depth)
elif len(empty_squares := board.empty_squares()) == 0:
# No plays left. Draw.
score = 0
elif mark is PLAYER:
# Pick best move for robot
score = -1000
for s in empty_squares:
score = max(score, minimax(ROBOT, s, alpha, beta, depth+1))
alpha = max(alpha, score)
if alpha > beta:
break
else:
# Guess what move player will make
score = 1000
for s in empty_squares:
score = min(score, minimax(PLAYER, s, alpha, beta, depth+1))
beta = min(beta, score)
if alpha > beta:
break
# Remove mark and return score for the square
square.mark = EMPTY
return score
# Collect scores for empty squares. If board is empty,
# minimax will return 0 for all squares
board.depth = 10
empty_squares = board.empty_squares()
if len(empty_squares) == 9:
board.scores = [[0, s] for s in empty_squares]
else:
# Calling minimax twice. The first is to find the square
# giving us best chance to win board. Second is to prevent
# abandoning board early and giving player an easy win.
board.scores = [[minimax("O", s), s] for s in empty_squares]
[minimax("X", s, depth=1) for s in empty_squares]
def play(self):
"""Place robot mark."""
# Get scores for all empty squares
depth = 10
for board in self.boards:
self.get_scores(board)
depth = min(depth, board.depth)
# Select board with minimum depth. This is the board that
# will win/lose in the least number of moves.
scores = []
for board in self.boards:
if board.depth <= depth:
scores.extend(board.scores)
# Randomly select from best scores on the selected board.
max_score = max(score[0] for score in scores)
squares = [score[1] for score in scores if score[0] >= max_score]
return random.choice(squares)
#END
class Square(tk.Button):
"""Special button for playing tic-tac-toe."""
colors = {"O": "blue", "X": "red"}
def __init__(self, parent, index):
super().__init__(parent, width=3, font=('Comic Sans MS', 20, 'bold'))
self.index = index
self._mark = None
@property
def mark(self):
"""What marker appears in square."""
return self._mark
@mark.setter
def mark(self, mark):
self._mark = mark
self["fg"] = self.colors.get(mark, 'black')
self["text"] = '' if mark is None else mark
class TicTacToe(tk.Tk):
"""Play tic-tac-toe. Players take turn clicking on empty buttons
to place their marker. The first player to get three markers in
a row, up/down, sideways or diagonally, wins
"""
# All possible winning conbinations
wins = ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8),
(9, 10, 11), (12, 13, 14), (15, 16, 17), (9, 12, 15), (10, 13, 16), (11, 14, 17),
(18, 19, 20), (21, 22, 23), (24, 25, 26), (18, 21, 24), (19, 22, 25), (20, 23, 26),
(27, 28, 29), (30, 31, 32), (33, 34, 35), (27, 30, 33), (28, 31, 34), (29, 32, 35),
(36, 37, 38), (39, 40, 41), (42, 43, 44), (36, 39, 42), (37, 40, 43), (38, 41, 44),
(45, 46, 47), (48, 49, 50), (51, 52, 53), (45, 48, 51), (46, 49, 52), (47, 50, 53),
(3, 6, 36, 39), (4, 7, 37, 40), (5, 8, 38, 41),
(18, 21, 39, 42), (19, 22, 40, 43), (20, 23, 41, 44),
(28, 29, 36, 37), (31, 32, 39, 40), (34, 35, 42, 43),
(37, 38, 45, 46), (40, 41, 48, 49), (43, 44, 51, 52),
(9, 12, 21, 24), (10, 13, 22, 25), (11, 14, 23, 26),
(0, 3, 12, 15), (1, 4, 13, 16), (2, 5, 14, 17),
(27, 28, 46, 47), (30, 31, 49, 50), (33, 34, 52, 53),
(0, 1, 27, 30), (3, 4, 28, 31), (6, 7, 29, 32),
(1, 2, 47, 50), (4, 5, 46, 49), (7, 8, 45, 48),
(18, 19, 32, 35), (21, 22, 31, 34), (24, 25, 30, 33),
(19, 20, 48, 51), (22, 23, 49, 52), (25, 26, 50, 53),
(15, 16, 27, 28), (12, 13, 30, 31), (9, 10, 33, 34),
(16, 17, 46, 47), (13, 14, 49, 50), (10, 11, 52, 53),
(6, 37, 41, 51), (7, 38, 48, 52), (7, 32, 34, 36), (8, 35, 37, 39),
(19, 28, 32, 42), (20, 29, 39, 43), (18, 41, 43, 45), (19, 44, 46, 48),
(19, 23, 32, 42), (19, 21, 44, 48)) #last one example of a diagonal combo over 2 boards
def __init__(self):
super().__init__()
self.title('Tic Tac Toe')
# create a frame to hold all four boards
self.boards_frame = tk.Frame(self)
self.boards_frame.pack(side="top", padx=5, pady=5)
# create the left board
self.frame1 = tk.Frame(self.boards_frame)
self.frame1.pack(side="left")
self.squares1 = []
for i in range(9):
self.squares1.append(Square(self.frame1, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame1.pack(side="top")
self.frame2 = tk.Frame(self.boards_frame)
self.frame2.pack(side="left")
for i in range(9, 18):
self.squares1.append(Square(self.frame2, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame3 = tk.Frame(self.boards_frame)
self.frame3.pack(side="left")
for i in range(18, 27):
self.squares1.append(Square(self.frame3, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame4 = tk.Frame(self.boards_frame)
self.frame4.pack(side="left")
for i in range(27, 36):
self.squares1.append(Square(self.frame4, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame5 = tk.Frame(self.boards_frame)
self.frame5.pack(side="left")
for i in range(36, 45):
self.squares1.append(Square(self.frame5, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame6 = tk.Frame(self.boards_frame)
self.frame6.pack(side="left")
for i in range(45, 54):
self.squares1.append(Square(self.frame6, i))
for square in self.squares1:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares1))
self.frame2.pack(side="bottom")
self.frame3.pack(side="bottom")
'''
# create the middle-left board
self.frame2 = tk.Frame(self.boards_frame)
self.frame2.pack(side="left")
self.squares2 = [Square(self.frame2, i) for i in range(9)]
for square in self.squares2:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares2, self.squares1))
# create the middle-right board
self.frame3 = tk.Frame(self.boards_frame)
self.frame3.pack(side="left")
self.squares3 = [Square(self.frame3, i) for i in range(9)]
for square in self.squares3:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares3, self.squares1, self.squares2, self.squares4, self.squares5, self.squares6))
self.frame4 = tk.Frame(self.boards_frame)
self.frame4.pack(side="left")
self.squares4 = [Square(self.frame4, i) for i in range(9)]
for square in self.squares4:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares4, self.squares1, self.squares2, self.squares3, self.squares5, self.squares6))
self.frame5 = tk.Frame(self.boards_frame)
self.frame5.pack(side="left")
self.squares5 = [Square(self.frame5, i) for i in range(9)]
for square in self.squares5:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares5, self.squares1, self.squares2, self.squares3, self.squares4, self.squares6))
self.frame1.pack(side="bottom")
self.frame2.pack(side="top")
self.frame6 = tk.Frame(self.boards_frame)
self.frame6.pack(side="left")
self.squares6 = [Square(self.frame6, i) for i in range(9)]
for square in self.squares6:
row = square.index // 3
column = square.index % 3
square.grid(row=row, column=column, padx=5, pady=5)
square.configure(command=lambda arg=square: self.play(arg, self.squares6, self.squares1, self.squares2, self.squares3, self.squares4, self.squares5))
self.frame3.pack(side="bottom")
'''
self.message = tk.Label(self, text=' ', width=30)
self.message.pack(side="bottom")
self.new_game = False
self.player = "X"
self.reset(self.squares1)
def reset(self, squares1):
"""Reset board to empty"""
self.open_squares = 54
self.new_game = False
for square in squares1:
square.mark = None
'''
for square in squares2:
square.mark = None
for square in squares3:
square.mark = None
for square in squares4:
square.mark = None
for square in squares5:
square.mark = None
for square in squares6:
square.mark = None
'''
self.message['text'] = f"{self.player}'s turn"
def play(self, square, squares1):
"""Put player marker in slot if open. Check for win or tie"""
if self.new_game:
return
if square.mark is not None:
self.message['text'] = "Invalid move"
return
square.mark = self.player
self.open_squares -= 1
# check for a win
for win in self.wins:
if all(squares1[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
'''
if all(squares2[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
if all(squares3[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
if all(squares4[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
if all(squares5[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
if all(squares6[i].mark == self.player for i in win):
self.message['text'] = f"{self.player} wins!"
self.new_game = True
return
'''
# check for a tie
if self.open_squares == 0:
self.message['text'] = "Tie game"
self.new_game = True
return
# switch players
self.player = "O" if self.player == "X" else "X"
self.message['text'] = f"{self.player}'s turn"
def game_over(self, squares1):
"""Check for winner or tie"""
# Check all winning combinations
for win in self.wins:
if all(squares1[i].mark == self.player for i in win):
for i in win:
squares1[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
'''
if all(squares2[i].mark == self.player for i in win):
for i in win:
squares2[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
if all(squares3[i].mark == self.player for i in win):
for i in win:
squares3[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
if all(squares4[i].mark == self.player for i in win):
for i in win:
squares4[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
if all(squares5[i].mark == self.player for i in win):
for i in win:
squares5[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
if all(squares6[i].mark == self.player for i in win):
for i in win:
squares6[i]["fg"] = "green"
self.message["text"] = f"{self.player} wins!"
return True
'''
# Check for a tie
if self.open_squares <= 0:
self.message["text"] = "Game ends in a tie"
return True
return False
TicTacToe().mainloop()
Posts: 6,823
Threads: 20
Joined: Feb 2020
On a tick tack toe board the maximum depth is 9 moves. On your board it is 54 moves. That should require a change in this line:
score = 10 - depth if mark is ROBOT else depth - 10 You don't want winning in 12 moves to be a negative score.
This doesn't really matter though. You cannot use minimax to play tic-tac-toe with 54 squares. Even a 4x4 board takes longer to make the first move than anyone is willing to wait. There are too many potential moves and it will take days (maybe weeks or months) for the computer to make the first move. Your only hope would be computing all winning combinations offline ad saving them to a database.
You need to try a different approach. What, I have no idea. Maybe you can use this to get an early start on your doctoral thesis.
Posts: 51
Threads: 6
Joined: Dec 2022
Apr-28-2023, 05:36 PM
(This post was last modified: Apr-28-2023, 05:36 PM by freethrownucleus.)
Yes I tried to adapt this line, but as you said, it doesn't really matter.
But if I only have winning combinations over one of the six boards, could I somehow implement my minimax algorithm (class Robot) into the code?
That was my biggest problem when drawing the surface (a net of a cube) because I didn't know how to draw my sample so I can use one board (9 squares) like I use all 6 boards (54 squares) like I used in the old game when I had a 3d-cube with 3 visible sides/boards by using pygame -> now I'm talking just about changing 3d-cube surface into a net of a cube that I have in the new version.
This was the old version that I'm describing in the last paragraph as you might remember:
"""Tic-tac-toe with a computer opponent. Three boards played simultaneously"""
import pygame
import random
PLAYER = 'X'
ROBOT = 'O'
EMPTY = ' '
background = "aliceblue"
msg_color = "dodgerblue"
colors = {EMPTY: 'dodger blue', PLAYER: 'green', ROBOT: 'red'}
class Robot:
def __init__(self, cube):
self.boards = cube.boards
def get_scores(self, board):
"""Get scores for all open squares on a board"""
def minimax(mark, square, alpha=-1000, beta=1000, depth=0):
"""minimax algorithm with alpha/beta pruning"""
# Place the mark and check for a win
square.mark = mark
if square.check_win():
# Give extra weight to earlier wins/losses
score = 10 - depth if mark is ROBOT else depth - 10
board.depth = min(board.depth, depth)
elif len(empty_squares := board.empty_squares()) == 0:
# No plays left. Draw.
score = 0
elif mark is PLAYER:
# Pick best move for robot
score = -1000
for s in empty_squares:
score = max(score, minimax(ROBOT, s, alpha, beta, depth+1))
alpha = max(alpha, score)
if alpha > beta:
break
else:
# Guess what move player will make
score = 1000
for s in empty_squares:
score = min(score, minimax(PLAYER, s, alpha, beta, depth+1))
beta = min(beta, score)
if alpha > beta:
break
# Remove mark and return score for the square
square.mark = EMPTY
return score
# Collect scores for empty squares. If board is empty,
# minimax will return 0 for all squares
board.depth = 10
empty_squares = board.empty_squares()
if len(empty_squares) == 9:
board.scores = [[0, s] for s in empty_squares]
else:
# Calling minimax twice. The first is to find the square
# giving us best chance to win board. Second is to prevent
# abandoning board early and giving player an easy win.
board.scores = [[minimax("O", s), s] for s in empty_squares]
[minimax("X", s, depth=1) for s in empty_squares]
def play(self):
"""Place robot mark."""
# Get scores for all empty squares
depth = 10
for board in self.boards:
self.get_scores(board)
depth = min(depth, board.depth)
# Select board with minimum depth. This is the board that
# will win/lose in the least number of moves.
scores = []
for board in self.boards:
if board.depth <= depth:
scores.extend(board.scores)
# Randomly select from best scores on the selected board.
max_score = max(score[0] for score in scores)
squares = [score[1] for score in scores if score[0] >= max_score]
return random.choice(squares)
class Square:
"""A 3D square in a tic-tac-toe board"""
def __init__(self, board, index, side, center=(0, 0, 0)):
self.board = board
self.index = index
self.mark = EMPTY
self.corners = [
pygame.Vector3(-1, -1, 0) * side / 2,
pygame.Vector3(1, -1, 0) * side / 2,
pygame.Vector3(1, 1, 0) * side / 2,
pygame.Vector3(-1, 1, 0) * side / 2
]
self.move(center)
def rotate(self, rotation):
"""Rotate square (rx, ry, rz) degrees"""
for deg, axis in zip(rotation, ((1, 0, 0), (0, 1, 0), (0, 0, 1))):
if deg:
for corner in self.corners:
corner.rotate_ip(deg, axis)
return self
def move(self, offset):
"""Move square offset (x, y, z) pixels"""
x, y, z = offset
for corner in self.corners:
corner.x += x
corner.y += y
corner.z += z
return self
def projection(self):
"""Return corners projected on xy plane"""
return [pygame.Vector2(p.x, p.y) for p in self.corners]
def draw(self, surface):
"""Draw projection of square on xy plane"""
pygame.draw.polygon(surface, colors[self.mark], self.projection())
def contains(self, point):
"""Return True if projection contains point."""
def area(a, b, c):
"""Compute area of triangle"""
return abs((a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0)
def has_point(a, b, c, p):
"""Return True if triange ABC contains point p."""
return area(a, b, c) >= int(area(a, p, b) + area(b, p, c) + area(c, p, a))
a, b, c, d = self.projection()
return has_point(a, b, c, point) or has_point(a, c, d, point)
def check_win(self):
return self.board.check_win(self)
class Board:
"""A tic-tac-toe board"""
winning_combos = (
(0, 2, 4, 6, 8), (1, 3, 5, 7), (0, 1, 2), (3, 4, 5),
(6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8),
)
def __init__(self, side):
dx = side / 3
self.squares = []
for index in range(9):
x = (index % 3 - 1) * dx
y = (index // 3 - 1) * dx
self.squares.append(Square(self, index, dx-3, (x, y, 0)))
self.scores = None
self.depth = 10
def empty_squares(self):
"""Return list of empty squares"""
return [s for s in self.squares if s.mark is EMPTY]
def check_win(self, square):
"""Return winning squares from last move, else None"""
for combo in self.winning_combos:
if square.index in combo:
squares = [self.squares[i] for i in combo]
if all(square.mark == s.mark for s in squares):
return squares
return None
class Cube:
"""Three tic-tac-toe boards plastered on the faces of a cube"""
def __init__(self, side):
def make_board(center, rotation):
board = Board(side)
for square in board.squares:
square.rotate(rotation).move(center)
return board
self.boards = [
make_board((0, 0, -side/2), (0, 0, 0)),
make_board((side/2, 0, 0), (0, 270, 0)),
make_board((0, -side/2, 0), (90, 0, 0))
]
self.squares = [s for b in self.boards for s in b.squares]
self.winner = None
self.mark = PLAYER
self.reset()
def click(self, point):
"""Try to place player's mark in clicked square."""
if self.mark is PLAYER:
for square in self.squares:
if square.contains(point):
if square.mark is EMPTY:
self.play(square, self.mark)
return square
break
return None
def play(self, square, mark):
"""Place mark in square. Test if is a winning move"""
square.mark = mark
self.mark_count += 1
if winner := square.check_win():
self.winner = winner
for square in self.squares:
if square not in winner:
square.mark = EMPTY
self.mark = PLAYER if mark is ROBOT else ROBOT
def done(self):
"""Return True if there is a winner or draw"""
return self.winner or self.mark_count >= 27
def reset(self):
"""Reset all boards to empty"""
self.mark_count = 0
self.winner = None
for square in self.squares:
square.mark = EMPTY
def main():
"""Play tic-tac-toe"""
def blit_text(surface, msg, pos, font, color = pygame.Color('dodgerblue')):
x, y = pos
m = msg.split('\n')
for line in m:
text = pygame.font.Font(None, 48).render(line, True, msg_color)
width, height = text.get_size()
surface.blit(text, (x - width/2, y - height * 2))
y += height + 2.
def refresh_screen(surface, msg = None):
"""Draw the cube and an optional message"""
surface.fill(background)
for square in cube.squares:
square.draw(surface)
text_player1 = pygame.font.Font(None, 48).render("You", True, 'green')
text_vs = pygame.font.Font(None, 48).render("vs", True, 'dodgerblue')
text_player2 = pygame.font.Font(None, 48).render("Computer", True, 'red')
surface.blit(text_player1, (text_player1.get_width(), text_player1.get_height()))
surface.blit(text_vs, (center.x - text_vs.get_width() / 2, text_vs.get_height()))
surface.blit(text_player2, (center.x + text_player2.get_width(), text_player2.get_height()))
if msg:
text = pygame.font.Font(None, 48).render(msg, True, msg_color)
pos = (350, 700)
blit_text(surface, msg, pos, None, color = pygame.Color('dodgerblue'))
pygame.display.flip()
pygame.display.set_caption("3D-Tic-Tac-Toe")
surface = pygame.display.set_mode((700, 750))
center = pygame.Vector3(350, 350, 0)
# Move cube for pretty orthogonal view at center of screen
cube = Cube(300)
for square in cube.squares:
square.rotate((0, 45, 0)).rotate((30, 0, 0)).move(center)
robot = Robot(cube)
refresh_screen(surface, None)
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.MOUSEBUTTONDOWN:
if cube.done():
# Start a new game
cube.reset()
if cube.mark is ROBOT:
cube.play(robot.play(), ROBOT)
refresh_screen(surface, None)
elif cube.click(pygame.Vector2(event.pos)):
# Player selected square. Robot's turn,
if not cube.done():
refresh_screen(surface, None)
cube.play(robot.play(), ROBOT)
# Is the game over?
if cube.done():
refresh_screen(surface, "Ready for another play?\nJust click on the screen!")
else:
refresh_screen(surface, None)
pygame.event.clear()
if __name__ == "__main__":
pygame.init()
main()
pygame.quit()
Posts: 6,823
Threads: 20
Joined: Feb 2020
Apr-28-2023, 11:22 PM
(This post was last modified: Apr-28-2023, 11:22 PM by deanhystad.)
Only a part of the problem is due to the number of winning combinations. The main contributing factor to move computation time is the number of available moves.
The code below demonstrates this. It kind of plays out like minimax, if minimax didn't check if the last move won or lost. It just alternates between placing X's and O's in empty squares, counting up the number of plays until all possible moves have been made. It doesn't take long to complete all the different puzzles from size 1 to 9, but finishing 10 is a length delay. 11 takes a really long time, and I give up waiting for 12.
def combinations(num_squares):
global count
def walk(squares):
global count
for index, square in enumerate(squares):
if square is None:
squares[index] = 1
count += 1
walk(squares)
squares[index] = None
squares = [None] * num_squares
count = 0
walk(squares)
return count
for i in range(1, 27):
print(i, combinations(i))Output: 1 1
2 4
3 15
4 64
5 325
6 1956
7 13699
8 109600
9 986409
10 9864100
11 108505111
This is why I used a heuristic in combination with minimax on the three face cube solver. Solving 3 tic-tac-toe games only takes three times longer than solving one, but solving a 27 square tic-tac-toe game takes well over a million times longer than solving a 9 square game.
Posts: 51
Threads: 6
Joined: Dec 2022
Yes makes sense. I got your point.
But can I somehow change this 3d-cube into a net of a cube by some slight changes in this code that uses pygame? I managed to make a net of a cube that I wanted with tkinter but it would be much easier if it's possible to continue using pygame and just change a shape.
This minimax works pretty fine and that's the reason why I would continue using pygame and just change a shape. But I don't know how to change it.
To repeat, I did it in tkinter but I don't know to do anything more using tkinter because as you said, there aren't 9 different squares on a board multiplied by 6, there are 54 different squares which makes the problem much harder to solve.
The code I just want to change the shape in:
"""Tic-tac-toe with a computer opponent. Three boards played simultaneously"""
import pygame
import random
PLAYER = 'X'
ROBOT = 'O'
EMPTY = ' '
background = "aliceblue"
msg_color = "dodgerblue"
colors = {EMPTY: 'dodger blue', PLAYER: 'green', ROBOT: 'red'}
class Robot:
def __init__(self, cube):
self.boards = cube.boards
def get_scores(self, board):
"""Get scores for all open squares on a board"""
def minimax(mark, square, alpha=-1000, beta=1000, depth=0):
"""minimax algorithm with alpha/beta pruning"""
# Place the mark and check for a win
square.mark = mark
if square.check_win():
# Give extra weight to earlier wins/losses
score = 10 - depth if mark is ROBOT else depth - 10
board.depth = min(board.depth, depth)
elif len(empty_squares := board.empty_squares()) == 0:
# No plays left. Draw.
score = 0
elif mark is PLAYER:
# Pick best move for robot
score = -1000
for s in empty_squares:
score = max(score, minimax(ROBOT, s, alpha, beta, depth+1))
alpha = max(alpha, score)
if alpha > beta:
break
else:
# Guess what move player will make
score = 1000
for s in empty_squares:
score = min(score, minimax(PLAYER, s, alpha, beta, depth+1))
beta = min(beta, score)
if alpha > beta:
break
# Remove mark and return score for the square
square.mark = EMPTY
return score
# Collect scores for empty squares. If board is empty,
# minimax will return 0 for all squares
board.depth = 10
empty_squares = board.empty_squares()
if len(empty_squares) == 9:
board.scores = [[0, s] for s in empty_squares]
else:
# Calling minimax twice. The first is to find the square
# giving us best chance to win board. Second is to prevent
# abandoning board early and giving player an easy win.
board.scores = [[minimax("O", s), s] for s in empty_squares]
[minimax("X", s, depth=1) for s in empty_squares]
def play(self):
"""Place robot mark."""
# Get scores for all empty squares
depth = 10
for board in self.boards:
self.get_scores(board)
depth = min(depth, board.depth)
# Select board with minimum depth. This is the board that
# will win/lose in the least number of moves.
scores = []
for board in self.boards:
if board.depth <= depth:
scores.extend(board.scores)
# Randomly select from best scores on the selected board.
max_score = max(score[0] for score in scores)
squares = [score[1] for score in scores if score[0] >= max_score]
return random.choice(squares)
class Square: #THIS IS WHAT I WANT TO CHANGE
"""A 3D square in a tic-tac-toe board"""
def __init__(self, board, index, side, center=(0, 0, 0)):
self.board = board
self.index = index
self.mark = EMPTY
self.corners = [
pygame.Vector3(-1, -1, 0) * side / 2,
pygame.Vector3(1, -1, 0) * side / 2,
pygame.Vector3(1, 1, 0) * side / 2,
pygame.Vector3(-1, 1, 0) * side / 2
]
self.move(center)
def rotate(self, rotation):
"""Rotate square (rx, ry, rz) degrees"""
for deg, axis in zip(rotation, ((1, 0, 0), (0, 1, 0), (0, 0, 1))):
if deg:
for corner in self.corners:
corner.rotate_ip(deg, axis)
return self
def move(self, offset):
"""Move square offset (x, y, z) pixels"""
x, y, z = offset
for corner in self.corners:
corner.x += x
corner.y += y
corner.z += z
return self
def projection(self):
"""Return corners projected on xy plane"""
return [pygame.Vector2(p.x, p.y) for p in self.corners]
def draw(self, surface):
"""Draw projection of square on xy plane"""
pygame.draw.polygon(surface, colors[self.mark], self.projection())
def contains(self, point):
"""Return True if projection contains point."""
def area(a, b, c):
"""Compute area of triangle"""
return abs((a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0)
def has_point(a, b, c, p):
"""Return True if triange ABC contains point p."""
return area(a, b, c) >= int(area(a, p, b) + area(b, p, c) + area(c, p, a))
a, b, c, d = self.projection()
return has_point(a, b, c, point) or has_point(a, c, d, point)
def check_win(self):
return self.board.check_win(self)
class Board:
"""A tic-tac-toe board"""
winning_combos = (
(0, 2, 4, 6, 8), (1, 3, 5, 7), (0, 1, 2), (3, 4, 5),
(6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8),
)
def __init__(self, side):
dx = side / 3
self.squares = []
for index in range(9):
x = (index % 3 - 1) * dx
y = (index // 3 - 1) * dx
self.squares.append(Square(self, index, dx-3, (x, y, 0)))
self.scores = None
self.depth = 10
def empty_squares(self):
"""Return list of empty squares"""
return [s for s in self.squares if s.mark is EMPTY]
def check_win(self, square):
"""Return winning squares from last move, else None"""
for combo in self.winning_combos:
if square.index in combo:
squares = [self.squares[i] for i in combo]
if all(square.mark == s.mark for s in squares):
return squares
return None
class Cube:
"""Three tic-tac-toe boards plastered on the faces of a cube"""
def __init__(self, side):
def make_board(center, rotation):
board = Board(side)
for square in board.squares:
square.rotate(rotation).move(center)
return board
self.boards = [
make_board((0, 0, -side/2), (0, 0, 0)),
make_board((side/2, 0, 0), (0, 270, 0)),
make_board((0, -side/2, 0), (90, 0, 0))
]
self.squares = [s for b in self.boards for s in b.squares]
self.winner = None
self.mark = PLAYER
self.reset()
def click(self, point):
"""Try to place player's mark in clicked square."""
if self.mark is PLAYER:
for square in self.squares:
if square.contains(point):
if square.mark is EMPTY:
self.play(square, self.mark)
return square
break
return None
def play(self, square, mark):
"""Place mark in square. Test if is a winning move"""
square.mark = mark
self.mark_count += 1
if winner := square.check_win():
self.winner = winner
for square in self.squares:
if square not in winner:
square.mark = EMPTY
self.mark = PLAYER if mark is ROBOT else ROBOT
def done(self):
"""Return True if there is a winner or draw"""
return self.winner or self.mark_count >= 27
def reset(self):
"""Reset all boards to empty"""
self.mark_count = 0
self.winner = None
for square in self.squares:
square.mark = EMPTY
def main():
"""Play tic-tac-toe"""
def blit_text(surface, msg, pos, font, color = pygame.Color('dodgerblue')):
x, y = pos
m = msg.split('\n')
for line in m:
text = pygame.font.Font(None, 48).render(line, True, msg_color)
width, height = text.get_size()
surface.blit(text, (x - width/2, y - height * 2))
y += height + 2.
def refresh_screen(surface, msg = None):
"""Draw the cube and an optional message"""
surface.fill(background)
for square in cube.squares:
square.draw(surface)
text_player1 = pygame.font.Font(None, 48).render("You", True, 'green')
text_vs = pygame.font.Font(None, 48).render("vs", True, 'dodgerblue')
text_player2 = pygame.font.Font(None, 48).render("Computer", True, 'red')
surface.blit(text_player1, (text_player1.get_width(), text_player1.get_height()))
surface.blit(text_vs, (center.x - text_vs.get_width() / 2, text_vs.get_height()))
surface.blit(text_player2, (center.x + text_player2.get_width(), text_player2.get_height()))
if msg:
text = pygame.font.Font(None, 48).render(msg, True, msg_color)
pos = (350, 700)
blit_text(surface, msg, pos, None, color = pygame.Color('dodgerblue'))
pygame.display.flip()
pygame.display.set_caption("3D-Tic-Tac-Toe")
surface = pygame.display.set_mode((700, 750))
center = pygame.Vector3(350, 350, 0)
# Move cube for pretty orthogonal view at center of screen
cube = Cube(300)
for square in cube.squares:
square.rotate((0, 45, 0)).rotate((30, 0, 0)).move(center)
robot = Robot(cube)
refresh_screen(surface, None)
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
elif event.type == pygame.MOUSEBUTTONDOWN:
if cube.done():
# Start a new game
cube.reset()
if cube.mark is ROBOT:
cube.play(robot.play(), ROBOT)
refresh_screen(surface, None)
elif cube.click(pygame.Vector2(event.pos)):
# Player selected square. Robot's turn,
if not cube.done():
refresh_screen(surface, None)
cube.play(robot.play(), ROBOT)
# Is the game over?
if cube.done():
refresh_screen(surface, "Ready for another play?\nJust click on the screen!")
else:
refresh_screen(surface, None)
pygame.event.clear()
if __name__ == "__main__":
pygame.init()
main()
pygame.quit()
|
