diff options
| -rw-r--r-- | doc/diagrams/GameBoard.pumlc | 28 | ||||
| -rw-r--r-- | doc/diagrams/GameMove.pumlc | 20 | ||||
| -rw-r--r-- | doc/diagrams/GameState.pumlc | 16 | ||||
| -rw-r--r-- | doc/diagrams/GameTree.pumlc | 4 | ||||
| -rw-r--r-- | doc/diagrams/gameRepresentation.puml | 9 | ||||
| -rw-r--r-- | doc/diagrams/gtpEngine.puml | 15 | ||||
| -rw-r--r-- | doc/tex/implementation.tex | 34 | ||||
| -rw-r--r-- | doc/tex/previousWorks.tex | 15 | ||||
| -rw-r--r-- | doc/tex/tfg.tex | 4 | ||||
| -rwxr-xr-x | go.py | 4 | ||||
| -rw-r--r-- | imago/engine/core.py | 19 | ||||
| -rw-r--r-- | imago/engine/monteCarlo.py | 91 | ||||
| -rw-r--r-- | imago/engine/parseHelpers.py | 9 | ||||
| -rw-r--r-- | imago/gameLogic/gameBoard.py | 148 | ||||
| -rw-r--r-- | imago/gameLogic/gameMove.py | 68 | ||||
| -rw-r--r-- | imago/gameLogic/gameState.py | 10 | ||||
| -rw-r--r-- | tests/test_gameBoard.py | 84 | ||||
| -rw-r--r-- | tests/test_gameMove.py | 78 | ||||
| -rw-r--r-- | tests/test_monteCarlo.py | 22 |
19 files changed, 513 insertions, 165 deletions
diff --git a/doc/diagrams/GameBoard.pumlc b/doc/diagrams/GameBoard.pumlc new file mode 100644 index 0000000..7a57b2d --- /dev/null +++ b/doc/diagrams/GameBoard.pumlc @@ -0,0 +1,28 @@ +@startuml + +class GameBoard { + int[][] board + int capturesBlack + int capturesWhite + + getBoard(self) + getBoardHeight(self) + getBoardWidth(self) + getDeepCopy(self) + getGroupLiberties(self, row, col) + getGroupLibertiesCount(self, row, col) + getGroupCells(self, row, col) + getGroupCellsCount(self, row, col) + moveAndCapture(self, row, col, player) + isMoveInBoardBounds(self, row, col) + isCellEmpty(self, row, col) + isCellEye(self, row, col) + isMoveSuicidal(self, row, col, player) + isMoveKoIllegal(self, row, col, player, prevBoards) + isPlayable(self, row, col, player, prevBoards) + score(self) + equals(self, otherBoard) + printBoard(self) +} + +@enduml diff --git a/doc/diagrams/GameMove.pumlc b/doc/diagrams/GameMove.pumlc index 7dcb5e3..0f75edd 100644 --- a/doc/diagrams/GameMove.pumlc +++ b/doc/diagrams/GameMove.pumlc @@ -1,13 +1,23 @@ @startuml class GameMove { - int player - int row - int col - int[2] makesKo - int[] board + GameBoard board GameMove[] nextMoves GameMove previousMove + boolean isPass + int[2] coords + + getRow(self) + getCol(self) + getPlayer(self) + getNextPlayer(self) + getGameLength(self) + getThisAndPrevBoards(self) + getPlayableVertices(self) + addMove(self, row, col) + addMoveForPlayer(self, row, col, player) + addPass(self) + printBoard(self) } @enduml diff --git a/doc/diagrams/GameState.pumlc b/doc/diagrams/GameState.pumlc index db39d8f..38e1397 100644 --- a/doc/diagrams/GameState.pumlc +++ b/doc/diagrams/GameState.pumlc @@ -1,14 +1,18 @@ @startuml class GameState { - int player - int capturesBlack - int capturesWhite - List board - List prevBoards # for ko + int size GameTree gameTree GameMove lastMove - GameData gameData + 'GameData gameData + + getCurrentPlayer(self) + getPlayerCode(self) + getBoard(self) + playMove(self, row, col) + playMoveForPlayer(self, row, col, player) + playPass(self) + undo(self) } @enduml diff --git a/doc/diagrams/GameTree.pumlc b/doc/diagrams/GameTree.pumlc index 85859d8..10b9251 100644 --- a/doc/diagrams/GameTree.pumlc +++ b/doc/diagrams/GameTree.pumlc @@ -1,8 +1,8 @@ @startuml class GameTree { - GameNode[] firstMoves - GameData gameData + GameMove[] firstMoves + 'GameData gameData } @enduml diff --git a/doc/diagrams/gameRepresentation.puml b/doc/diagrams/gameRepresentation.puml index 9a869f1..db5d5a5 100644 --- a/doc/diagrams/gameRepresentation.puml +++ b/doc/diagrams/gameRepresentation.puml @@ -5,10 +5,13 @@ !include GameState.pumlc !include GameTree.pumlc !include GameMove.pumlc +!include GameBoard.pumlc -GameState --> GameTree -GameState --> GameMove: Current move +GameState -> GameTree +GameState --> GameMove: Last move GameTree *--> GameMove -GameMove -> GameMove +GameMove --> GameMove: Previous move +GameMove *--> GameMove: Next moves +GameBoard <- GameMove @enduml diff --git a/doc/diagrams/gtpEngine.puml b/doc/diagrams/gtpEngine.puml index c4caf32..5b098da 100644 --- a/doc/diagrams/gtpEngine.puml +++ b/doc/diagrams/gtpEngine.puml @@ -2,13 +2,20 @@ !include skinparams.puml -class EngineCore { -} - class IO { processComand() } +class EngineCore { + setBoardsize() + clearBoard() + setKomi() + setFixedHandicap() + play() + genmove() + undo() +} + !include GameState.pumlc 'class EngineBoard { @@ -22,7 +29,7 @@ class EngineAI { genmove(board) } -EngineCore --> IO +IO --> EngineCore EngineCore --> GameState EngineCore --> EngineAI diff --git a/doc/tex/implementation.tex b/doc/tex/implementation.tex index 9e42313..28fd0ec 100644 --- a/doc/tex/implementation.tex +++ b/doc/tex/implementation.tex @@ -2,9 +2,23 @@ \subsection{Engine} -An engine implementing GTP.\@ It is designed to be used by a software controller +An implementation of GTP, that is, the piece of software which offers the GTP +interface to other applications.\@ It is designed to be used by a software controller but can also be directly run, mostly for debugging purposes. Its design is shown -in \fref{fig:engine} +in \fref{fig:engine}. The core of the engine is related with three components, +each with a separate responsibility: + +\begin{itemize} + \item The IO component is the one called from other applications and offers + the text interface. It reads and processes input and calls corresponding + commands from the core of the engine. + \item The EngineBoard component stores the state of the match, recording + information such as the history of boards positions and whose turn goes + next. The engine core uses it for these state-storing purposes. + \item The EngineAI component is responsible of analyzing the match and + generate moves. The engine core uses it when a decision has to be made + by the AI, such as when a move needs to be generated by the engine. +\end{itemize} \begin{figure}[h] \begin{center} @@ -28,14 +42,16 @@ moves. One module to read and write SGF files. Modules are shown in \subsection{Representation of a match} -Strictly said, a match is composed of a series of moves. But since game review -and variants exploration is an important part of Go learing, \program{} allows -for navigation back and forth through the board states of a match and for new +A regular Go match is composed of a list of moves. But since game review and +variants exploration is an important part of Go learning, \program{} allows for +navigation back and forth through the board states of a match and for new variants to be created from each of these board states. Therefore, a match is -represented as a tree of moves. The state of the game must also be present so -liberties, captures and legality of moves can be addressed, so it is represented -with its own class, which holds a reference both to the game tree and the -current move. This classes and their relationship can be seen in +represented as a tree of moves. The state of the board at any given move must +also be stored so liberties, captures count and legality of moves can be +addressed, so it is represented with its own class, which holds a reference both +to the game tree and the current move. Moves depend on a representation of the +game board to have access to its current layout and count of captured stones. +These classes and their relationships can be seen in \fref{fig:gameRepresentation}. \begin{figure}[h] diff --git a/doc/tex/previousWorks.tex b/doc/tex/previousWorks.tex index 6ba5dce..6e503a3 100644 --- a/doc/tex/previousWorks.tex +++ b/doc/tex/previousWorks.tex @@ -2,12 +2,13 @@ \subsection{SGF} -SGF (\textit{Smart Go Format} or \textit{Smart Game Format}) is a text file -format specification for records of games or even collections of them. It was -devised for Go but it supports other games with similar turns structure. It -supports move variations, annotations, setups and game metadata. By supporting -SGF, our application can be used to analyse existing games registered by other -applications, such as those played on online Go servers. +SGF (\textit{Smart Go Format} or, in a more general context, \textit{Smart Game +Format}) is a text file format specification for records of games or collections +of them. It was devised for Go but it supports other games with similar +turn-based structure. It supports move variations, annotations, setups and game +metadata. By supporting SGF our application can be used to analyse existing +games registered by other applications, such as those played on online Go +servers. The SGF specification can be found at \url{https://www.red-bean.com/sgf/user_guide/index.html} @@ -17,5 +18,5 @@ The SGF specification can be found at GTP (\textit{Go Text Protocol}) is a text based protocol for communication with computer go programs. [ref https://www.lysator.liu.se/~gunnar/gtp/] It is the protocol used by GNU Go and the more modern and powerful KataGo. By supporting -GTP, our application can be used with existing GUIs and other programs, making +GTP our application can be used with existing GUIs and other programs, making it easier to use it with the tools users are already familiar with. diff --git a/doc/tex/tfg.tex b/doc/tex/tfg.tex index 9248748..a14708d 100644 --- a/doc/tex/tfg.tex +++ b/doc/tex/tfg.tex @@ -23,7 +23,7 @@ %\renewcommand{\contentsname}{Contenidos} %\renewcommand{\figurename}{Figura} -\newcommand{\program}{Go-AI} +\newcommand{\program}{Imago} \newcommand{\inputtex}[1]{\input{tex/#1}} \newcommand{\fref}[1]{Fig.~\ref{#1}} @@ -33,7 +33,7 @@ \frenchspacing -\title{\program} +\title{\program: An AI capable of playing the game of Go} \author{Íñigo Gutiérrez Fernández} @@ -7,8 +7,8 @@ from imago.gameLogic.gameState import GameState if __name__ == "__main__": - #GAMESTATE = GameState(5) - GAMESTATE = GameState(19) + GAMESTATE = GameState(5) + #GAMESTATE = GameState(19) while 1: diff --git a/imago/engine/core.py b/imago/engine/core.py index 0960319..48af241 100644 --- a/imago/engine/core.py +++ b/imago/engine/core.py @@ -5,7 +5,7 @@ from random import randrange from imago.data.enums import Player from imago.gameLogic.gameState import GameState -DEF_SIZE = 19 +DEF_SIZE = 7 DEF_KOMI = 5.5 class GameEngine: @@ -33,7 +33,7 @@ class GameEngine: self.komi = komi def setFixedHandicap(self, stones): - """Sets handicap stones in fixed vertexes.""" + """Sets handicap stones in fixed vertices.""" if stones < 1 or stones > 9: raise Exception("Wrong number of handicap stones") # TODO: Set handicap stones @@ -41,22 +41,35 @@ class GameEngine: def play(self, color, vertex): """Plays in the vertex passed as argument""" + if vertex == "pass": + self.gameState.passForPlayer(color) + return row = vertex[0] col = vertex[1] self.gameState.playMoveForPlayer(row, col, color) def genmove(self, color): """The key of this TFG.""" + + # Get valid vertices to play at validCells = [] board = self.gameState.getBoard().board size = self.gameState.size for row in range(size): for col in range(size): if board[row][col] == Player.EMPTY: - validCells.append([row, col]) + # Don't play on eyes! + if ( self.gameState.getBoard().getGroupCellsCount(row, col) != 1 + and self.gameState.getBoard().isCellEye(row, col) == Player.EMPTY ): + validCells.append([row, col]) + # Pass if no valid vertices + # Select a random vertex randIndex = randrange(0, len(validCells)) move = validCells[randIndex] self.gameState.playMoveForPlayer(move[0], move[1], color) + # NOTA: Esto usa gameState para hacer play, y en monteCarlo.py se usa GameMove + # para hacer add. Incoherente. Idealmente monteCarlo.py usaría un GameState en vez + # de acceder a los GameMove y gestionar un árbol... return move def undo(self): diff --git a/imago/engine/monteCarlo.py b/imago/engine/monteCarlo.py index 13f5c47..6e5d54d 100644 --- a/imago/engine/monteCarlo.py +++ b/imago/engine/monteCarlo.py @@ -8,37 +8,11 @@ class MCTS: def selection(self): """Select the most promising node with unexplored children.""" - bestUCB = 0 - bestNode = None - bestUCB, bestNode = self._selectionRec(self.root, bestUCB, bestNode) + bestNode = self.root.selectionRec(self.root) return bestNode - def __selectionRec(self, node, bestUCB, bestNode): - - # Check if node has unexplored children and better UCB than previously explored - if len(node.unexploredVertices) > 0: - ucb = node.ucb() - if ucb > bestUCB: - bestUCB = ucb - bestNode = node - - # Recursively search children for better UCB - for child in node.children: - bestUCB, bestNode = self._selectionRec(child, bestUCB, bestNode) - - return bestUCB, bestNode - - def expansion(self, node): - # Get a random unexplored vertex and remove it from the set - newVertex = node.unexploredVertices.pop() - newNode = MCTSNode(newVertex[0], newVertex[1], node) - parent.children.add(self) - return newNode - - def simulation(self, node): - def backup(self, node): - + """Update nodes backbards up to root.""" class MCTSNode: """Monte Carlo tree node.""" @@ -53,7 +27,66 @@ class MCTSNode: def ucb(self): """Returns Upper Confidence Bound of node""" - # meanVictories + 1/visits + # UCB = meanVictories + 1/visits mean = self.score / self.visits adjust = 1/self.visits return mean + adjust + + def selectionRec(self, bestNode): + """Searches this node and its children for the node with the best UCB value.""" + + # Check if node has unexplored children and better UCB than previously explored + if len(self.unexploredVertices) > 0: + if self.ucb() > bestNode.ucb(): + bestNode = self + + # Recursively search children for better UCB + for child in self.children: + bestNode = child.selectionRec(bestNode) + + return bestNode + + def expansion(self): + """Pick an unexplored vertex from this node and add it as a new MCTSNode.""" + newVertex = self.unexploredVertices.pop() # Random? + newMove = self.move.addMove(newVertex[0], newVertex[1]) + newNode = MCTSNode(newMove, self) + self.children.add(newNode) + return newNode + + def simulation(self): + """Play random matches to accumulate reward information on the node.""" + matches = 10 + for _ in range(matches): + result = self._randomMatch() + self.visits += 1 + scoreDiff = result[0]-result[1] + self.score += scoreDiff / abs(scoreDiff) + self._printBoardInfo() + + def _randomMatch(self): + """Play a random match and return the resulting score.""" + #IMPORTANT: the score heuristic doesn't work for the first move of the game, since + #the black player holds all except for one vertex! + currentMove = self.move + scoreHeuristic = 15 + score = currentMove.board.score() + while currentMove.getGameLength() < 5 or abs(score[0] - score[1]) < scoreHeuristic: + validMoves = currentMove.getPlayableVertices() + selectedMove = validMoves.pop() + currentMove = currentMove.addMove(selectedMove[0], selectedMove[1]) + print("Current move: %d, %d" % (currentMove.getRow(), currentMove.getCol())) + print("Current move game length: ", currentMove.getGameLength()) + score = currentMove.board.score() + print("Score of the board: %d, %d (%d)" + % (score[0], + score[1], + score[0]-score[1]) + ) + currentMove.printBoard() + return score + + def _printBoardInfo(self): + """Prints the visits and score for debugging purposes.""" + print("Visits: %d" % self.visits) + print("Score: %d" % self.score) diff --git a/imago/engine/parseHelpers.py b/imago/engine/parseHelpers.py index 32f0753..59e0496 100644 --- a/imago/engine/parseHelpers.py +++ b/imago/engine/parseHelpers.py @@ -21,7 +21,7 @@ class ParseCodes(Enum): QUIT = enumAuto() def parseMove(args, boardsize): - """Converts the textual input of a move to a move instance.""" + """Converts the textual representation of a move to a move instance.""" if len(args) != 2: print("[ERROR] - Wrong n of args for move") return ParseCodes.ERROR @@ -40,7 +40,8 @@ def parseColor(text): return ParseCodes.ERROR def parseVertex(text, boardSize): - """Returns row and column of a vertex given its input string. + """Returns row and column of a vertex given its input string. A vertex can also be the + string "pass". GTP uses A1 style notation: columns are letters left to right, rows are number bottom to top. @@ -48,6 +49,8 @@ def parseVertex(text, boardSize): text = text.upper() if not re.match("^[A-HJ-Z][1-9][0-9]*$", text): + if text == "PASS": + return "pass" return ParseCodes.ERROR vertexCol = ord(text[0]) @@ -70,6 +73,8 @@ def vertexToString(vertex, boardSize): GTP uses A1 style notation: columns are letters left to right, rows are number bottom to top. """ + if vertex == "pass": + return "pass" if len(vertex) != 2: return ParseCodes.ERROR if vertex[0] >= boardSize or vertex[1] >= boardSize or vertex[0] < 0 or vertex[1] < 0: diff --git a/imago/gameLogic/gameBoard.py b/imago/gameLogic/gameBoard.py index c6a6007..eaa1545 100644 --- a/imago/gameLogic/gameBoard.py +++ b/imago/gameLogic/gameBoard.py @@ -20,7 +20,10 @@ class GameBoard: self.board = _getNewBoard(height, width) self.capturesBlack = 0 self.capturesWhite = 0 - self.lastStone = None + + def getBoard(self): + """Gets the matrix representing the board.""" + return self.board def getBoardHeight(self): """Returns the number of rows in the board.""" @@ -31,27 +34,16 @@ class GameBoard: be the same for all the rows.""" return len(self.board[0]) - def getLastPlayer(self): - """Returns the player who placed the last stone.""" - if self.lastStone is None: - return Player.EMPTY - return self.board[self.lastStone[0]][self.lastStone[1]] - def getDeepCopy(self): """Returns a copy GameBoard.""" newBoard = GameBoard(self.getBoardHeight(), self.getBoardWidth()) newBoard.capturesBlack = self.capturesBlack newBoard.capturesWhite = self.capturesWhite - newBoard.lastStone = self.lastStone newBoard.board = deepcopy(self.board) return newBoard - def getGroupLibertiesCount(self, row, col): - """Returns the number of liberties of a group.""" - return len(self.getGroupLiberties(row, col)) - def getGroupLiberties(self, row, col): - """Returns the empty vertexes adjacent to the group occupying a vertex (its + """Returns the empty vertices adjacent to the group occupying a vertex (its liberties) as a set. An empty set is returned if the vertex is empty. """ groupColor = self.board[row][col] @@ -62,6 +54,10 @@ class GameBoard: self.__exploreLiberties(row, col, groupColor, emptyCells, exploredCells) return emptyCells + def getGroupLibertiesCount(self, row, col): + """Returns the number of liberties of a group.""" + return len(self.getGroupLiberties(row, col)) + def __exploreLiberties(self, row, col, groupColor, emptyCells, exploredCells): """Adds surrounding empty cells to array if they have not been added yet and explores adjacent occupied cells of the same group. @@ -78,51 +74,36 @@ class GameBoard: emptyCells.add((row, col)) return - # Up - if row > 0: - self.__exploreLiberties(row-1, col, groupColor, emptyCells, exploredCells) - - # Right - if col < self.getBoardWidth()-1: - self.__exploreLiberties(row, col+1, groupColor, emptyCells, exploredCells) - - # Down - if row < self.getBoardHeight()-1: - self.__exploreLiberties(row+1, col, groupColor, emptyCells, exploredCells) - - # Left - if col > 0: - self.__exploreLiberties(row, col-1, groupColor, emptyCells, exploredCells) + for side in ((-1,0), (1,0), (0,-1), (0,1)): + rowToExplore = row + side[0] + colToExplore = col + side[1] + if self.isMoveInBoardBounds(rowToExplore, colToExplore): + self.__exploreLiberties(rowToExplore, colToExplore, groupColor, + emptyCells, exploredCells) def getGroupCells(self, row, col): - """Returns a set containing the cells occupied by the group in the given cell.""" + """ + Returns a set containing the cells occupied by the group in the given cell. + This is also valid if the cell is empty.""" groupColor = self.board[row][col] - if groupColor == Player.EMPTY: - return 0 cells = set() self.__exploreGroup(row, col, groupColor, cells) return cells + def getGroupCellsCount(self, row, col): + """Returns the number of cells of a group.""" + return len(self.getGroupCells(row, col)) + def __exploreGroup(self, row, col, groupColor, cells): if self.board[row][col] != groupColor or (row, col) in cells: return cells.add((row, col)) - # Up - if row > 0: - self.__exploreGroup(row-1, col, groupColor, cells) - - # Right - if col < self.getBoardWidth()-1: - self.__exploreGroup(row, col+1, groupColor, cells) - - # Down - if row < self.getBoardHeight()-1: - self.__exploreGroup(row+1, col, groupColor, cells) - - # Left - if col > 0: - self.__exploreGroup(row, col-1, groupColor, cells) + for side in ((-1,0), (1,0), (0,-1), (0,1)): + rowToExplore = row + side[0] + colToExplore = col + side[1] + if self.isMoveInBoardBounds(rowToExplore, colToExplore): + self.__exploreGroup(rowToExplore, colToExplore, groupColor, cells) def moveAndCapture(self, row, col, player): """Checks surrounding captures of a move, removes them and returns a set @@ -130,33 +111,17 @@ class GameBoard: """ self.board[row][col] = player - self.lastStone = [row, col] captured = set() - if row > 0: - if (self.board[row-1][col] != player - and self.board[row-1][col] != Player.EMPTY - and len(self.getGroupLiberties(row-1, col)) == 0): - captured.update(self.__captureGroup(row-1, col)) - - if row < self.getBoardHeight()-1: - if (self.board[row+1][col] != player - and self.board[row+1][col] != Player.EMPTY - and len(self.getGroupLiberties(row+1, col)) == 0): - captured.update(self.__captureGroup(row+1, col)) - - if col > 0: - if (self.board[row][col-1] != player - and self.board[row][col-1] != Player.EMPTY - and len(self.getGroupLiberties(row, col-1)) == 0): - captured.update(self.__captureGroup(row, col-1)) - - if col < self.getBoardWidth()-1: - if (self.board[row][col+1] != player - and self.board[row][col+1] != Player.EMPTY - and len(self.getGroupLiberties(row, col+1)) == 0): - captured.update(self.__captureGroup(row, col+1)) + for side in ((-1,0), (1,0), (0,-1), (0,1)): + rowToExplore = row + side[0] + colToExplore = col + side[1] + if self.isMoveInBoardBounds(rowToExplore, colToExplore): + if (self.board[rowToExplore][colToExplore] != player + and self.board[rowToExplore][colToExplore] != Player.EMPTY + and self.getGroupLibertiesCount(rowToExplore, colToExplore) == 0): + captured.update(self.__captureGroup(rowToExplore, colToExplore)) return captured @@ -177,6 +142,29 @@ class GameBoard: """Returns True if cell is empty, false otherwise.""" return self.board[row][col] == Player.EMPTY + def isCellEye(self, row, col): + """Returns the surrounding color if the cell is part of an eye and Player.EMTPY + otherwise. + """ + # if isCellEmpty && all adjacent to group are same color + if not self.isCellEmpty(row, col): + return Player.EMPTY + groupCells = self.getGroupCells(row, col) + surroundingColor = Player.EMPTY + # Check surrounding cells of each cell in the group + for cell in groupCells: + for side in ((-1,0), (1,0), (0,-1), (0,1)): + rowChecked = cell[0]+side[0] + colChecked = cell[1]+side[1] + if self.isMoveInBoardBounds(rowChecked, colChecked): + otherColor = self.board[rowChecked][colChecked] + if otherColor != Player.EMPTY: + if surroundingColor == Player.EMPTY: + surroundingColor = otherColor + elif surroundingColor != otherColor: + return Player.EMPTY + return surroundingColor + def isMoveSuicidal(self, row, col, player): """Returns True if move is suicidal.""" @@ -238,6 +226,26 @@ class GameBoard: return False, "Illegal by ko rule." return True, "" + def score(self): + """Gets the current score given by the already surrounded territory for Japanese + rules. The format of the returned score is (black, white). + """ + scores = [] + for player in Player: + while len(scores) <= player.value: + scores.append(0) + checkedVertices = set() + for row in range(0, self.getBoardHeight()): + for col in range(0, self.getBoardWidth()): + if not (row, col) in checkedVertices: + group = self.getGroupCells(row, col) + for cell in group: + checkedVertices.add(cell) + surroundingColor = self.isCellEye(row, col) + if surroundingColor != Player.EMPTY: + scores[surroundingColor.value] += len(group) + return (scores[Player.BLACK.value], scores[Player.WHITE.value]) + def equals(self, otherBoard): """Returns true if this board is equal to another board. Only takes into account dimensions and placed stones. diff --git a/imago/gameLogic/gameMove.py b/imago/gameLogic/gameMove.py index 90ec4bf..224e120 100644 --- a/imago/gameLogic/gameMove.py +++ b/imago/gameLogic/gameMove.py @@ -7,22 +7,52 @@ class GameMove: Tree: the board can be empty, or the move can consist of more than one added or removed stones.""" - def __init__(self, player, board): + def __init__(self, board, coords=None, isPass=False): self.board = board self.nextMoves = [] self.previousMove = None + self.isPass = isPass + self.coords = coords def getRow(self): """Returns the row of the vertex the move was played on.""" - return self.board.lastStone[0] + if self.coords is None: + return None + return self.coords[0] def getCol(self): """Returns the column of the vertex the move was played on.""" - return self.board.lastStone[1] + if self.coords is None: + return None + return self.coords[1] - def getLastPlayer(self): - """Returns the player who placed the last stone.""" - return self.board.getLastPlayer() + def getPlayer(self): + """Returns the player who placed the last stone or passed.""" + if self.isPass: + if self.previousMove is None: + return Player.BLACK + return Player.otherPlayer(self.previousMove.getPlayer()) + + if self.coords is None: # Not pass and no coordinates: root move of the tree + return Player.EMPTY + + return self.board.getBoard()[self.getRow()][self.getCol()] + + def getNextPlayer(self): + """Returns the player who should place the next stone.""" + selfPlayer = self.getPlayer() + if selfPlayer == Player.EMPTY: + return Player.BLACK + return Player.otherPlayer(selfPlayer) + + def getGameLength(self): + """Returns the number of (actual player-made) moves since the game started.""" + acc = 0 + prevMove = self.previousMove + while prevMove is not None: + acc += 1 + prevMove = prevMove.previousMove + return acc def getThisAndPrevBoards(self): """Returns an array with all the boards of this and previous moves.""" @@ -36,21 +66,23 @@ class GameMove: def getPlayableVertices(self): """Returns a set with the playable vertices.""" playables = set() - player = Player.otherPlayer(self.getLastPlayer()) + player = self.getNextPlayer() prevBoards = self.getThisAndPrevBoards() for row in range(self.board.getBoardHeight()): for col in range(self.board.getBoardWidth()): - if self.board.isPlayable(row, col, player, prevBoards): + isPlayable, _ = self.board.isPlayable(row, col, player, prevBoards) + if isPlayable: playables.add((row, col)) + return playables def addMove(self, row, col): """Adds a move to the next moves list creating its board from this move's board plus a new stone at the specified row and column. """ - if self.getLastPlayer() == Player.EMPTY: + if self.getPlayer() == Player.EMPTY: player = Player.BLACK else: - player = Player.otherPlayer(self.getLastPlayer()) + player = Player.otherPlayer(self.getPlayer()) return self.addMoveForPlayer(row, col, player) def addMoveForPlayer(self, row, col, player): @@ -59,11 +91,19 @@ class GameMove: """ newBoard = self.board.getDeepCopy() newBoard.moveAndCapture(row, col, player) - return self.addMoveForPlayerAndBoard(player, newBoard) + newMove = GameMove( newBoard, (row, col) ) + newMove.previousMove = self + self.nextMoves.append(newMove) + return newMove - def addMoveForPlayerAndBoard(self, player, board): - """Adds a move to the next moves list containing the provided board.""" - newMove = GameMove(player, board) + def addPass(self): + """Adds a pass move to the next moves list.""" + newBoard = self.board.getDeepCopy() + newMove = GameMove(newBoard, True) newMove.previousMove = self self.nextMoves.append(newMove) return newMove + + def printBoard(self): + """Prints the board as of this move.""" + self.board.printBoard() diff --git a/imago/gameLogic/gameState.py b/imago/gameLogic/gameState.py index e4dd629..55bac5f 100644 --- a/imago/gameLogic/gameState.py +++ b/imago/gameLogic/gameState.py @@ -12,16 +12,16 @@ class GameState: self.size = size self.gameTree = GameTree() newBoard = GameBoard(self.size, self.size) - self.lastMove = GameMove(Player.EMPTY, newBoard) + self.lastMove = GameMove(newBoard) self.gameTree.firstMoves.append(self.lastMove) def getCurrentPlayer(self): """Gets the player who should make the next move.""" if self.lastMove is None: return Player.BLACK - if self.lastMove.getLastPlayer() is Player.EMPTY: + if self.lastMove.getPlayer() is Player.EMPTY: return Player.BLACK - return Player.otherPlayer(self.lastMove.getLastPlayer()) + return Player.otherPlayer(self.lastMove.getPlayer()) def getPlayerCode(self): """Gets a string representation of the current player.""" @@ -48,6 +48,10 @@ class GameState: print("Invalid Move! %s" % message) return False + def playPass(self): + """Passes the turn for the given player.""" + self.lastMove.addPass() + def undo(self): """Sets the move before the last move as the new last move.""" self.lastMove = self.lastMove.previousMove diff --git a/tests/test_gameBoard.py b/tests/test_gameBoard.py index 2fa1037..3a4d5a0 100644 --- a/tests/test_gameBoard.py +++ b/tests/test_gameBoard.py @@ -5,8 +5,6 @@ import unittest from imago.data.enums import Player from imago.gameLogic.gameBoard import GameBoard -#from imago.data.enums import Player - TEST_BOARD_SIZE = 19 class TestGameBoard(unittest.TestCase): @@ -14,10 +12,10 @@ class TestGameBoard(unittest.TestCase): def testGetGroupLiberties(self): """Test calculation of group liberties.""" - board = GameBoard(TEST_BOARD_SIZE) + board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) #Empty cell liberties - self.assertEqual(board.getGroupLiberties(0,0), {}) + self.assertEqual(board.getGroupLiberties(0,0), set()) self.assertEqual(board.getGroupLibertiesCount(0,0), 0) # Lone stone liberties @@ -26,5 +24,83 @@ class TestGameBoard(unittest.TestCase): {(2,3), (3,2), (4,3), (3,4)}) self.assertEqual(board.getGroupLibertiesCount(3,3), 4) + def testIsCellEye(self): + """Tests the isCellEye method.""" + board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) + + # Empty board is eye + self.assertEqual(Player.EMPTY, board.isCellEye(0, 0)) + self.assertEqual(Player.EMPTY, board.isCellEye(3, 3)) + self.assertEqual(Player.EMPTY, board.isCellEye(TEST_BOARD_SIZE-1, TEST_BOARD_SIZE-1)) + + # Board with 1 stone is eye + board.board[5][6] = Player.WHITE + self.assertEqual(Player.WHITE, board.isCellEye(3, 3)) + + # Board with 2 stones of different color is not eye + board.board[9][9] = Player.BLACK + self.assertEqual(Player.EMPTY, board.isCellEye(3, 3)) + + # Surrounded cell is eye + board.board[6][5] = Player.WHITE + board.board[6][7] = Player.WHITE + board.board[7][6] = Player.WHITE + + self.assertEqual(Player.WHITE, board.isCellEye(6, 6)) + + # Surrounded cell with 2 different colors is not eye + board.board[6][5] = Player.BLACK + self.assertEqual(Player.EMPTY, board.isCellEye(6, 6)) + + def testScore(self): + """Tests the score method.""" + board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) + + # Empty board has no score. + self.assertEqual((0, 0), board.score()) + + # Board with 1 black stone has totalVertices-1 points for black. + board.board[3][3] = Player.BLACK + self.assertEqual((TEST_BOARD_SIZE*TEST_BOARD_SIZE-1, 0), board.score()) + + # Board with 2 black stones has totalVertices-2 points for black. + board.board[5][5] = Player.BLACK + self.assertEqual((TEST_BOARD_SIZE*TEST_BOARD_SIZE-2, 0), board.score()) + + # Board with lone stones of different colors has no score. + board.board[7][7] = Player.WHITE + self.assertEqual((0, 0), board.score()) + + # Black group with surrounded territory. + board.board[2][3] = Player.BLACK + board.board[1][3] = Player.BLACK + board.board[0][3] = Player.BLACK + board.board[3][2] = Player.BLACK + board.board[3][1] = Player.BLACK + board.board[3][0] = Player.BLACK + self.assertEqual((9, 0), board.score()) + + # White group besides black group. + board.board[6][7] = Player.WHITE + board.board[5][7] = Player.WHITE + board.board[5][6] = Player.WHITE + board.board[5][5] = Player.WHITE + board.board[5][4] = Player.WHITE + board.board[5][3] = Player.WHITE + board.board[5][2] = Player.WHITE + board.board[5][1] = Player.WHITE + board.board[5][0] = Player.WHITE + board.board[8][7] = Player.WHITE + board.board[9][7] = Player.WHITE + board.board[9][6] = Player.WHITE + board.board[9][5] = Player.WHITE + board.board[9][4] = Player.WHITE + board.board[9][3] = Player.WHITE + board.board[9][2] = Player.WHITE + board.board[9][1] = Player.WHITE + board.board[9][0] = Player.WHITE + self.assertEqual((9, 21), board.score()) + + if __name__ == '__main__': unittest.main() diff --git a/tests/test_gameMove.py b/tests/test_gameMove.py new file mode 100644 index 0000000..6569c5b --- /dev/null +++ b/tests/test_gameMove.py @@ -0,0 +1,78 @@ +"""Tests for gameMove module.""" + +import unittest + +from imago.data.enums import Player +from imago.gameLogic.gameBoard import GameBoard +from imago.gameLogic.gameMove import GameMove + +TEST_BOARD_SIZE = 19 + +class TestGameMove(unittest.TestCase): + """Test gameMove module.""" + + def testAddMove(self): + """Test adding new moves to existing moves.""" + board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) + firstMove = GameMove(board) + + self.assertIsNone(firstMove.coords) + + secondMove = firstMove.addMove(1, 2) + + self.assertIsNone(firstMove.coords) + self.assertEqual(secondMove.coords[0], 1) + self.assertEqual(secondMove.coords[1], 2) + + thirdMove = secondMove.addMove(5, 7) + + self.assertIsNone(firstMove.coords) + self.assertIsNone(thirdMove.previousMove.previousMove.coords) + + self.assertEqual(secondMove.coords[0], 1) + self.assertEqual(secondMove.coords[1], 2) + self.assertEqual(thirdMove.previousMove.coords[0], 1) + self.assertEqual(thirdMove.previousMove.coords[1], 2) + + self.assertEqual(thirdMove.coords[0], 5) + self.assertEqual(thirdMove.coords[1], 7) + self.assertEqual(firstMove + .nextMoves[0] + .nextMoves[0] + .coords[0], 5) + self.assertEqual(firstMove + .nextMoves[0] + .nextMoves[0] + .coords[1], 7) + + self.assertEqual(firstMove.board.getBoard()[1][2], Player.EMPTY) + self.assertEqual(secondMove.board.getBoard()[1][2], Player.BLACK) + self.assertEqual(thirdMove.board.getBoard()[1][2], Player.BLACK) + + self.assertEqual(firstMove.board.getBoard()[5][7], Player.EMPTY) + self.assertEqual(secondMove.board.getBoard()[5][7], Player.EMPTY) + self.assertEqual(thirdMove.board.getBoard()[5][7], Player.WHITE) + + def testGetPlayableVertices(self): + """Test getting the set of valid moves.""" + boardSize = 3 + board = GameBoard(boardSize, boardSize) + + firstMove = GameMove(board) + self.assertSetEqual( + firstMove.getPlayableVertices(), + set(((0,0), (0,1), (0,2), + (1,0), (1,1), (1,2), + (2,0), (2,1), (2,2))) + ) + + secondMove = firstMove.addMove(1, 2) + self.assertSetEqual( + secondMove.getPlayableVertices(), + set(((0,0), (0,1), (0,2), + (1,0), (1,1), + (2,0), (2,1), (2,2))) + ) + +if __name__ == '__main__': + unittest.main() diff --git a/tests/test_monteCarlo.py b/tests/test_monteCarlo.py new file mode 100644 index 0000000..8fe6f47 --- /dev/null +++ b/tests/test_monteCarlo.py @@ -0,0 +1,22 @@ +"""Tests for the MonteCarlo algorithm.""" + +import unittest + +from imago.gameLogic.gameBoard import GameBoard +from imago.gameLogic.gameMove import GameMove +from imago.engine.monteCarlo import MCTSNode + +TEST_BOARD_SIZE = 19 + +class TestMonteCarlo(unittest.TestCase): + """Test MonteCarlo algorithm.""" + + def testSimulation(self): + """Test calculation of group liberties.""" + board = GameBoard(TEST_BOARD_SIZE, TEST_BOARD_SIZE) + move = GameMove(board) + node = MCTSNode(move, None) + node.simulation() + +if __name__ == '__main__': + unittest.main() |