Oskar Arvidsson
Linus Wallgren
This report applies the reinforcement learning algorithm Q-learning to the simple pen and pencil game dots & boxes, also known as La Pipopipette. The goal is to analyse how different parameters and opponents affect the performance of the Q-learning algorithm. Simple computer opponents play against the Q-learning algorithm and later Q-learning algorithms with different experience play against each other. Several different parameters are tried and the results are plotted on detailed graphs. The graphs show that the best results are gained against other Q-learning algorithms and a high discount factor. In the interval of 0.2 to 0.8, a discount factor of 0.8 showed the best results. In the same interval a learning rate of 0.2 showed the best long-term result while a higher learning rate, 0.8, gave the best short-term results. Especially when two Q-learning algorithms with different experiences played against each other, the best results were obtained with a learning rate of 0.8. The best results were shown when letting a Q-learning algorithm play against another Q-learning algorithm. A learning rate and discount factor of 0.8 showed the best results, however the data suggested even higher values of the discount factor might give even better results. In a dots & boxes game with a grid of three by three dots it requires about 1 million games to reach a good result.
Den här rapporten handlar om att applicera Q-learning, en belöningsbaserad inlärnings- algoritm, på spelet dots & boxes som ursprungligen kallades La Pipopipette. Målet är att analysera hur olika parametrar och motståndaren påverkar prestandan av Q-learning. Q- learningalgoritmen spelar både mot enkla datormotståndare och mot andra Q-learning al- goritmer med andra erfarenheter. Flera parametrar testas och resultatet av alla tester pre- senteras i en mängd detaljerade grafer. Vad graferna visar är att de bästa resultaten fås när motståndaren också är en Q-learning algoritm samt när avdragsfaktorn är hög. När Q- learningalgoritmen spelar mot enkla datormotståndare visar det sig att inom intervallet 0.2 – 0.8 ger en learning rate på 0.2 samt en discount factor på 0.8 de bästa resultaten. Resul- taten antydde även att ännu högre discount factors ger ännu bättre resultat. När två olika Q-learning algoritmer möter varandra blir resultatet som bäst när man även låter learning rate vara 0.8. Alla tester visar på att en miljon körningar är mer än tillräckligt för att göra algoritmen mycket bra när en spelplan på 3 gånger 3 prickar används.