HKU Department of Computer Science 2016-17 - FYP16020
Playing Othello by Deep Learning Neural Network

icon INSPIRATION

Over the years, people have been trying to exploit the abilities of a computer to create a better world. One of such abilities is to make decision as if human do. A way to show the capability of a computer making good decision is by playing board games as it involves the evaluation of the current board settings and selecting the next best moves constantly throughout the game. It is also a good way to evaluate how good a computer can perform when compared with human.


icon COMPUTER BOARD GAME

Traditionally, a computer plays a board game by searching through the game tree - a tree containing all the possible moves with the corresponding weights, which indicate how likely one can win the game with those moves. The values of the weights are being assigned according to an evaluation function.

Due to the limited storage and the complexity of the game search tree, the computer has to prune the branches with less weight for decision-making.



icon PROJECT FORMULATION

Inspired by the human brain, neural network is a way of information processing. Several layers of notes in the neural network are connected together and change as the system is trained. A large amount of training data are used to fine-tune the connections during the training process so that the network can produce a specific output corresponds to the given input. A deep learning neural network is a network with many layers. This deep learning neural network can help increase the accuracy of the results generated by the evaluation function throughout a series of learning processes, and hence, can help the computer make better decision of which branches to prune when searching for the next best move.

This project aims to demonstrate how powerful deep learning neural network can be for game-playing. The game Othello is chosen as the technique of deep learning neural network can be applied this game. Meanwhile, the size and the complexity of this game is suitable for a one-year long project with limited resources.



icon OBJECTIVES

The objective of this project to develop a computer Othello program with the following attributes:

  • The game board configuration being the size of 8x8
  • A winning rate of 50% when playing against a moderate (computer) opponent
  • A winning rate of 35% when playing against a strong (computer) opponent
  • A user-friendly UI for easy playing

While the ultimate outcome is to deliver the above program, the key of this project is to allow the evaluation function of the program being constructed by the program itself without human logic.



METHODOLOGY


  • Development Model

    Figure 1 describes the development model of this project. Detail steps of the project flow are listed below:

    1. Collect requirements and analyze on the current solution and strategy
    2. Prepare 100 sets of training data for use in deep learning
    3. Design the game search tree for selecting the next best move
    4. Implement the game program
    5. Implement the evaluation function with suitable set of parameters
    6. Test for the evaluation function
    7. Evaluate the testing results, repeat step 5 - 6 if necessary
  • Development Model
  • Algorithm - Evaluation Function

    The simple flow of building the evaluation function is demonstrated in Figure 2. The set of board configurations of different game will be pre-processed and used as the training data for the neural network. Once a learning model is built and configured, it can learn from the training data during the learning process and the evaluation function will be updated accordingly. An updated evaluation function for the board configuration will be obtained at the end of the learning process.

  • Evaluation Function
  • Testing

    The computer Othello developed will be tested against two types of opponents, moderate computer opponents and strong computer opponents. The choice of opponents at both levels for testing shall be discussed and agreed with the supervisor during the second phase of the project.

    The two types of opponents will be tested with 50 games each. When playing against a moderate computer opponent, the targeted winning rate is 50%, while the targeted winning rate for playing against a strong computer opponent is 35%.

    It is believed that when both sides play the game perfectly, the game will very likely end with a draw. Hence, when the winning rate of 50% is achieved, the computer Othello we developed can be said to be comparable with the existing computer Othello developed with the traditional method.

    A lower winning rate of 35% is set when our computer Othello plays against a strong computer opponent and the reasons are stated as follow. The neural network may not be trained very well due to the limited time and other resources. Besides, the number of different board configurations we obtained as the training data may not be large enough for constructing a good evaluation function. These factors will affect the performance of the computer Othello we are going to develop, and hence, a target of 35% winning rate is set.

DOCUMENTS


SCHEDULE


Date Task(s) Deliverables Status
Sep 2016
  1. Self-study on
    1. Game tree
    2. Deep learning neural network
    3. Strategies of playing Othello
  2. Preparation of training data
Completed
2 Oct 2016
  1. Detailed project plan
  2. Webpage
Completed
Mid-Oct 2016
  1. Assignments of values for the board configurations obtained from training data
  1. 100 sets of training data
Completed
16 Nov 2016
  1. Implentation of the game tree
Completed
21 Dec 2016
  1. Implementation of the evaluation function and the game
Completed
28 Dec 2016
  1. Report on the result of the first set of pre-defined parameters for deep learning process
Completed
9 - 13 Jan 2017
  1. Interim Presentation
Completed
22 Jan 2017
  1. Interim Report
Completed
08 Feb 2017
  1. UI of the game
Completed
Mid-Mar 2017
  1. Finalized optimization
Completed
16 Apr 2017
  1. Final Report
Completed
02 May 2017
  1. Project exhibition and presentation
In Progress

OUR TEAM

Please contact us at fyp16020@cs.hku.hk