Why does my program take so long to run

[TheComputerdude]

from oWinner import oWin
from xWinner import xWin

xPos = []
oPos = []
open = [1,2,3,4,5,6,7,8,9]
class TicTacToeBrain :
    xPos = []
    oPos = []
    open = [1,2,3,4,5,6,7,8,9]
    def __init__(self, player = "x") :
        self._squares = {}
        self._copySquares = {}

    def getAvailableMoves(self,open) :
        return open

    def makeMove(self, position, player) :
        open.remove(position)
        if player == 'x':
            xPos.append(position)
        else:
            oPos.append(position)
    def undoMove(self, position, player) :
        open.append(position)
        if player == 'x':
            xPos.remove(position)
        else:
            oPos.remove(position)
    def complete(self,open) :
        # *** see above
        if len(open)==0:
            return True
        if self.getWinner(xPos,oPos,open) != None :
            return True
        return False

    def getWinner(self,xPos,oPos,open) :
        if xWin(xPos):
            return 'x'
        if oWin(oPos):
            return 'o'
        # *** see above
        if len(open) == 0:
            return "tie"
        return None

    def getEnemyPlayer(self, player) :
        if player == "x" :
            return "o"
        return "x"

    def minimax(self, player,open,xPos,oPos, depth = 0):
        if player == "o":
            best = -30
        else:
            best = 30
        if self.complete(open) :
            if self.getWinner(open,xPos,oPos) == "x" :
                # *** don't do this, you may still need the position to try other moves
                # self._squares = self._copySquares
                # *** value should be closer to zero for greater depth!
                # *** expect tuple return value
                return -30 + depth, None
            elif self.getWinner(open,xPos,oPos) == "tie" :
                # self._squares = self._copySquares
                # *** expect tuple return value
                return 0, None
            elif self.getWinner(open,xPos,oPos) == "o" :
                # self._squares = self._copySquares
                # *** value should be closer to zero for greater depth!
                # *** expect tuple return value
                return 30 - depth, None
            # *** Execution can never get here
        bestMove = None
        for move in self.getAvailableMoves(open) :
            # print (self.getAvailableMoves(open))
            # print (xPos)
            # print (oPos)
            self.makeMove(move, player)
            val, _ = self.minimax(self.getEnemyPlayer(player),open,xPos,oPos, depth+1)
            #print(val)
            # *** undo last move
            self.undoMove(move, player)
            if player == "o" :
                if val > best :
                    # *** Also keep track of the actual move
                    best, bestMove = val, move
            else :
                if val < best :
                    # *** Also keep track of the actual move
                    best, bestMove = val, move
        bestMove = bestMove
        return best, bestMove

    def printCopy(self) :
        print(self._copySquares)
game = TicTacToeBrain()
# val, bestMove = game.minimax("o",open,xPos,oPos)
# print ("best move", bestMove )
while game.complete:
    userInput = int(input("enter your move"))
    game.makeMove(userInput, 'x')
    val, bestMove = game.minimax("o",open,xPos,oPos)
    game.makeMove(bestMove, 'o')
    print (bestMove)

I am trying to create a minimax algoritm to play tictactoe. The functions I am calling outside of the file are fast. Why does it take so long to execute on the first time? What can I do to speed it up

[LtStaffel]

Where did owinner and xwinner imports come from? I want to run your script.

[TheComputerdude]

8 minutes ago, LtStaffel said:

Where did owinner and xwinner imports come from? I want to run your script.

They are my own custome functions  oWin:

def oWin(oPos):

    # Checks for across matches
    x= 1
    y= 1
    while x in range(1, 28):

        if  x in oPos and x + y in oPos and x + (y*2) in oPos:
            #print "o wins yay"
            x+=2002002

            #print"win"
            return True
            break
        else:
            x+=3
    #up down
    x= 1
    y= 3
    while x in range(1, 28):
        if x in range(1,4) or x in range(10,14) or x in range(19,24):
            if  x in oPos and x + y in oPos and x + (y*2) in oPos:
                #print "o wins yay"
                x+=2002002


                return True

            else:

                x+=1
        else:

            x+=1
    #vertical
    x= 1
    y= 9
    while x in range(1, 28):
        if  x in oPos and x + y in oPos and x + (y*2) in oPos:
            #print "o wins yay"

            #print"win"
            x+=2002002
            return True
        else:
            x+=1
    x= 3
    y= 2
    while x in range(1, 28):
        if  x in oPos and x + y in oPos and x + (y*2) in oPos:
            #print "o wins yay"

            x+=2002002
            return True
        else:
            x+=9
    x= 1
    y= 4
    while x in range(1, 28):
        if  x in oPos and x + y in oPos and x + (y*2) in oPos:
            #print "o wins yay"

            x+=2002002
            return True
        else:
            x+=9
    #DIAGONAL DIAGONAL VERTICAL

    x= 1
    y= 13
    x1=7
    y1=7
    while x in range (1,4):
        if  (x in oPos and x + y in oPos and x + (y*2) in oPos)or(x1 in oPos and x1 + y1 in oPos and x1 + (y1*2) in oPos):
            x+=900
            return True
        else:
            x+=2
            y-=2
            y1-=2
            x1+=2

    #ACROSS DIAGONAL VERTICAL

    x= 1
    y= 10

    while x in range (1,8):
        if  (x in oPos and x + y in oPos and x + (y*2) in oPos):
            x+=900
            return True
        else:
            x+=3
    x= 3
    y= 7
#above but compressed
    while x in range (3,10):
        if  (x in oPos and x + y in oPos and x + (y*2) in oPos):
            x+=900
            return True
        else:
            x+=3
    count = 1
    x=1
    y=12

    while x <= 3:
        if  (x in oPos and x + y in oPos and x + (y*2) in oPos):
            x+=900
            return True
        else:
            x+=1
    x=7
    y=6
    while x <= 9:
        if  (x in oPos and x + y in oPos and x + (y*2) in oPos):
            x+=900
            return True
        else:
            x+=1
    return False

They both are essentially the same they check if one has won.

xWin

import time
def xWin(xPos):

    # Checks for across matches
    x= 1
    y= 1
    while x in range(1, 28):

        if  x in xPos and x + y in xPos and x + (y*2) in xPos:
            #print "o wins yay"
            x+=2002002
            #print"win"
            return True
            break
        else:
            x+=3
    #up down
    x= 1
    y= 3
    while x in range(1, 28):
        if x in range(1,4) or x in range(10,14) or x in range(19,24):
            if  x in xPos and x + y in xPos and x + (y*2) in xPos:
                #print "o wins yay"
                x+=2002
                return True
                break
            else:

                x+=1
        else:

            x+=1
    #vertical
    x= 1
    y= 9
    while x in range(1, 28):
        if  x in xPos and x + y in xPos and x + (y*2) in xPos:
            #print "o wins yay"
            #print"win"
            x+=2002002
            return True
        else:
            x+=1
    x= 3
    y= 2
    while x in range(1, 28):
        if  x in xPos and x + y in xPos and x + (y*2) in xPos:
            #print "o wins yay"
            x+=2002002
            return True
        else:
            x+=9
    x= 1
    y= 4
    while x in range(1, 28):
        if  x in xPos and x + y in xPos and x + (y*2) in xPos:
            x+=2002002
            return True
        else:
            x+=9
    x= 1
    y= 13
    while x in range (1,4):
        if  x in xPos and x + y in xPos and x + (y*2) in xPos:
            x+=900
            return True
        else:
            x+=2
            y-=2
    #DIAGONAL DIAGONAL VERTICAL

    x= 1
    y= 13
    x1=7
    y1=7
    while x in range (1,4):
        if  (x in xPos and x + y in xPos and x + (y*2) in xPos)or(x1 in xPos and x1 + y1 in xPos and x1 + (y1*2) in xPos):
            x+=900
            return True
        else:
            x+=2
            y-=2
            y1-=2
            x1+=2

    #ACROSS DIAGONAL VERTICAL

    x= 1
    y= 10

    while x in range (1,8):
        if  (x in xPos and x + y in xPos and x + (y*2) in xPos):
            x+=900
            return True
        else:
            x+=3
    x= 3
    y= 7
#above but compressed
    while x in range (3,10):
        if  (x in xPos and x + y in xPos and x + (y*2) in xPos):
            x+=900
            return True
        else:
            x+=3
    count = 1
    x=1
    y=12

    while x <= 3:
        if  (x in xPos and x + y in xPos and x + (y*2) in xPos):
            x+=900
            return True
        else:
            x+=1
    x=7
    y=6
    while x <= 9:
        if  (x in xPos and x + y in xPos and x + (y*2) in xPos):
            x+=900
            return True
        else:
            x+=1


    return False

 

[TheComputerdude]

1 hour ago, gabrielcarvfer said:

Dude, this thing is the cause of it being slow. In a normal TicTacToe game, you can only have 8 configurations to win (123,456,789,147,258,369,159,357). Just change everything of that check to something like the following and you're done.
 

positions = [1,5,2,3,7,4]
solutions = [[1,2,3],[4,5,6],[7,8,9],[1,4,7],[2,5,8],[3,6,9],[1,5,9],[3,5,7]]


def won(positionList):
    global solutions
    for solution in solutions:
        if all(position in positionList for position in solution):
            return True
    return False

won(positions)

 

 

Tried that and it still takes a while for also I want to adapt it to 3d tic-tac-toe.

 

EDIT just saw your edit. How would you suggest I go about doing that also is there a good way to multithread this?

[TheComputerdude]

1 hour ago, gabrielcarvfer said:

To check the winner on 3d tic-tac-toe, is basically the same thing, just add more options to that list.

 

If you managed to make your code non-recursive, it would probably be much faster than the recursive version. Try to confine the minimax to a loop or 2 instead of calling itself.

 

You can precompute all possibilities, that you can easily make parallel, for example, precomputing those minimax scores in a tree for every starting move, and then stick together at the end to get a complete decision tree, that will have 9! possibilities for 2d 3x3 tic-tac-toe. You will probably want to save that tree for later use (using Pickle, for example) to prevent the recomputation of everything.

Is there a good way to automate the generating of the minimax trees cause at every depth level and w/ 3d tic tac toe... Not really sounding that fun

[Dat Guy]

15 hours ago, TheComputerdude said:

Why does it take so long to execute on the first time?

 

Because you write in Python.

 

15 hours ago, TheComputerdude said:

 What can I do to speed it up

 

Write in C.

 

Source: Own experience.

[VoxelProgrammer]

14 hours ago, Dat Guy said:

 

Because you write in Python.

 

 

Write in C.

 

Source: Own experience.

Cython man.  Just add the data types and compile with cython  it will provide near C speeds or better.

Though honestly I vote assembly.