{"id":17649,"date":"2018-04-18T16:27:00","date_gmt":"2018-04-18T16:27:00","guid":{"rendered":"http:\/\/www.gamasutra.com\/view\/news\/316654"},"modified":"2018-04-18T16:27:00","modified_gmt":"2018-04-18T16:27:00","slug":"blog-creating-a-hard-ai-for-terra-mystica","status":"publish","type":"post","link":"https:\/\/sickgaming.net\/blog\/2018\/04\/18\/blog-creating-a-hard-ai-for-terra-mystica\/","title":{"rendered":"Blog: Creating a hard AI for Terra Mystica"},"content":{"rendered":"

The following blog post, unless otherwise noted, was written by a member of Gamasutra\u2019s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.<\/small><\/em><\/strong><\/p>\n

\n

Spoiler alert: This doesn’t have a happy ending.\u00a0 Digidiced<\/a> has been hard at work for more than a year trying to produce a Hard version of its AI for Terra Mystica<\/a> using machine learning.\u00a0 Our results have been a lot less impressive than we were hoping for.\u00a0 This article will describe a little bit about what we\u2019ve tried and why it hasn’t worked for us.<\/p>\n

If you\u2019ve paid attention to the latest developments in AI, you\u2019ve probably heard of AlphaGo<\/a> and AlphaZero<\/a>, developed by Google\u2019s DeepMind<\/a>.\u00a0 In 2017, AlphaGo defeated Ke Jie, the #1 ranked Go player in the world.\u00a0 AlphaGo was developed by using a massive neural network and feeding it hundreds of thousands of professional games.\u00a0 From those games, it learned to predict what it thought a professional would play.\u00a0 AlphaGo then went on to play millions of games against itself, gradually improving its evaluation function little by little until it became a superhuman monster, better than any human player.\u00a0 The defeat of a human professional was thought to be decades away for a game as complex as Go. \u00a0But AlphaGo shocked everyone with its quantum leap in playing strength.\u00a0 AlphaGo was able to come up with new strategies, some of which were described as \u201cgod-like.\u201d<\/p>\n

\"\"<\/p>\n

But it didn’t stop there.\u00a0 In December of 2017, DeepMind introduced AlphaZero \u2013 a method that also learned the game of Go, but this time didn’t use any human-played games.\u00a0 It learned entirely from self-play, being only told the rules of the game.\u00a0 It was not given any suggestions or strategies on how to play.\u00a0 AlphaZero not only able to learn from self-play alone, it was able to get stronger than the original AlphaGo.\u00a0 And on top of that, the same methodologies were used for Chess and Shogi and the DeepMind team showed results that AlphaZero was able to solidly beat the top existing AI players in both of these games (which were already better than humans).\u00a0 Since these results have come out, there has been some criticism around if the testing conditions were really fair to the existing AI programs, so there is a little debate as to whether AlphaZero is actually stronger, but it is an outstanding achievement nonetheless.\u00a0<\/p>\n

It also became quite clear that AlphaZero approached chess differently than Stockfish<\/a> (the existing AI they competed against).\u00a0 While Stockfish examined 70 million positions per second, AlphaZero only examined 80,000.\u00a0 But AlphaZero was able to pack a lot more positional and strategic evaluation into each of those positions.\u00a0 By examining the games that AlphaZero played against Stockfish it became obvious to a lot of people that AlphaZero was much better at positioning its pieces and relied less on having a material advantage.\u00a0 In many cases AlphaZero would sacrifice material in order to get a better position, which it later used to come back and secure a win.\u00a0 It suggested the possibility that there might be a resurgence in chess programming ideas, which had been stagnating in recent years.<\/p>\n

\"\"<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

\u00a0<\/p>\n

The DeepMind team was able to show that AlphaZero learned many human-discovered opening moves.\u00a0 They showed several examples of how different openings gained and lost popularity as it continued to learn.<\/em><\/p>\n

As Digidiced\u2019s AI developer, these were exciting developments for me.\u00a0 I\u2019ve had experience with machine learning and neural networks before and have been playing around with them for many years. \u00a0I once developed a network as a private commission for a professional poker player that could play triple draw low at a professional level.\u00a0 I began to wonder if I could use some of these same techniques for Digidiced\u2019s Terra Mystica app.\u00a0 One of the compelling features of AlphaGo was that it was largely based on something called a convolutional neural network<\/a> (CNN).\u00a0 A CNN is also used in other deep learning applications like image recognition and is good at identifying positional relationships between objects.\u00a0 AlphaGo was able to use this structure to identify patterns on the Go board and determine the complex relationships that could be formed from the different permutations of stones.<\/p>\n

While Terra Mystica takes place on a hex-based map instead of a square grid, a CNN can still be applied to it so that the proximity of players\u2019 buildings can be incorporated, which is a critical part of TM strategy.\u00a0 However, there are several things that make TM a much more complicated game than Go.<\/p>\n