MiniMax Recursive Algorithm (Python)

Question

나는 꽤 새롭기 때문에 여기에 게시 할 때 오류가 발생하면 사과드립니다 ... 검색을 수행했지만 많이 도움이되지 않았습니다. Tic Tac Toe의 변형을위한 miniMax 알고리즘을 쓰고 있습니다. 이 변형을 통해 플레이어는 보드에 X 또는 O를 둘 수 있습니다. 재귀에 문제가있어서 약간의 지침을 얻을 수 있기를 바랍니다.

class TicTacToeBoard: 

def __init__(self, initGameBoard): 
    #initGameBoard is a string 
    self.board = initGameBoard 

def getEmptySpaces(self): 
    return self.board.count("-") 

def markX(self, index): 
    self.board = self.board[:index] + "x" + self.board[index+1:] 

def markO(self, index): 
    self.board = self.board[:index] + "o" + self.board[index+1:] 

def endGame(self): 
    #determines if someone has won 
    endGameStates = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] 
    for x in range(len(endGameStates)): 
     trySlice = self.board[endGameStates[x][0]] + self.board[endGameStates[x][1]] + \ 
        self.board[endGameStates[x][2]] 
     if trySlice[0] == trySlice[1] == trySlice[2] and "-" not in trySlice: 
      return True 
    return False 

def draw(self): 
    #determines if there has been a draw 
    if "-" not in self.board: 
     endGameStates = [[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]] 
     for x in range(len(endGameStates)): 
      trySlice = self.board[endGameStates[x][0]] + self.board[endGameStates[x][1]] + \ 
         self.board[endGameStates[x][2]] 
      if trySlice[0] == trySlice[1] == trySlice[2] and "-" not in trySlice: 
       return False 
     return True 
    else: 
     return False 

def __str__(self): 
    boardStr = "" 
    for char in self.board: 
     boardStr += char 
    return boardStr 

는 위 내 보드 클래스입니다. 나는 문자열을 사용하고 너무 화려하지 않습니다. 나는 또한 (나는 생각하지만 내가 너무 내 생각 문자열을 사용할 수 있습니다 ...) 단지 데이터를 저장하는 매우 간단한 노드 클래스를 사용하고

from tic_tac_toe_board import TicTacToeBoard  
from node import Node 

nodeQueue = [] 

def fitnessFunction(gameBoard): 
    #only runs if end game or if all full 
    if gameBoard.draw(): 
     return 0 
    else: 
     emptySpaces = gameBoard.getEmptySpaces() 
     if emptySpaces %2 == 0: 
      #max won 
      return (emptySpaces + 1) *1 
     else: 
      #max lost 
      return (emptySpaces + 1) *-1 

def miniMax(gameBoard): 
    if gameBoard.endGame() or if "-" not in gameBoard: 
     #end game checks for winner, second clause checks for full/draw 
     return fitnessFunction(gameBoard) 
    else: 
     emptyIndexes = [] #keeps track of which indexes are empty 
     count = 0 
     for char in gameBoard: 
      if char == "-": 
       emptyIndexes.append(count) 
      count +=1    
     if len(emptyIndexes) %2 != 0: 
      #max's turn 
      for index in emptyIndexes: 
       childNode = Node(gameBoard.markX(index)) 
       nodeQueue.append(childNode) 
       childNode = Node(gameBoard.markO(index)) 
       nodeQueue.append(childNode) 
     return miniMax() 

fitnessFunction는 수에 따라 점수를 반환 빈 공간이 남았습니다. 내 재귀 miniMax 메소드에 문제가 있습니다. 내가해야 할 일은 기본 케이스 (플레이어가이기는 것 또는 추첨하는 것)를 확인하는 것입니다. 그리고 그 기본 케이스가 사실이 아니라면, 남은 빈 공간의 수를 기반으로 이동을 결정합니다. 나는 그걸 멀리 생각한 것 같지만, 다음에해야할 일 (재귀 부분)을 모른다. 나는 또한 누구의 차례에 따라 아이들의 최소 또는 최대를 얻을 수 있어야합니다. 나는 재귀와 함께 길을 잃은 것 같다. 나는 CS에 익숙하지 않고 그것에 많은 관심을 기울이지 않았습니다. 어떤 힌트도 대단히 감사하겠습니다! :)

Answer 1

미니 맥스 알고리즘을 찾으려면 적용 할 예제가 필요 없습니다. 대부분의 게임에는 최소 최대 알고리즘이 필요합니다.

그래서 원한다면 어떻게 행동해야하는지 결정하십시오. 그런 다음 적어도 하나의 행동에 대한 테스트를 작성하십시오.

시험을 게시하십시오. (게임이 아니며 게임 결과 일뿐입니다.)

알고리즘이 작동하지 않으면 게임 프로그램이 작동하지 않을 수 있습니다.

힌트 : 미니 맥스 알고리즘은 게임이 실행될 때가 아니라 게임 경로의 평가에만 의존합니다.