The concept of an AI playing itself and learning from the games seems amazing to me. I know there are some interested in AI on this website so I thought I would share if they haven't seen yet
Re: Go AI beats top professional
Posted:
Feb 9, 2016, 10:09 PM
Apologies in advance for the mini thesis to follow... I ran across this news a week or so ago; a very impressive accomplishment by Google's DeepMind project - it'll be interesting to see how a 5 month older distributed AlphaGo program performs against Lee Sedol in March. I remember several years ago playing against a Pente program which had a genetic algorithm (which seems similar to allowing a program to improve by playing against itself across 50 computers as they did with the DeepMind project). Unfortunately, as I recall the genetic algorithm program itself wasn't very good at Pente. I believe it was the program found here, but it's been a decade or more so I might be mistaken. http://www.generation5.org/content/2001/penteai.asp Looking at some of the details involved in achieving AlphaGo's success (without having access to the full article in Nature yet) as described here in relationship to Pente and AI: http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html
1.) they used two deep neural networks- a.) a policy network and b.) a value network, the policy network initially being trained on 30 million moves from games played by human experts. Pente.org's database likely includes less than 10 million moves, based on the 500K+ games and figuring the average number of moves in most games to be less than 20. Also, the majority of the moves in the database weren't made by Pente experts, since some were played by players before they became expert at the game and some were played by players who have not yet achieved an expert rating (whatever that might be; I'm not sure what the Elo or Dan ranking cutoff was for moves used to train the program, but training an AI on moves made by expert pente players would definitely have a much smaller pool of moves to choose from given the shorter games, shorter history of the game and smaller number of players of the game. Nonetheless, given how much simpler Pente is to master for human players than Go, the number of moves currently available might be sufficient for training a similarly successful policy deep neural network for Pente. The value network seems similar(from a non programming expert's perspective at least) to what is used by Mark Mammel's and other Pente programs.
2.) The Monte Carlo tree search is guided by the 2 deep neural networks of AlphaGo. We had a thread here a few years back about Monte-Carlo tree search in which Kolia mentioned some research he had done on improving it (he also mentions 3.) "reinforcement learning" in his post about that): https://www.pente.org/gameServer/forums/thread.jspa?forumID=1&threadID=230180&tstart=-3
3.) repeated use of reinforcement learning to further improve the neural networks: quotes from http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html "AlphaGo learned to discover new strategies for itself, by playing thousands of games between its neural networks, and gradually improving them using a trial-and-error process known as reinforcement learning. This approach led to much better policy networks, so strong in fact that the raw neural network (immediately, without any tree search at all) can defeat state-of-the-art Go programs that build enormous search trees. These policy networks were in turn used to train the value networks, again by reinforcement learning from games of self-play. These value networks can evaluate any Go position and estimate the eventual winner - a problem so hard it was believed to be impossible."
Read that last sentence again and let the achievement of that sink in with respect to a second quote from the article "The search space in Go is vast -- more than a googol times larger than chess (a number greater than there are atoms in the universe!). As a result, traditional ?brute force? AI methods -- which construct a search tree over all possible sequences of moves -- don?t have a chance in Go."
Looking at Elo rankings of various computer Go programs in comparison to Pente ratings here is a bit difficult due to the larger upper range in games like Go and chess versus the upper ranks for Pente which generally top out around the mid 2300s both here and at Brainking, whereas the world's best chess and Go players top out at around 2900 based on FIDE ratings and European Go Federation ratings, which are modified Elo ratings https://en.wikipedia.org/wiki/Go_ranks_and_ratings#Elo-like_rating_systems_as_used_in_Go ; top commercially available Go programs like Crazy Stone and Zen currently play at around an amateur 6 dan level which the European Go Federation translates to a 2600 level. A 2 dan professional such as Fan Hui, who Alpha Go beat, would appear to have an EGF rating of around 2720. Lest those rating differences seem relatively small, bear in mind that AlphaGo on a single computer won 499/500 games against the other top computer Go programs and beat them even when giving them a 4 stone handicap (equivalent to roughly 400 rating points in the EGF rating system). Based on DeepMind's comparison chart shown in the above linked article, they estimate that AlphaGo played at approximately a 5 dan professional level in October 2015, which would not then have put it at the top professional level of Go play 9 dan professional (or 2940 EGF) but it may well have improved in the last 4 months and improve some more again before it plays for $1 million against Lee Sedol in March.
I think it's safe to say, given the complexity of Go versus Pente, that if equivalent resources were brought to bear on Pente as have been brought to bear on Chess or Go, Pente would already be a solved game. Thank goodness for us that we still have a challenging and fun game to play where perfect strategies are not all absolutely known from start to finish.
Re: Go AI beats top professional
Posted:
Feb 18, 2016, 11:50 PM
Thanks for the figures, RW. I'm also glad Pente hasn't been of interest (so far, anyway) to that level of AI development. I enjoy playing games which i occasionally have a chance of winning However, I'm also interested in the development of AI and looking forward to seeing how creative it can eventually become during my lifetime. For now, I'm making up a thought experiment wherein some currently unsolved math problems like Goldbach's conjecture are translated into base 3 (instead of binary) and expressed as a pattern of black stones, white stones and 0s on a 19x19 board. How many of such expressions as examples would a super intelligent mind need in order to predict how an example pattern would evolve in order to express another such pattern?
Message was edited by: watsu at Feb 18, 2016 11:51 PM
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Go AI beats top professional
Posted:
Mar 8, 2016, 5:45 AM
Just for fun in a bit of my free time I wrote a list style post about AI, games and the upcoming (the first game starts in less than a day now) $1 million challenge match between AlphaGo and the best professional Go player of the past decade. http://www.buzzfeed.com/tomc6/will-go-ai-eclipse-top-human-gamer-this-week-1icm
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Go AI beats top professional
Posted:
Mar 9, 2016, 1:12 PM
AlphaGo defeated Lee Sedol in game one (Sedol resigned after 186 moves). I was only able to watch the first 60% of the game before I had to crash, but I was very impressed by the speed at which AlphaGo played its moves - at one point Sedol was down about 8 minutes on the timer and Sedol spent a significant amount of time (upwards of five minutes per move at points) evaluating positions, whereas AlphaGo rarely took more than a minute or two to move. I'm hoping Sedol can pull a Kasparov and come from behind to win the set - I predicted game one would be AlphaGo's best chance of winnning due to being more familiar with Sedol's games than vice versa. It'll be very interesting to see how the week plays out. Huge milestone any way it goes, though, since Sedol was hoping for a 5-0 shutout victory.
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
Re: Go AI beats top professional
Posted:
Mar 11, 2016, 11:40 PM
I'm not very optimistic about it being good news as a challenge for Go players in the near term (say the next decade) due to the amount of processing power Deep Mind had to use to run the program for a "real time" game. Also, I think they'll (DeepMind) likely be moving away from games and on to working to make their innovations apply to solving real world problems. If their program were able to explain reasoning behind a move in a given position being better than another, that would be different, but even if one were able to manage to run the program (likely for days on a position on the hardware most people have available) you would only get the answer of what the program thought was the best move. If a person didn't play as the AI expected (quite possible given a branching factor in Go exceeding that of Pente) the new position would need to be re-evaluated, again taking days. And so on for 200 moves. That would be a single game. That's assuming DeepMind even makes their AlphaGo program freely available...
Retired from TB Pente, but still playing live games & exploring variants like D, poof and boat
