从中间向外循环列表

Question

我正在制作一个连接四个 AI，并希望 AI 从中间和向外循环遍历可用的动作，因为在连接四个中，中间的动作通常更好，然后发生 alpha beta 修剪的概率要高得多.

例如，如果我给它一个这样的数组：[1,2,3,4,5]
它应该像这样循环 3,4,2,5,1

或者像这样的数组 [1,2,3,4,5,6]
它应该像这样循环 4,3,5,2,6,1

提前致谢

这是我连接四的代码：

import os # os.system('cls') to clear screen 
import random
import time
import sys

class ConnectFour:
    def __init__(self):
        self.board = [[" ", " ", " ", " ", " ", " "," "], 
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "]]
        self.numberLine = [1,2,3,4,5,6,7]
        self.rowCount = 6
        self.columnCount = 7

    def printBoard(self, column=None, row=None):
        os.system('cls') # clears the screen
        terminalWidth = os.get_terminal_size().columns
        terminalHeight = os.get_terminal_size().lines

        playerToHighlighted = {
        'R': '3[91;44mR3[0m',
        'Y': '3[93;44mY3[0m' }

        print("\n"*round(terminalHeight/2 - (1 + self.columnCount))) # 
        
        highlightedPlayer = ''

        try:
            playerHold = self.board[row][column] 
            self.board[row][column] = 'H'
            highlightedPlayer = playerToHighlighted[playerHold]
        except:
            pass

        print(
        ((((
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[5])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[4])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[3])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[2])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[1])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        (("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ".format(*self.board[0])).center(terminalWidth)) + '\n' + 
        '3[94m' + ("---------------------------------------").center(terminalWidth) + '3[0m' + '\n' +
        ((("  {}  |  {}  |  {}  |  {}  |  {}  |  {}  |  {}  ").format(*self.numberLine)).center(terminalWidth))).replace('Y', '3[93mY3[0m')).replace('R', "3[91mR3[0m")).replace('|', '3[94m|3[0m')).replace('H', highlightedPlayer)  )
        
        try:
            self.board[row][column] = playerHold
        except:
            pass

    def clearBoard(self):
        self.board = [[" ", " ", " ", " ", " ", " "," "], 
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "],
                      [" ", " ", " ", " ", " ", " "," "]]
    
    def makeMove(self, position, player):
        for row in range(self.rowCount):
            if self.board[row][position] == " ":
                self.board[row][position] = player
                return row

    def availableMoves(self): # this might be broken
        moves = []
        for column in range(self.columnCount):
            if self.board[self.rowCount - 1][column] == ' ':
                moves.append(column)
        return moves

    def removeMove(self, row, column): 
        self.board[row][column] = " "    

    def checkWin(self): 
        for player in ('R', 'Y'): 
            for column in range(self.columnCount - 3): # Check vertical locations for win
                for row in range(self.rowCount):
                    if self.board[row][column] == player and self.board[row][column+1] == player and self.board[row][column+2] == player and self.board[row][column+3] == player:
                        return player

            for column in range(self.columnCount): # Check vertical locations for win
                for row in range(self.rowCount - 3):
                    if self.board[row][column] == player and self.board[row+1][column] == player and self.board[row+2][column] == player and self.board[row+3][column] == player:
                        return player
            
            for column in range(self.columnCount-  3): # Check positively sloped diaganols
                for row in range(self.rowCount - 3):
                    if self.board[row][column] == player and self.board[row+1][column+1] == player and self.board[row+2][column+2] == player and self.board[row+3][column+3] == player:
                        return player

            for column in range(self.columnCount-3): # Check negatively sloped diaganols
                for row in range(3, self.rowCount):
                    if self.board[row][column] == player and self.board[row-1][column+1] == player and self.board[row-2][column+2] == player and self.board[row-3][column+3] == player:
                        return player

    def whoWon(self):
        if self.checkWin() == 'R':
            return "Red"
        elif self.checkWin() == 'Y':
            return "Yellow"
        elif self.checkGameOver() == True:
            return "Nobody"


    def checkGameOver(self): 
        if self.checkWin() != None:
            return True
        for column in range(self.columnCount):
                if self.board[self.rowCount - 1][column] == " ":
                    return False
        return True

    def getMoveCount(self, player): # getStoneCount this can be better
        moveCount = 0
        for column in range(self.columnCount):
            for row in range(self.rowCount):
                if self.board[row][column] == player:
                    moveCount += 1
        return moveCount
    

    def minimax(self, node, depth, alpha, beta, player):
        if depth == 0 or node.checkGameOver():
            if node.checkWin() == 'R':
                return -(22 - self.getMoveCount('R'))
            elif node.checkWin() == 'Y':
                return 22 - self.getMoveCount('Y')
            else:
                return 0

        if player == 'Y':
            maxValue = -(sys.maxsize)
            for move in node.availableMoves():
                moveRow = node.makeMove(move, player)
                moveValue = self.minimax(node, depth-1, alpha, beta, changePlayer(player))
                node.removeMove(moveRow, move)
                maxValue = max(maxValue, moveValue)
                alpha = max(alpha, moveValue)
                if beta <= alpha:
                    break
            return maxValue
        
        if player == 'R':
            minValue = sys.maxsize
            for move in node.availableMoves():
                moveRow = node.makeMove(move, player)
                moveValue = self.minimax(node, depth-1, alpha, beta, changePlayer(player))
                node.removeMove(moveRow, move)
                minValue = min(minValue, moveValue)
                beta = min(beta, moveValue)
                if beta <= alpha: 
                    break
            return minValue

def changePlayer(player):
    if player == 'R':
        return 'Y'
    else:
        return 'R'

def makeBestMove(board, depth, player):
    neutralValue = 0
    choices = []
    bestLossingMoveValue = -(sys.maxsize)

    for move in board.availableMoves(): 
        moveRow = board.makeMove(move, player)
        moveValue = board.minimax(board, depth-1, -(sys.maxsize), sys.maxsize, changePlayer(player))
        board.removeMove(moveRow, move)
        print(moveValue)
        
        if moveValue > neutralValue:
            choices = [move]
            #instaWin = True
            break
        elif moveValue == neutralValue:
            choices.append(move)
        elif moveValue > bestLossingMoveValue:  
            bestLossingMove = move

    if len(choices) > 0:
        return random.choice(choices), choices
    elif bestLossingMove != None:
        return bestLossingMove, [False]
    else: 
        return random.choice(board.availableMoves()), [] # idk if i need this


def askPlayAgain():
    terminalWidth = os.get_terminal_size().columns
    print("Would you like to play again?".center(terminalWidth))
    playAgain = input(' ' * round(terminalWidth/2 - 8) + "Enter y/n here: ")
    if playAgain == 'y':
        game.clearBoard()
        game.printBoard()        
        setupGame() 
    elif playAgain == 'n':
        exit()
    else: 
        game.printBoard()
        print("Error: Please try again!".center(terminalWidth))
        askPlayAgain()

playerToColor = {
    'R': '3[91mRed3[0m',
    'Y': '3[93mYellow3[0m' }

def askPlayerMove(player):
    terminalWidth = os.get_terminal_size().columns
    print(("You are " + playerToColor[player] + ": Choose number from 1-7").center(terminalWidth + 8))    
    move = input(" " * round(terminalWidth/2 - 9) + "Enter Move Here: ")
    try:
        move = int(move) - 1
    except:
        game.printBoard()
        print("Error: Please try again!".center(terminalWidth))
        return askPlayerMove(player)

    if move >= 0 and move <= game.columnCount - 1: 
        row = game.makeMove(move, player)
        return [move, row]
    else:
        game.printBoard()
        print("Error: Please try again!".center(terminalWidth))
        return askPlayerMove(player)

def askDepth():
    terminalWidth = os.get_terminal_size().columns
    print(("What depth do you want the engine to use?").center(terminalWidth))    
    depth = input(" " * round(terminalWidth/2 - 17) + "Enter depth here: (Recommended: 9) ")
    try:
        depth = int(depth)
        return depth
    except:
        game.printBoard()
        print("Error: Please try again!".center(terminalWidth))
        return askDepth()


def setupGame():

    terminalWidth = os.get_terminal_size().columns
    print("Would you like to play computer or player".center(terminalWidth))    
    gameMode = input(" " * round(terminalWidth/2 - 8) + "Enter c/p Here: ")

    if gameMode == 'p':
        startGame(gameMode)
    elif gameMode == 'c':
        game.printBoard()
        depth = askDepth()
        startGame(gameMode, depth)
    else:
        game.printBoard()
        print("Error: Please try again!".center(terminalWidth))
        setupGame()
    


def startGame(gameMode, depth=None):
    
    game.printBoard()

    while game.checkGameOver() == False:
        movePosition = askPlayerMove('R')
        game.printBoard(movePosition[0], movePosition[1])

        if game.checkGameOver() == True:
            break
        
        if gameMode == 'c':
            terminalWidth = os.get_terminal_size().columns
            print("Computer choosing move...".center(terminalWidth))
            computerMove = makeBestMove(game, depth, 'Y') 
            movePosition[1] = game.makeMove(computerMove[0], 'Y') 
            movePosition[0] = computerMove[0]
            computerChoices = computerMove[1]
        elif gameMode == 'p':
            movePosition = askPlayerMove('Y')

        game.printBoard(movePosition[0], movePosition[1])
        if gameMode == 'c':
            print(("Computer choices are " + str(computerChoices)).center(terminalWidth))
            
        
    terminalWidth = os.get_terminal_size().columns
    game.printBoard()
    print(("Game Over. " + game.whoWon() + " Wins").center(terminalWidth))
    askPlayAgain()
    

if __name__ == '__main__':
    game = ConnectFour()
    game.printBoard()

    setupGame() #start game

Answer 1

如果想按到中间的距离排序，可以使用lambda表达式。

a = [1, 2, 3, 4, 5]
sortedByMiddle = sorted(a, key = lambda x: abs(x-a[len(a)//2]))

这将遍历数组并按数组元素与中间值之差的绝对值排序。

Answer 2

总是把中间的去掉：

def middle_out(a):
    while a:
        yield a.pop(len(a) // 2)

演示：

>>> print(*middle_out([1,2,3,4,5]))
3 4 2 5 1
>>> print(*middle_out([1,2,3,4,5,6]))
4 3 5 2 6 1

从中间向外循环列表

Loop over a list from the middle outwards

python

minimax

alpha-beta-pruning