Jump to content
  • Advertisement
Sign in to follow this  
vbuser1338

Possible bug in my code, python version dramatically slower

This topic is 4228 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I tried to prototype the AI for my game in python so I programmed a game of Tic Tac Toe as a refresher of MiniMax but the performance is very bad. It takes about 4.8 seconds to generate the first move. I coded up a c++ version quickly and it takes very little time to generate the move. I can't believe that the python version is that much slower. I compared the two codes and I don't see anything different. It could be I'm calling an expensive function in the python version that I am unaware of but I can't figure it out. I tried not using a list to generate the moves thinking that could be a bottle neck but that didn't shave much off the time. Should the python version be this much slower or is it something I've done wrong? Here is the code: C++
    Game::MiniMaxNode Game::miniMax() {
        return max();
    }

    Game::MiniMaxNode Game::max() {
        if (gameOver()) {
            // Get the score and return
            return Game::MiniMaxNode(evaluate());
        }
        else {
            Game::MiniMaxNode bestMove(-1000);

            for (int y = 0; y < Board::BOARD_SIZE; ++y) {
                for (int x = 0; x < Board::BOARD_SIZE; ++x) {
                    if (board.board[x][y] == EMPTY) {
                        board.board[x][y] = X;
                        Game::MiniMaxNode score = min();
                        if (score.score > bestMove.score) {
                            bestMove.score = score.score;
                            bestMove.x = x;
                            bestMove.y = y;
                        }
                        board.board[x][y] = EMPTY;
                    }
                }
            }

            return bestMove;
        }
    }

    Game::MiniMaxNode Game::min() {
        if (gameOver()) {
            // Get the score and return
            return Game::MiniMaxNode(evaluate());
        }
        else {
            Game::MiniMaxNode bestMove(1000);

            for (int y = 0; y < Board::BOARD_SIZE; ++y) {
                for (int x = 0; x < Board::BOARD_SIZE; ++x) {
                    if (board.board[x][y] == EMPTY) {
                        board.board[x][y] = O;
                        Game::MiniMaxNode score = max();
                        if (score.score < bestMove.score) {
                            bestMove.score = score.score;
                            bestMove.x = x;
                            bestMove.y = y;
                        }
                        board.board[x][y] = EMPTY;
                    }
                }
            }

            return bestMove;
        }
    }

    int Game::evaluate() const {
        // Return positive if x wins, negative if o wins and 0 if its a tie
        ++eval;
        Winner winner = getWinner();
        if (winner == X_WIN) {
            return 1;
        }
        else if (winner == O_WIN) {
            return -1;
        }
        else {
            return 0;
        }
    }

    bool Game::gameOver() const {
        if (board.isFull()) {
            return true;
        }
        else {
            // Check for winner
            Winner winner = getWinner();
            if (winner == X_WIN || winner == O_WIN) {
                return true;
            }
        }

        // Game not over
        return false;
    }

    Game::Winner Game::getWinner() const {
        // Check horizontally
        for (int y = 0; y < Board::BOARD_SIZE; ++y) {
            if (board.board[0][y] != EMPTY && board.board[0][y] == board.board[1][y] && board.board[1][y] == board.board[2][y]) {
                return convertWinner(board.board[0][y]);
            }
        }

        // Check veritcally
        for (int x = 0; x < Board::BOARD_SIZE; ++x) {
            if (board.board[x][0] != EMPTY && board.board[x][0] == board.board[x][1] && board.board[x][1] == board.board[x][2]) {
                return convertWinner(board.board[x][0]);
            }
        }

        // Check diagonals
        if (board.board[0][0] != EMPTY && board.board[0][0] == board.board[1][1] && board.board[1][1] == board.board[2][2]) {
                return convertWinner(board.board[0][0]);
        }
        else if (board.board[2][0] != EMPTY && board.board[2][0] == board.board[1][1] && board.board[1][1] == board.board[0][2]) {
                return convertWinner(board.board[2][0]);
        }

        // No winner so if game is over then its a tie or else there is no winner
        if (board.isFull()) {
            return TIE;
        }
        else {
            return NONE;
        }
    }

    Game::Winner Game::convertWinner(TileType type) const {
        // Convert the tile type to a winner
        if (type == X) {
            return X_WIN;
        }
        else if (type == O) {
            return O_WIN;
        }
        else {
            throw std::logic_error("Invalid tile type to convert to winner");
        }
    }


Python
	def _getInput(self, events): 
		""" Handles the input for the game """
		for event in events: 
			if event.type == QUIT: 
				self.running = False
			elif event.type == MOUSEBUTTONDOWN:
				# Move the player
				pos = pygame.mouse.get_pos()
				xTile = (pos[0] - self.boardOffset[0]) / 30
				yTile = (pos[1] - self.boardOffset[1]) / 30 
				if (0 <= xTile < 3) and (0 <= yTile < 3):
					self.board[xTile, yTile] = Board.O
					
					# If game is not over move computer
					if not self._gameOver():
						t = time.time()
						move = self._miniMax()
						self.board[move[0], move[1]] = Board.X
						print "Took ", (time.time() - t) * 1000, "ms"

	def _evaluate(self):
		""" 
		Evalutes the score for the game and returns a large positive
		if X wins, a large negative if Y wins and 0 if there is no winner
		or it is a tie
		"""
		winner = self._getWinner()
		if winner == Board.X:
			return 1
		elif winner == Board.O:
			return -1
		else:
			return 0

	def _getWinner(self):
		""" Returns the winner of the game """
				
		# Check horizontally
		for y in range(3):
			if (self.board[0, y] != Board.EMPTY) and (self.board[0, y] == self.board[1, y] == self.board[2, y]):
				return self.board[0, y]
		
		# Check vertically
		for x in range(3):
			if (self.board[x, 0] != Board.EMPTY) and (self.board[x, 0] == self.board[x, 1] == self.board[x, 2]):
				return self.board[x, 0]
		
		# Check diagonally
		if (self.board[0, 0] != Board.EMPTY) and (self.board[0, 0] == self.board[1, 1] == self.board[2, 2]):
			return self.board[0, 0]
		elif (self.board[2, 0] != Board.EMPTY) and (self.board[2, 0] == self.board[1, 1] == self.board[0, 2]):
			return self.board[2, 0]
	
		
		# Tie or no one won
		return None
		
	def _miniMax(self):
		_, move = self._max()
		return move

	def _max(self):		
		if self._gameOver():
			return self._evaluate(), [0, 0]
		else:
			bestScore = -10000
			bestMove = [0, 0]
			validMoves = self._generateMoves()
			for validMove in validMoves:
				self.board[validMove[0], validMove[1]] = Board.X
				score, _ = self._min()
				
				if score > bestScore:
					bestScore = score	
					bestMove = validMove	
				self.board[validMove[0], validMove[1]] = Board.EMPTY
			return bestScore, bestMove
				
	def _min(self):
		if self._gameOver():
			return self._evaluate(), [0, 0]
		else:
			bestScore = 10000
			bestMove = [0, 0]
			validMoves = self._generateMoves()
			for validMove in validMoves:
				self.board[validMove[0], validMove[1]] = Board.O
				score, _ = self._max()
								
				if score < bestScore:
					bestScore = score	
					bestMove = validMove	
				self.board[validMove[0], validMove[1]] = Board.EMPTY
			return bestScore, bestMove
				
	def _gameOver(self):
		""" Returns true if the game is over and false otherwise """
		winner = self._getWinner()
		if winner == Board.X or winner == Board.O or self.board.isFull():
			# Game over
			return True
			
		# Game not over
		return False
	
	def _generateMoves(self):
		""" Returns a list of valid moves on a board """
		moves = []
		for y in range(3):
			for x in range(3):
				if self.board[x, y] == Board.EMPTY:
					moves.append((x, y))
		
		return moves


Can anyone explain this? Thanks, vbuser

Share this post


Link to post
Share on other sites
Advertisement
I think this is mostly a case of python being slower than compiled code.

Profiling shows that most of the time is spent in the _getWinner method, followed by _generateMoves (at least given the way I implemented the board class). There are several optimizations that improve the running time (eliminating unnecessary function calls).

How fast does C++ generate the move? Is it at least within a factor of 10 or 20?

Share this post


Link to post
Share on other sites
self.board[x, 0]

I don't like the look of that. Did you overload __getitem__ or whatever it is in the board class to take a tuple?

The implementation of your board class is important here. That lookup could be quite slow. There are other optimisations to be made, but this access looks like the main one.

Share this post


Link to post
Share on other sites
Oh, it looks like Kylotan is correct. I had tried to keep the code as close as possible as what was posted to test it, so I used numpy arrays to get the tuple item indexing. Replacing that with an ordinary list of lists caused a huge speed increase. Hmmm...why didn't the profiler catch that? Maybe because I'm still using python 2.4?

Share this post


Link to post
Share on other sites
Thanks, the main problem was the __getitem__ method. It was declared to take a tuple but for every access I had two __getitem__ lookups plus one on the regular list because the board contained a custom class MultiArray that contained the list of tiles. I changed this to a single list and it took just over 1 second to do the first lookup. I'm sure there are many other optimisations I can make to get better performance. I didn't think the lookups would be that expensive.

Thanks again for the help,
vbuser

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!