Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> This is getting scary
        
(Message started by: omar on Dec 10^th, 2017, 1:51pm)

Title: This is getting scary
Post by omar on Dec 10^th, 2017, 1:51pm

A year after defeating the top Go player, the Google DeepMind project is continuing to make astonishing progress. Now they don't even need to use a database of expert games to train the AI, they just give it the rules and let it play itself to produce super human AI players. And not just for one game. The same AI can play Chess, Go and Shogi. It masters these games in a matter of hours.

https://goo.gl/c8RWx3

https://arxiv.org/pdf/1712.01815.pdf

If anyone is interested in reproducing these results for Arimaa and making the bot and bot generation code open source (along with a published paper describing the work), I would be willing to award a prize of $10,000. The program has to win a 10 game match against bot_Sharp2015CC to prove superior human level play.

Title: Re: This is getting scary
Post by christianF on Dec 10^th, 2017, 3:11pm

What exactly would you consider scary about these developments? I'm inclined to think your thoughts go beyond the fact that these programs can learn to play two-player strategy games - presumably all of them - on a superhuman level in a matter of days (or even less).

Title: Re: This is getting scary
Post by Lion on Dec 11^th, 2017, 8:12pm

Nice! I was actually seriously thinking about doing this before the new challenge was announced. Now I've got no excuse for not trying.

By the way, Omar, could you please post sharp_2015 (CC and other time controls) onto the bot ladder? This would be of great help -- and not just with respect to the new challenge.

Title: Re: This is getting scary
Post by Belteshazzar on Dec 17^th, 2017, 2:18pm

on 12/10/17 at 13:51:08, omar wrote:

https://www.sciencealert.com/it-took-4-hours-google-s-ai-world-s-best-chess-player-deepmind-alphazero

For some reason, in the displayed url there was a space in the word "chess", which broke the link for me. I'm using Firefox.

At this rate, there could be a challenge to create a game, let AI play itself, and then defeat the AI at the game.

Title: Re: This is getting scary
Post by omar on Dec 17^th, 2017, 7:29pm

on 12/10/17 at 15:11:22, christianF wrote:

Yes, exactly. Applying this to games is a good testbed, but once the techniques and breakthroughs have been achieved, they can be applied to other problems. The scariest part for me is how fast progress is being made now and that the same neural net is being used to play multiple different games. Further progress can start us down the slippery slope of general AI. Maybe we've already started.

Reminds me of this article:
https://waitbutwhy.com/2015/01/artificial-intelligence-revolution-1.html

Title: Re: This is getting scary
Post by omar on Dec 17^th, 2017, 7:35pm

on 12/17/17 at 14:18:02, Belteshazzar wrote:

Seems like the original URL was being too long and not being processed right.

https://www.sciencealert.com/it-took-4-hours-google-s-ai-world-s-best-chess-player-deepmind-alphazero

I have shortened it:

https://goo.gl/c8RWx3

Title: Re: This is getting scary
Post by omar on Dec 17^th, 2017, 7:40pm

on 12/11/17 at 20:12:38, Lion wrote:

I've added Sharp2015* to the bot ladder.

Title: Re: This is getting scary
Post by Belteshazzar on Jan 5^th, 2018, 7:05pm

on 12/10/17 at 13:51:08, omar wrote:

I guess I don't know enough to understand exactly what this would entail. Giving the Arimaa rules to the same AI which has mastered the other games sounds simple enough. But if it were, I'm sure you'd do it yourself.

Title: Re: This is getting scary
Post by Lion on Jan 5^th, 2018, 8:40pm

The biggest obstacle might turn out to be hardware (computational time) ... but we shall see. I've created an account named "bot_0ArimaaZero" and plan to start working on this in a few weeks.

Title: Re: This is getting scary
Post by aaaa on Jan 8^th, 2018, 5:12pm

This thread should not go without a shout-out to Leela Zero (https://github.com/gcp/leela-zero), a distributed effort to replicate AlphaGo Zero. Since it's highly unlikely for any similar project for Arimaa to get anything near the same amount of computational resources, I have a hard time seeing a particularly strong Arimaa player coming into existence this way any time soon. On the other hand, it might just be within the realm of possibility to at least witness some kind of interesting evolution going on in playing behavior within a decent time scale.

Title: Re: This is getting scary
Post by Hippo on Jan 17^th, 2018, 1:53am

@Omar, in original challenge you have limited computationa power by the common PC of fixed prize.

Don't you think about adding the simillar constraint to the new challenge?

The original challenge was limited by year 2020.

Don't you think about adding simillar constraint as well?

Title: Re: This is getting scary
Post by elescondite on Jan 19^th, 2018, 9:40pm

Hi Omar, great to see that you're still interested in the development of general artificial intelligence.

Just FYI, some time ago I created a bot (bot_eliminator) with this kind of thing in mind. The bot uses a set of neural networks for its evaluation function. There are multiple levels, starting with each square of the board, which feeds into a net that evaluates quadrants, which feeds into a net that evaluates the board itself. The neural networks were randomly initialized, and they have been playing each other using a highly modified version of the roundrobin.py script included in the AEI package. Over a year ago I purchased a server on eBay for a little over $1000, and all it does is run this 24/7. (For reference, it is a dual processor E5-2670 Sandy Bridge generation, 8 cores/processor, 2.6 GHz, 32 GB RAM.) It currently plays games using a 2-ply depth search, and currently it completes approximately 130 games/hour. It does not use any video cards at the moment, because I have not had the time to invest in incorporating CUDA support. I did recently add AVX support, though frankly the neural networks are pretty small, and they aren't the performance bottleneck at the moment. I have a group of 64 bots that play each round. The top 32 get to survive and "mate", and the bottom 32 die. Bots mate by randomly selecting groups of 32 values from one of the parent neural networks, and then adding some occasional random mutations to the values passed on. During the mating phase, each bot randomly mates 8 times, and the 8 children then fight to the death. The top bot out of the 8 is selected to replace one of the 32 that were killed. This setup has been running for about 16 months now. I have improved the performance of the software over that time from approximately 80 games/hour to the current 130. It has been a very interesting project.

So, after 16 months of computing, the bot is, well, not very good… I have played it against various bots in the game room, with some interesting results at times. I was very surprised when my bot won by immobilization, for example. In general, it appears that the bots have evolved to try to bottle up their opponent, which isn't all that effective against a reasonable player. I am assuming that over time the bots will evolve better strategies, but the evolution time appears to be an enormous. Some better techniques are needed.

The Google AlphaZero engine is based on a Monte Carlo approach, I believe, and I think that technique has more promise than I originally thought. In essence, their approach tries to pick the best move, rather than trying to pick the best board. It's a minor distinction, but pretty important one in that focusing on the best move automatically prioritizes your search order, as opposed to my case where I have to discover "killer moves" to try to optimize pruning. Based on the limited reading I have done about bot_Sharp, I believe lightvector put quite a bit of work in identifying promising moves. This really is the key to strengthening play. The quicker an algorithm can identify promising lines, the more effective pruning will be.

I wish I had more time to devote to this. Unfortunately, I have a day job that demands my attention… :-) Still, I am trying to accomplish exactly what you are proposing. I think Arimaa provides an interesting challenge, because I think it is probably more resistant to the Monte Carlo approach used by AlphaZero. Of course, that was originally the case for chess, and they have clearly overcome some of the limitations. They are not exactly using desktop hardware at the moment for their bot, either. They have developed custom ASICs that process their neural networks even faster than standard video cards. Still, I suspect that this technology will become more commonplace over the next 10 years, so I don't really hold that against them. But it does mean that a six-year-old used server is at a unique disadvantage when trying to compete with AlphaZero.

I do intend to make modifications and keep trying. If I get anywhere with it, you'll be the first to know.

Lance

Title: Re: This is getting scary
Post by Lion on Jan 20^th, 2018, 2:38pm

Great info. Thanks for sharing. How many games in total has the bot played against itself?

Title: Re: This is getting scary
Post by elescondite on Jan 20^th, 2018, 11:35pm

I don't actually know the exact number of games played, though I can estimate. Each round of 64 can require a total of 2016 games to complete, though I have modified the script to continually keep a tally of wins and losses, and schedule winning bots to play subsequent games. The script plays 32 games simultaneously, one for each hyperthread in the system. Obviously some games finish quickly, and others will go on forever if you let it. I set an upper time limit of 60 minutes for each of these games, and then choose the winner on whichever bot has the most pieces, regardless of their "value". (I wanted to avoid injecting my valuation of the pieces.) As the top bots play, the bottom ones get games only to allow the top bots to complete the round. As the bottom bots accumulate losses, they eventually have too many losses to make it into the top 32. When the top 32 bots have been established and it is numerically impossible for it to change, the script concludes the round, avoiding playing unnecessary games. It seemed like a great idea when I wrote it, but in reality it doesn't generally save that many games during the round of 64. For example, I just checked and the last round played 1999 games, avoiding 17 out of 2016. So, not a real big deal… But it does help during the next part. The eight offspring of each bot fight to the death. That's 28 games if they must all be played, but if one bot dominates quickly, several games can be avoided each round. (Note that each of these games gets two threads, and 16 simultaneous games are played, to keep the processors loaded.) Sometimes a bot dominates, and sometimes it doesn't, but I'm going to estimate that on average 20 games get played. So that's 32 offspring times 20 games on average, or 640 games during the "reproduction" phase. Add the 2000 for the combat round, and that's 2640 on average per generation. I haven't kept close track, but I believe there have been a little over 300 generations over the past 16 months. (I have things sped up a little bit now, and now I'm getting a generation every 23 hours or so. It used to be a little over 36 hours.) So that math works out to around 800,000 games.

I was kind of hoping it would be a little better with that many games… :-) Having said that, there are a total of 1851 weights in the various neural networks that have to be chosen "correctly". Because this approach has been evolutionary, with no reinforcement learning about “correct" evaluations, it takes a long time to get that many numbers set right. And really, it's a very tiny neural network, perhaps too small. Still, with only 300 generations, there just haven't been enough iterations to know for sure.

I would have done something differently already if I had the time, but it only costs me electricity to let the server run and see what happens.

Title: Re: This is getting scary
Post by Lion on Jan 21^st, 2018, 6:04am

Looking at the AlphaZero paper (on Arxiv), the bot needed around 6 million games to get really strong at any of the three games (Go, chess, shogi) . At 3 million games, the bot was much weaker, but it was apparent that quick progress was being made at that point. At less than 1 million games, the bot was weak indeed. On the one hand, these numbers are encouraging, since it suggests your bot might start making quick progress after only 1 million more games or so. On the other hand, this translates to approximately another 2 years, or so, given your current system. Still, looking at some recent games by bot_eliminator, it looks like things are on the right track.

Title: Re: This is getting scary
Post by elescondite on Jan 21^st, 2018, 10:23pm

Thanks for the encouragement! It will be interesting to see how it evolves.

Title: Re: This is getting scary
Post by omar on May 24^th, 2018, 10:41pm

User DeathCure sent me an interesting link worth sharing.

This article mentions that Alpha Go runs on about $25 million in hardware.

https://www.inc.com/lisa-calhoun/google-artificial-intelligence-alpha-go-zero-just-pressed-reset-on-how-we-learn.html

https://bit.ly/2z10X50

Title: Re: This is getting scary
Post by DeathCure on May 31^st, 2018, 8:22pm

on 12/17/17 at 14:18:02, Belteshazzar wrote:

At this rate, there could be a challenge to create a game, let AI play itself, and then defeat the AI at the game.

Such a game can't be created, an AI that plays itself means it has genetically developed to know how to respond to all moves made (AlphaZero evaluates 80K moves per second - https://www.chess.com/forum/view/general/alpha-zero-stockfish-number-of-moves-per-second-vs-hardware-debate). The only way to beat it would be to either start the game with a forced win for the player, or make the game have some luck factor in it.

Title: Re: This is getting scary
Post by apophis on Jan 29^th, 2019, 9:36pm

Curious if anyone has made progress on this challenge. I found this interesting tutorial the other day that could be used as a starting point:

https://medium.com/applied-data-science/how-to-build-your-own-alphazero-ai-using-python-and-keras-7f664945c188

Note: for some reason the link above includes a space that you have to remove for it to work. I can't seem to get rid of it in this post.

Title: Re: This is getting scary
Post by RightfulChip on Oct 25^th, 2019, 12:53am

Quote:

Curious if anyone has made progress on this challenge.

I will be taking on this challenge and have an engine self playing now. It will be interesting to see if, and how fast it learns, as well as how many games it takes to be competitive.

For reference, on my machine, the engine has learned:

Connect4 - 3 hours to perfect play.
Quoridor - 4 days for high level play.
Arimaa - ???

Title: Re: This is getting scary
Post by omar on Oct 30^th, 2019, 7:32am

That's awesome. Please keep us posted on your progress.

Title: Re: This is getting scary
Post by cyberix on Aug 29^th, 2020, 5:03am

The chess community has setup the Leela Chess Zero project for developing a chess AI comparable to Alpha Zero. Anyone can participate in providing computational resources to the project. Perhaps the same open source software could be used for a Leela Arimaa Zero project.

See https://lczero.org/ for details.