#python #algorithm #minimax
#python #алгоритм #минимакс
Вопрос:
В настоящее время я работаю над непревзойденной игрой в крестики-нолики на Python с использованием минимаксного алгоритма. На данный момент я застрял на несколько дней, пытаясь выяснить, почему алгоритм не возвращает правильный результат или ходы для воспроизведения ИИ. В текущем состоянии программы, если я выполняю первый ход (X) в верхнем левом углу, минимакс возвращает значение 0, что кажется правильным, поскольку компьютер может только связать. Однако это должно применяться ко всем углам, и любой начальный ввод в нижней строке возвращает -1, что неверно. Лучший ход, который возвращается, также фактически не является лучшим ходом. Любой ввод будет оценен, подсказки будут предпочтительнее, чем полный ответ. Я включил соответствующий код ниже:
#executes on odd numbered turns (AI goes second) Currently configured with print statements for debugging
def AI_Logic():
score = minimax(Board, False)
x, y = bestmove
Board[x][y] = 0
print(count)
print(bestmove)
print(score)
print(Board)
Turn = 1
def minimax(Board, Maxplayer):
global bestmove
global count
count = 1
# Checks if the board is full or if a player has won
if is_Full(Board) or has_Won(Board) == True:
# Checks for wins, if no wins exists return 0
if has_Won(Board) == False:
return 0
# If O has won , return 1
elif who_Won(Board) == 0:
return 1
# If X has won, return -1
elif who_Won(Board) == 1:
return -1
if Maxplayer == True:
maxscore = float("-inf")
for x in range(3):
for y in range(3):
if Board[x][y] == None:
Board[x][y] = 0
score = minimax(Board, False)
Board[x][y] = None
if score > maxscore:
bestmove = (x, y)
maxscore = max(maxscore, score)
return maxscore
else:
minscore = float("inf")
for x in range(3):
for y in range(3):
if Board[x][y] == None:
Board[x][y] = 1
score = minimax(Board, True)
Board[x][y] = None
minscore = min(minscore, score)
return minscore
def is_Full(Board):
if any(None in sublist for sublist in Board):
return False
else:
return True
def who_Won(Board):
global hasWon
# Checks for three of a kind in first column
if Board[0][0] == Board[1][0] and Board[0][0] != None:
if Board[1][0] == Board[2][0]:
hasWon = 1
return Board[2][0]
if Board[0][0] == Board[0][1] and Board[0][0] != None:
if Board[0][1] == Board[0][2]:
hasWon = 1
return Board[0][2]
# Checks for diag win top Left to bottom right
if Board[0][0] == Board[1][1] and Board[0][0] != None:
if Board[1][1] == Board[2][2]:
hasWon = 1
return Board[2][2]
# Checks for diag win bottom left to top right
if Board[0][2] == Board[1][1] and Board[0][2] != None:
if Board[1][1] == Board[2][0]:
hasWon = 1
return Board[2][0]
# Checks for center column win
if Board[0][1] == Board[1][1] and Board[0][1] != None:
if Board[1][1] == Board[2][1]:
hasWon = 1
return Board[2][1]
# Checks for right column win:
if Board[0][2] == Board[1][2] and Board[0][2] != None:
if Board[1][2] == Board[2][2]:
hasWon = 1
return Board[2][2]
# Checks for second row win:
if Board[1][0] == Board[1][1] and Board[1][0] != None:
if Board[1][1] == Board[1][2]:
hasWon = 1
return Board[1][2]
# Checks for third row win:
if Board[2][0] == Board[2][1] and Board[2][0] != None:
if Board[2][1] == Board[2][2]:
hasWon = 1
return Board[2][2]
def has_Won(Board):
# Checks for three of a kind in first column
if Board[0][0] == Board[1][0] and Board[0][0] != None:
if Board[1][0] == Board[2][0]:
return True
if Board[0][0] == Board[0][1] and Board[0][0] != None:
if Board[0][1] == Board[0][2]:
return True
# Checks for diag win top Left to bottom right
if Board[0][0] == Board[1][1] and Board[0][0] != None:
if Board[1][1] == Board[2][2]:
return True
# Checks for diag win bottom left to top right
if Board[0][2] == Board[1][1] and Board[0][2] != None:
if Board[1][1] == Board[2][0]:
return True
# Checks for center column win
if Board[0][1] == Board[1][1] and Board[0][1] != None:
if Board[1][1] == Board[2][1]:
return True
# Checks for right column win:
if Board[0][2] == Board[1][2] and Board[0][2] != None:
if Board[1][2] == Board[2][2]:
return True
# Checks for second row win:
if Board[1][0] == Board[1][1] and Board[1][0] != None:
if Board[1][1] == Board[1][2]:
return True
# Checks for third row win:
if Board[2][0] == Board[2][1] and Board[2][0] != None:
if Board[2][1] == Board[2][2]:
return True
return False
# Checks the position of a mouse click and draws an X/O, Appends the Board matrix with a 1 in the correct spot to reflect an X, 0 to relfect O
def draw_X(x, y):
global Turn
# Checks if turn is an even number (i.e x's turn)
if Turn % 2 == 0:
# Series of statements checking the x and y pos of the mouse. Each mouse click lies in a specific box, draw the X/O in the center of the box,
# making sure there is nothing in the box, and not to overwrite if an X or O already exist.
if x < WIDTH / 3 and y < HEIGHT/3:
if Board[0][0] == None:
Board[0][0] = 1
WIN.blit(X, (60, 60))
# Increases Turn after each executed x or O drawing
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT/3:
if Board[0][1] == None:
Board[0][1] = 1
WIN.blit(X, (WIDTH / 3 60, 60))
Turn = 1
elif x < WIDTH and y < HEIGHT/3:
if Board[0][2] == None:
Board[0][2] = 1
WIN.blit(X, (WIDTH - WIDTH / 3 60, 60))
Turn = 1
elif x < WIDTH / 3 and y < HEIGHT - HEIGHT/3:
if Board[1][0] == None:
Board[1][0] = 1
WIN.blit(X, (60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT - HEIGHT/3:
if Board[1][1] == None:
Board[1][1] = 1
WIN.blit(X, (WIDTH / 3 60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH and y < HEIGHT - HEIGHT/3:
if Board[1][2] == None:
Board[1][2] = 1
WIN.blit(X, (WIDTH - WIDTH / 3 60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH / 3 and y < HEIGHT:
if Board[2][0] == None:
Board[2][0] = 1
WIN.blit(X, (60, HEIGHT - HEIGHT / 3 60))
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT:
if Board[2][1] == None:
Board[2][1] = 1
WIN.blit(X, (WIDTH / 3 60, HEIGHT - HEIGHT / 3 60))
Turn = 1
elif x < WIDTH and y < HEIGHT:
if Board[2][2] == None:
Board[2][2] = 1
WIN.blit(X, (WIDTH - WIDTH / 3 60, HEIGHT - HEIGHT / 3 60))
Turn = 1
# On odd number turns, O will be drawn onto the board:
else:
if x < WIDTH / 3 and y < HEIGHT/3:
if Board[0][0] == None:
Board[0][0] = 0
WIN.blit(O, (60, 60))
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT/3:
if Board[0][1] == None:
Board[0][1] = 0
WIN.blit(O, (WIDTH / 3 60, 60))
Turn = 1
elif x < WIDTH and y < HEIGHT/3:
if Board[0][2] == None:
Board[0][2] = 0
WIN.blit(O, (WIDTH - WIDTH / 3 60, 60))
Turn = 1
elif x < WIDTH / 3 and y < HEIGHT - HEIGHT/3:
if Board[1][0] == None:
Board[1][0] = 0
WIN.blit(O, (60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT - HEIGHT/3:
if Board[1][1] == None:
Board[1][1] = 0
WIN.blit(O, (WIDTH / 3 60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH and y < HEIGHT - HEIGHT/3:
if Board[1][2] == None:
Board[1][2] = 0
WIN.blit(O, (WIDTH - WIDTH / 3 60, HEIGHT / 3 60))
Turn = 1
elif x < WIDTH / 3 and y < HEIGHT:
if Board[2][0] == None:
Board[2][0] = 0
WIN.blit(O, (60, HEIGHT - HEIGHT / 3 60))
Turn = 1
elif x < WIDTH - WIDTH / 3 and y < HEIGHT:
if Board[2][1] == None:
Board[2][1] = 0
WIN.blit(O, (WIDTH / 3 60, HEIGHT - HEIGHT / 3 60))
Turn = 1
elif x < WIDTH and y < HEIGHT:
if Board[2][2] == None:
Board[2][2] = 0
WIN.blit(O, (WIDTH - WIDTH / 3 60, HEIGHT - HEIGHT / 3 60))
Turn = 1
# 3x3 Matrix used for game logic
Board = [[None]*3, [None]*3, [None]*3]
# Executes every frame, draws the board, checks for wins, and updates the display
def draw_Window():
draw_Board()
has_Won(Board)
pygame.display.update()
# Main Event Loop
def main():
global Turn
FPS = 60
run = True
WIN.fill((255, 255, 255))
clock = pygame.time.Clock()
while run:
clock.tick(FPS)
draw_Window()
# Runs the AI turn on odd numbers
if Turn % 2 != 0:
while x:
AI_Logic()
x = False
# Checks for winner
if has_Won == True:
pass
for event in pygame.event.get():
if event.type == pygame.QUIT:
run = False
# Checks if a mouse is clicked. When clicked, it records the x and y pos of the mouse and passes it through the draw_X function
if event.type == pygame.MOUSEBUTTONDOWN:
x, y = pygame.mouse.get_pos()
draw_X(x, y)
pygame.display.update()
pygame.quit()
main()
Комментарии:
1. Можем ли мы посмотреть, как вы создаете плату, которую вы передаете в эти функции?
2. Абсолютно, просто добавил больше кода в сообщение, входные данные игрока добавляются через функцию draw_X .
3. Существует много кода, и я не могу его запустить, не могли бы вы поместить все это в pastebin?
4. Вы запускали свою
minimaxфункцию самостоятельно без какого-либо пользовательского интерфейса — например, просто некоторые базовые тесты на разных платах в консольном приложении или среде тестирования?5. В соответствии с запросом здесь приведен весь код через paste bin. pastebin.com/DjeHMaKD Я отключил некоторые аспекты, которые я переопределю позже (например, фактически нарисовал поворот ИИ в пользовательском интерфейсе). В настоящее время он просто выводит состояние доски после хода ии. Я попробую реализовать тот же алгоритм в более простой программе без пользовательского интерфейса, чтобы увидеть, достигну ли я другого результата. Хорошее предложение.