First MonteCarlo match simulations.

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}
 
diff --git a/go.py b/go.py
index 548df38..96f7052 100755
--- a/go.py
+++ b/go.py
@@ -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()