aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--doc/diagrams/GameBoard.pumlc28
-rw-r--r--doc/diagrams/GameMove.pumlc20
-rw-r--r--doc/diagrams/GameState.pumlc16
-rw-r--r--doc/diagrams/GameTree.pumlc4
-rw-r--r--doc/diagrams/gameRepresentation.puml9
-rw-r--r--doc/diagrams/gtpEngine.puml15
-rw-r--r--doc/tex/implementation.tex34
-rw-r--r--doc/tex/previousWorks.tex15
-rw-r--r--doc/tex/tfg.tex4
-rwxr-xr-xgo.py4
-rw-r--r--imago/engine/core.py19
-rw-r--r--imago/engine/monteCarlo.py91
-rw-r--r--imago/engine/parseHelpers.py9
-rw-r--r--imago/gameLogic/gameBoard.py148
-rw-r--r--imago/gameLogic/gameMove.py68
-rw-r--r--imago/gameLogic/gameState.py10
-rw-r--r--tests/test_gameBoard.py84
-rw-r--r--tests/test_gameMove.py78
-rw-r--r--tests/test_monteCarlo.py22
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()