People.uncw.edu



Optimizing Strategies to Play Go Richard Chambers, Tower Hufham, Eryn VanceUniversity of North Carolina WilmingtonAbstract Go is an ancient Chinese board game that has been around for centuries. It is a simplistic game by nature. Two players place either black or white pieces on to a game board, which is a simple nineteen by nineteen Cartesian plane, with the goal of capturing as much territory as possible by the end of the game. The simplistic nature of the game allows for a wide variety of strategies to be used in a single match. But when implemented algorithmically, what singular, na?ve strategy performs the best when accounting for winning percentages and time complexity? The three popular and distinct strategies that were tested were Connection and Separation, Life and Death, and High and Low. By a wide margin, Connection and Separation was the superior strategy when in regards to win percentage; however, the time complexity of this implementation of Connection and Separation is O(n(4(n-e)), which gives it the worst complexity of the three algorithms and thus, a much slower relative average turn speed.1. IntroductionThe game of Go is relatively simple when compared to many other board games. The game is played between two players, one using black pieces and the other using white pieces. The game is usually played on a wooden board with a nineteen by nineteen grid carved into it. The players play their pieces on the points on the grid. The goal of the game is to capture as much “territory” as possible. The territory is defined to be all three hundred sixty-one points on the board. If a player’s piece(s) becomes surrounded, then the piece(s) is/are removed from the board.The simplicity of Go has allowed many strategies to take shape in the years since the game was created. Three popular strategies to play Go are Connection and Separation, Life and Death, and High and Low. Players in a real game of Go implement many strategies at once based on their opponent’s moves. The purpose of this project was to determine which of these strategies would perform best when used alone, i.e. have the highest when percentages against players using the other two strategies and has the lowest time complexity when implemented algorithmically. These algorithms were implemented in Python and Google’s AlphaGo [1] library was used to handle all of the Go game logic and test win percentages of the algorithms. AlphaGo was used as the inspiration for this research as it was the first Go-playing program to beat an official world champion in the game of Go.2. Formal Problem Statement Formally, the goal of the project was the following: the team must design three algorithms which each implement a distinct Go game strategy. Based on win percentages against each of the other algorithms, win percentages against a fourth random placement algorithm, the time complexity of executing a turn (t), and average turn time, compare the three algorithms and determine which algorithm is the most optimal strategy. Each algorithm must take in a 19x19 board (Cartesian plane of size 19x19) represented by an 19x19 matrix “A.” The algorithms will select an index A[i][j] as a placement and if no piece can be placed the algorithm will return “None” each turn. Two algorithms represented by player1 and player2 (P1, P2) will play against each other during a game.The game enters the end state when neither player has chosen to place a piece or neither player can make a legal move. Each player’s territory (T1, T2) is summed and compared to find the winner.Score Talley:n = total board size (19x19)Eye: A position surrounded by a player’s pieces3. Connection and Separation StrategyThe strategy of Connection and Separation is as simple as it sounds, the player should attempt to split their moves between keeping their pieces connected and blocking or separating their opponent’s pieces. By ensuring that the opponent is unable to form groups, this strategy makes it very difficult for the opposing player to execute their strategy and leaves the opponent’s pieces susceptible to being captured; at the same time, it allows the player to ensure that they are steadily gaining territory and locking down sections of the board. The inhibiting nature of this strategy makes it very difficult to overcome. As shown below, black (Con. and Sep.) builds a large group in the bottom left of the image while blocking white from forming any large groups.(Connection and Separation: Black)4. Connection and Separation AnalysisIn the implementation of this algorithm the process is split up into a series of three states. The first state is the starting state. In this state the algorithm randomly chooses a starting position to place one piece. The position is chosen from a list of points on the board known as “star points.” Star points have no special value in Go other than being traditionally where players place their first piece. During every turn in both the connection state and the separation state, a list of legal moves is returned from the AlphaGo library. This list of moves is iterated over to remove coordinates known as “eyes.” Eyes are positions without a piece that are surrounded on all sides by a single player’s pieces. Since the opponent could not play a piece at this location, it is not considered to be a useful place for that player to make a move. Since the list of n moves must be iterated over completely that brings the complexity of the algorithm to O(n) so far.4.1. Connection State After the start state, the algorithm flips to the connection state. Once the eyes are removed, the algorithm searches the board to find all the open positions that have the players pieces connected to it. To do this, the list of legal moves is iterated over and at each position each of the four liberties (above the position, below the position and to the left and right of the position) are checked to see whether a piece placed by that player is occupying any of those positions. If so, that position is appended to a list that will eventually contain all positions occupied by the player’s pieces. This operation is O(4(n-e) with e being the number of eyes. The four represents the fact that, at each index in legal moves, the algorithm must perform four checks, one for each liberty of the position at that index.After all the positions that connected to the player’s pieces are found, the algorithm randomly chooses an index of this list and returns the position stored there. Since the algorithm was implemented in Python, it uses Python’s random.choice() function, which has a complexity of O(1). If all the complexities are combined for each of the steps in the algorithm, then that would give a complexity of O(n(4(n-e)).4.2. Separation StateAfter connection is performed five times, the state is flipped into separation mode. Again, before the board is searched, all the eyes are removed from legal moves. Separation mode works identically to connection mode with the exception of searching for positions that are connected to the opponent’s pieces instead of searching for positions connected to the player’s pieces. This makes the complexity of separation O(n(4(n-e)) as well. Separation is performed fifteen times before the algorithm switches back to connection. The algorithm alternates back and forth between the two states until the game is finished.5. Life and Death StrategyThe Life and Death algorithm is an extension of the random algorithm. Instead of placing a stone in a random position, it attempts to build a “block” on a random area. A block is a shape that when completed is uncapturable by the other player.Structure of a “block”. The central stone is the “home.”Once a block is finished, the two spaces it leaves open (“eyes”) are stored in set E so that they don’t get played on. Checking these is a simple iteration, making the operation O(n-E), where n = legal moves.When starting a block, it chooses a “home” space randomly on the board away from edges and other pieces. (If a suitable location can’t be found after 20 tries, it defaults to random placement.)5.1 Determining H, The Home PointPoint H is a random Hx, Hy where:2 >= Hx => 17, 1 >= Hy => 18,and there are no spaces filled by an opponent’s piece in B, where B is the set of all x,y points where the x value is in the range [Hx-2, Hx+2] inclusive, and the y value is in the range [Hy-1, Hy+1] inclusive; and no point in B is also in E.If a suitable H cannot be found within twenty attempts, the algorithm defaults to the random placement algorithm, with the addendum that it won’t play on any point in E.During a turn while it has a home space, it checks for all points in B (a set of at most 13 points).First, it checks to see if an enemy stone has been placed on any point in B. If it finds one, then a new home is searched for next turn. If there are no enemy points placed in B, then it checks to see how many points are left un-played by the player. If there are points left, it chooses a random one and places a stone there. If all the spaces are filled, then a new home is searched for.Checking E (the set of eyes) is an O(n-E) operations. Every other operation is O(1), so this algorithm is O(n-E) overall.6. Life and Death AnalysisThis algorithm performs best when it isn’t interrupted. An enemy placing a stone into an area where this algorithm is planning to play in causes it to start a new block, therefore wasting a lot of time. If it is able to fully build blocks, then this algorithm performs well. Its uncapturable structures give it a very large advantage due to the fact that its territory can never be removed from the board.Out of the 1500 games it played against the other algorithms, the Life and Death algorithm won 837, giving a total win percentage of about 56%.7. High and Low StrategyHigh and low is a strategy that focuses evenly on gaining territory by places stones around the edges of the board as well gaining influence by placing stones in the center. The strategy does not focus on capturing small groups of pieces as the two previous strategies do; it instead aims to minimize the amount of territory the player has by encompassing large areas of the board.8. High and Low AnalysisHigh and low is the least complex of the three strategies discussed in this paper. Each turn, the algorithm iterates through the list of all legal moves and appends moves within the defined high and low areas to a list of preferred moves. It then uses the python random.choice() method to randomly choose from the preferred move list. The “low” part of the board is bracket shaped and consists of x and y coordinates such that y is [0,19] when x is [0,3], or y is [0, 3] ∪ [15, 19] when x is [4, 8].The “high” part of the board consists of all moves where both x and y are in the range [6,12]. High and Low’s preferred moves.The algorithm prioritizes moves in the following order from highest priority to lowest: low moves, high moves, middle moves, moves on its half of the board, and random moves. Middle moves are defined as the set of legal moves where x is equal to 9. Additionally, each game, the algorithm makes a random choice to decide which half of the board to focus on; it attempts to fill in its half when it runs out of high, low, and middle moves, respectively. Finally, random moves are played when there are no more preferred moves available.The random.choice method is O(1), thus, since the rest of the algorithm is simply iterating through a list of n moves and copying preferred moves to one of four new lists before randomly choosing from one of the lists based on conditional statements, the overall Big O is O(n).8.1. Comparison to Other AlgorithmsOut of 1500 total games played, with 500 games played against each of the other three algorithms (the third algorithm being random placement), High and Low performed the worst. High and Low did not win any games against either of the two “strategy” algorithms, and only won by a small margin during its 500 games against the random algorithm.However, High and Low had one of the lowest times per turn; it performed a single turn in an average of 2.79e-6 seconds, which was negligibly slower than Life and Death.8.2. High and Low Conclusions Ultimately, High and Low appeared to perform the worst because of its focus on only a single half of the board. Unlike the other algorithms, High and Low’s strategy depended on creating a bracket on only one side of the board. There appeared to be no difference in performance regardless of which side of the board was chosen.The algorithm aimed to gain territory on, at minimum, one half of the board each game; however, because the other algorithms did not behave in the same way, High and Low’s bracket formation was easy captured by the enemy.In the ideal game of Go, a player would employ High and Low in conjunction with several other strategies. Data shows that by itself, however, the strategy is incredibly weak and can be quickly overtaken.9. Findings: Game Data AlgorithmsNumber of WinsConnection VS Life and DeathC: 458 L: 42Connection VS High and LowC: 500 H: 0Connection VS RandomC: 500 R: 0Life and Death VS High and LowL: 500 H: 0Life and Death VS RandomL: 287 R: 213High and Low VS RandomH: 295 R: 205Random VS RandomBlack:263 White: 237Figure 1 Illustrated in the table above (Figure 1), it is evident that the algorithm that won the most games was Connection and Separation. Out of the 1500 games that were played, the algorithm lost only 42 times. In contrast, the algorithm that won the least amount of games was High and low. Only winning 295 of the 1500 it played. Looking at the results from the random versus random games, it is also apparent that there is a slight advantage to playing as black since black always makes the first move. This was accounted for during the testing as each of the algorithms played 250 games as black and 250 games as white in each round.10. Findings: Average Turn Speed and Complexity Listed below are the average turn speeds (in seconds) for each of the algorithms and a bar graph comparing the four algorithms.Connection and Separation1.6016e-5Life and Death2.6822e-6High and Low2.79e-6Random7.1168e-6Figure 2Figure 3 In Figure 3, it is clear to see that the complexity of Connection and Separation yielded a much higher average turn speed. The algorithm with the fastest average turn speed was Life and Death. This is to be expected as less iteration is used each turn, giving it a very low complexity compared to the other algorithms. Random performed slower than both High and Low and Life and Death. This is likely because Python’s random.choice() function uses more operations to derive its random choice than High and Low and Life and Death do to derive their placement. 11. Future WorkFuture work on these algorithms would include improvement of strategies, with the primary focus being on optimizing Connection and Separation so that its average turn time is faster. The ability for each algorithm to play against a human player would also be important in order to test the strategies to the same degree that Google’s AlphaGo was tested. Additionally, implementing the use of multiple strategies by a single algorithm during a game would bring allow the research and data gathered to be more comparable to games of Go played by humans.12. Conclusion Although Connection and Separation has a much higher average turn speed than the other two non-trivial algorithms, it is still fast enough on a 19x19 board that it does not affect the performance of playing the game. Given the sheer number of wins accrued during testing by Connection and Separation, the high average turn speed is not enough to discount Connection and Separation as a viable algorithm. What can be surmised from these findings is that any optimal strategy for playing Go must include a component that focuses on separating the other players pieces. This greatly inhibits the other player from executing their own strategy and makes it much harder for them to gain an advantage.12. Resources[1] vapor, jzhangbs, wzhouad. (2018). AlphaZero Documentation. Available: ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download