From b08408d23186205e71dfc68634021e3236bfb45c Mon Sep 17 00:00:00 2001 From: InigoGutierrez Date: Fri, 1 Jul 2022 16:10:15 +0200 Subject: First version. --- doc/tex/conclusions.tex | 128 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 128 insertions(+) create mode 100644 doc/tex/conclusions.tex (limited to 'doc/tex/conclusions.tex') diff --git a/doc/tex/conclusions.tex b/doc/tex/conclusions.tex new file mode 100644 index 0000000..ebbf7fd --- /dev/null +++ b/doc/tex/conclusions.tex @@ -0,0 +1,128 @@ +\section{Conclusions} + +Some problems found during the project, an evaluation of the results and what +could be done in the future to improve the system are discussed here. + +\subsection{Problems with the Implementation of the Game} + +While Go has a simple set of rules, they lead to many borderline cases which +must be specifically addressed. For example, the ko rule obliges to check the +previous board positions after each move so no boards are repeated. + +These problems have been solved by designing the tree of moves of a match so +each move stores the full board layout after it has been played. This of course +increases the memory needed to run the application, but has been chosen over the +alternative of having to recreate the board parsing the tree backwards for each +move to check if ko is occurring, if a move makes a capture and which stones +have already been captured, etc. It is the old problem of memory versus +processing, which in this case has been answered with memory. Which one would be +the best solution would require a deep analysis out of the scope of the project. + +\subsection{Problems with the Monte Carlo Tree Search Algorithm} + +The implementation Monte Carlo Tree Search algorithm was not precise by itself +when asked for moves. This could be attributed to various factors: + +\begin{itemize} + + \item The way the score is counted makes it difficult to evaluate who is + winning at the beginning or middle of the game, so the score of a move + has to be evaluated by running playing simulations. These simulations + are not precise on analyzing the result since the moves in them are + played at random. + + \item The configuration used, 5 explorations with 10 simulations each for + cycle, does not allow for many good moves to be found. + +\end{itemize} + +To solve these problems, either a good score evaluation engine has to be +implemented, which is another machine learning problem by itself, or the +explorations and simulations of the engine tuned up to values unable to be run +on the development hardware. + +\subsection{Problems with Neural Networks} + +Some concerns with the design and results of the neural networks are discussed +on this section. + +\subsubsection{Finding the correct design} + +When approaching neural networks design with a basic understanding of their +inner workings it is easy to get lost in all the different factors that can be +tuned. The number and variant of layers, their number of nodes, their activation +function, the learning rate; they can all be tweaked and doing so in the favour +of the design requires a good knowledge of what is being done. + +The basic approach was to design the input and output shapes and then adjust the +network based on that. At first, the desired output was a 9x9 two-dimensional +matrix with the probabilities of playing on each move. A heatmap generated from +a failed solution of this approach can be seen on \fref{fig:oldHM}, where the +network distributed the probability for each row instead of the whole board. The +fitting of shapes of input, internal layers and output has found to be tricky at +first. + +\begin{figure}[h] + \begin{center} + \includegraphics[width=\textwidth]{img/matches/oldLineByLineHeatmap.png} + \caption{A heatmap from an old design of the dense neural network.} + \label{fig:oldHM} + Note that each row adds up to one, meaning that the engine is selecting + the best move for each row and not for the whole board. + \end{center} +\end{figure} + +Finally, based on the design of classification networks where each possible +class is mapped to a value in the one-dimensional output vector, it was decided +that the output was not a two-dimensional matrix but a one-dimensional vector. +This also helped address the possibility of passing, treating it as just another +possible move that was previously left out because of not knowing how to fit it +on the matrix of possible moves. This vector is then reshaped to a matrix +representing the board when needed, for example to generate the heatmaps used +for evaluation. + +\subsubsection{Mistakes on Networks' Play Patterns} + +One notable mistake made by the networks, specially the convolutional network, +was passing to much. Passing is considered just another move, so the networks +have no grasp that they should not pass until there are no more valuable moves +to be made. A new design problem could be to create a specific passing policy. + +Another observation is that the engines seem to follow traditional openings and +make reasonable decisions at the start of the game, with some interesting +variations. But as the game progresses their moves make less sense. This could +be because they have seen many examples of starting moves but complications at +the middle and end game are much more diverse and the networks had not been +trained on similar situations. + +\subsection{Viable Extensions} + +There are several ways this project could be improved, but were left out by lack +of resources or time. Some interesting ones are explored on this section. + +\subsubsection{Joining Monte Carlo Tree Search and Neural Networks} + +The tree search algorithm is better at the end of the game, where the tree to +explore is much more manageable. On the other hand, the neural networks are +better at the beginning, where the positions are more common and patterns are +simpler. The logical next step would be to join both: the network could select +the best moves to be made, and the tree search algorithm could explore them to +select the best and grow its explored tree in meaningful directions. + +This is also what was done by AlphaGo. By seeing the results obtained in this +project it makes sense they made that decision. + +\subsubsection{Train the Engine by Itself} + +By training a game engine on human matches, it can at best get as good as the +human players it has learned from. + +Top engines learn not from humans but by playing against themselves. This would +be an interesting problem to tackle, if requiring a new approach to the design +of the networks and a lot of training resources. + +\subsubsection{Presenting the Engine to the World} + +Some Go servers allow for bot players to be registered. This would provide a +source of training against players from all around the world and also an +evaluation over time of the engine strength. -- cgit v1.2.1