Minimax funktioniert nicht

[henridoh]

Ich habe einen unschlagbaren Tic Tac Toe bot gemacht, aber mir war der Algorithmus zu schlampig und jetzt habe ich es mit minimax versucht.

Kann mir jemand sage was an dieser Minimax funktion(aiset()) falsch ist?
Ich kenn mich noch nicht so gut damit aus

Code: Alles auswählen

from random import randint
from time import sleep
table = ["0", "1", "2",
         "3", "4", "5",
         "6", "7", "8"]
computer = ""
human = ""
turn = ""


def randlist(array):
    return array[randint(0, len(array)-1)]


def isfree(board, pos):
    return False if board[pos] == ["X", "O"] else True


def pickl():
    global human
    global computer
    global turn
    letter = ""
    while not(letter in ["X", "O"]):
        letter = input("Please pick X or O. ")
    human = letter
    computer = "X" if letter == "O" else "O"
    turn = randlist([computer, human])
    print("{} beginns! ".format(turn))


def setp(pos, p):
    if not(table[pos] in ["X", "O"]):
        table[pos] = p
    else:
        return False


def winning(board, player):
    try:
        for i in [0, 3, 6]:
            if [board[i], board[i+1], board[i+2]].index(player) == 3:
                return True
        for i in [0, 1, 2]:
            if [board[i], board[i+3], board[+6]].index(player) == 3:
                return True
        if [board[0], board[4], board[8]].index(player) == 3 or [board[2], board[4], board[6]].index(player) == 3:
                return True
    except ValueError:
        return False
    return False


def aiset(board, player):
    global computer
    global human


    av = []
    for i in range(len(board)):
        if not(board[i] in ["O", "X"]):
            av.append(i)

    moves = []

    if winning(board, human):
        return {"score": -10}
    elif winning(board, computer):
        return {"score": +10}
    elif len(av) == 0:
        return {"score": 0}


    for i in av:
        move = {}

        move["index"] = board[i]
        board[i] = player

        if player == human:
            move["score"] = aiset(board, computer)["score"]
        else:
            move["score"] = aiset(board, human)["score"]

        board[i] = move["index"]

        moves.append(move)

    bestMove = None

    if player == computer:
        bestScore = -1000000
        for i in range(len(moves)):
            if moves[i]["score"] > bestScore:
                bestScore = moves[i]["score"]
                bestMove = i
    else:
        bestScore = 100000
        for i in range(len(moves)):
            if moves[i]["score"] < bestScore:
                bestScore = moves[i]["score"]
                bestMove = i

    return moves[bestMove]






def printtable():
    global table
    for i in [0, 3, 6]:
        print("|"+table[i]+"|"+table[i+1]+"|"+table[i+2]+"|")
    print("\n")


if __name__ == "__main__":
    turnnum = 0
    pickl()
    game = True
    while game:
        if turnnum > 8:
            game = "cats"
            turn = ""
        if turn == human:
            turn = computer
            printtable()
            print("Its your turn: ")
            position = int(input("Where would you like to set {}? ".format(human)))
            while not(isfree(table, position)):
                position = int(input("Where would you like to set {}? ".format(human)))
            setp(position, human)
            if winning(table, human):
                game = human
        elif turn == computer:
            turn = human
            print("Its AI's turn... ")
            val = aiset(table.copy(), computer)
            print(val)
            setp(int(val["index"]), computer)
            sleep(0.5)
            printtable()
            if winning(table, computer):
                game = computer
        turnnum += 1

    if game == human:
        print("You won! ")
    elif game == computer:
        print("You loose! ")
    elif game == "cats":
        print("its a tie! ")

[Sirius3]

@henridoh: »global« sollte in einem ordentlichen Programm nicht vorkommen. Alles was eine Funktion braucht, sollte sie über ihre Argumente bekommen, und die Ergebnisse per »return« zurückgeben.

»randlist« ist identisch zu »random.sample«. Der Vergleich in »isfree« liefert schon einen Wahrheitswert, da braucht man kein if-else. Der Wahrheitswert ist immer True, da ein Listenelement niemals eine Liste ist. In »pickl« solltest Du eine while-True mit Abbruch per break benutzen, statt »letter« mit einem Dummy-Wert zu belegen. »not« ist keine Funktion, die Klammerung also verwirrend, benutze »not in«. »human«, »computer« und »turn« sind wie schon geschrieben, Rückgabewerte. Der Rückgabewert von »setp« ist irritierend, weil nur ein Pfad einen expliziten Rückgabewert hat. In »winning« kann der Index von einer drei-elementigen Liste niemals 3 sein. »index« wirft auch zu oft einen ValueError, so dass die weiteren Tests gar nicht durchgeführt werden.

In »aiset« wenn man sowohl einen Index als auch die Elemente der Liste braucht, benutzt man »enumerate«. Die winning-if-Abfragen brauchen weder »av« noch »moves«, so dass man den Code davor nach unter schieben kann. »move["index"]« enthält immer nur ein Leerzeichen, weil das der Wert eines leeren Feldes ist. bestMove ermittelt man am einfachsten per min/max mit key-Argument.
"score" kann nur die Werte 10, -10 oder 0 annehmen, bestMove ist also irgendeine Kombination, wo Computer/Spieler gewinnt, auch wenn der Gegner bei dieser Kombination schon 3mal vorher gewonnen hätte.

»printtable« sollte table als Argument erhalten.

Alles was innerhalb des if-__name__ steht, sollte in einer Funktion »main« stehen, dann kommt man auch nicht in die Gefahr, aus Versehen, globale Variablen zu verwenden. »game« kann die Werte True, "cats", "X" oder "O" annehmen, was alles „wahr” ist, so dass die while-Schleife nie verlassen wird. Die while-not(...)-Schleife sollte eine while-True-Schleife sein, wie oben schon beschrieben.

[Sirius3]

Da man nicht einen einfachen Fehler bei aiset benennen kann, hier mal eine Lösungsvariante

Code: Alles auswählen

from itertools import cycle
from random import sample, choice

X = "X"
O = "O"
XO = [X, O]

def pickl():
    while True:
        human = input("Please pick {}: ".format(" or ".join(XO)))
        if human in XO:
            break
    return human

def winning(board):
    for i in [0, 3, 6]:
        if board[i]==board[i+1]==board[i+2]:
            return board[i]
    for i in [0, 1, 2]:
        if board[i]==board[i+3]==board[i+6]:
            return board[i]
    if board[0]==board[4]==board[8] or board[2]==board[4]==board[6]:
        return board[4]
    if all(c in XO for c in board):
        return "tie"
    return None

def aiset(board, player):
    moves = []
    for i, c in enumerate(board):
        if c in XO:
            continue
        board[i] = player
        winner = winning(board)
        if winner is None:
            other = X if player == O else O
            _, score = aiset(board, other)
            score /= -2
        elif winner == "tie":
            score = 0
        else:
            score = 1
        board[i] = i
        moves.append((i, score))
    best_move = max(moves, key=lambda x:x[1])
    return best_move

def printtable(table):
    for i in [0, 3, 6]:
        print("|{}|{}|{}|".format(table[i], table[i+1], table[i+2]))
    print("\n")

def main():
    table = list(range(9))
    human = pickl()
    turns = sample(XO, len(XO))
    print("{} beginns! ".format(turns[0]))
    for turn in cycle(turns):
        printtable(table)
        if turn == human:
            print("Its your turn: ")
            while True:
                try:
                    position = int(input("Where would you like to set {}? ".format(human)))
                except ValueError:
                    pass
                else:
                    if table[position] not in XO:
                        break
        else:
            print("Its AI's turn... ")
            if human not in table:
                # start with a random field
                position = choice(table)
            else:
                position, score = aiset(table, turn)
                print("Score", score)
        table[position] = turn
        winner = winning(table)
        if winner:
            break
    printtable(table)
    if winner == "tie":
        print("its a tie!")
    elif winner == human:
        print("You won!")
    else:
        print("You loose!")

if __name__ == "__main__":
    main()

[henridoh]

Danke, hast mir ein gutes beispiel gegeben, und auch dein erster post hat mit weitergeholfen