Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Jul 23, 2014 8:20 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 66 posts ]  Go to page Previous  1, 2
Author Message
 Post subject: Re: Threes!
PostPosted: Sat Mar 29, 2014 9:51 pm 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
The closest I've gotten to beating this game is a 1024, 512, 256, 128, 64, 32, 16, and two 8's. It's too bad the the board was crammed and the 8's were on the complete opposite ends of the board. Needless to say I was pretty mad because the next two moves were my last. :evil:

_________________
For all of you that bought a KO 8x8x8: You should have bought a V8!


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Sat Mar 29, 2014 10:03 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
Brandon Enright wrote:
What exactly do you mean by "Monte-Carlo"? It does moves at random? I can't imagine that working very well. Are you using some sort of random move input plus a outcome score / heuristic to choose a random move?

Monte-Carlo-based game players work by evaluating lots and lots of random games and accumulating statistics. The simplest thing to do, which is what I'm doing, is this: for each possible move from the current position, play out lots of random games, until no more moves are possible (following the rules about random tile placement etc.), and keep track of which move statistically generates the highest score. Then, play it. It's cool, because there is absolutely no game-specific knowledge or heuristics in it. But even this almost always wins.

More sophisticated approaches combine Monte-Carlo techniques with tree search, gradually building up a search tree, informed by random playouts, rather than a static evaluator.

My program makes the 4096 tile maybe a third of the time now. It has yet to make 8192, though it keeps getting close. I'm speeding up the move function; that should get me more playouts. I can also try going with smarter playouts, that embody reasonable heuristics, rather than totally random moves.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Sun Mar 30, 2014 4:32 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bhearn wrote:
Brandon Enright wrote:
What exactly do you mean by "Monte-Carlo"? It does moves at random? I can't imagine that working very well. Are you using some sort of random move input plus a outcome score / heuristic to choose a random move?

Monte-Carlo-based game players work by evaluating lots and lots of random games and accumulating statistics. The simplest thing to do, which is what I'm doing, is this: for each possible move from the current position, play out lots of random games, until no more moves are possible (following the rules about random tile placement etc.), and keep track of which move statistically generates the highest score. Then, play it. It's cool, because there is absolutely no game-specific knowledge or heuristics in it. But even this almost always wins.


So if I'm understanding you correctly the algorithm is basically:

For each possible move, do that move and then play completely randomly after that. Then whichever first move was the best for the random games after that is probably the best move to make now.

I wouldn't think this would work because the randomness after each move would dominate the the outcome. That is, a good move followed by random play isn't really much better than a mediocre move followed by random play. I guess that's where statistics come in when you play tons of games to smooth out the randomness to measure the quality of the first move.

How many games are you playing for each move? 1000? 1,000,000?

I should program something like this for threes to see how well it does. Random play with threes ends a lot faster than with 2048. That combined with having some information about the next card could probably do rather well. It will have to wait until next week though, I'm swamped this weekend!

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Sun Mar 30, 2014 10:49 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
Brandon Enright wrote:
I wouldn't think this would work because the randomness after each move would dominate the the outcome. That is, a good move followed by random play isn't really much better than a mediocre move followed by random play. I guess that's where statistics come in when you play tons of games to smooth out the randomness to measure the quality of the first move.

How many games are you playing for each move? 1000? 1,000,000?

A good move followed by random play only has to be very slightly better than a mediocre move followed by random play to be selected. This strategy works especially well when the board gets tight -- it always finds the most likely way out, because that opens up more options for future play.

Depending on the parameter settings, I'm getting a few thousand games per option, per turn. Of course it would be much faster in C++, instead of in JavaScript in a browser, while competing with animation time.

Monte-Carlo methods are actually very powerful, especially when combined with tree search. The best go programs, by far, all use Monte-Carlo Tree Search. All go programs basically sucked until 2006, when MCTS was invented. They have been steadily gaining on professional strength ever since – now the difference is down to a 4-stone handicap. When I first heard about this approach to go, I openly scoffed. And I did so as an AI researcher, and a 2-dan go player. Well, I was wrong.

This is an excellent recent survey paper on MCTS and related techniques:

http://www.cameronius.com/cv/mcts-survey-master.pdf


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Mon Mar 31, 2014 12:33 am 
Offline
User avatar

Joined: Mon Feb 16, 2004 12:49 am
Location: Raleigh NC
I wasted a lot of time on this. I should probably stop.


Attachments:
Screen shot 2014-03-31 at 1.31.00 AM.png
Screen shot 2014-03-31 at 1.31.00 AM.png [ 32.1 KiB | Viewed 1246 times ]

_________________
LE|F
Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Thu Apr 03, 2014 6:58 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I built a Threes "AI" based on naive Monte-Carlo search exactly as bhearn described. It gets a 768 card every time and the median score seems to be about 27k.

I have two ideas for improvement that don't involve just increasing the number of random plays. Hopefully I can get it to reach higher value cards with some consistency.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Thu Apr 03, 2014 11:17 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
I've been screwing with my 2048 player all week, when I should have been working, and it's frustratingly not getting much better, even though it's now much more sophisticated (now a full Monte Carlo tree search, with UCB1 move selection). It almost always wins, gets the 4096 tile more than half the time, and only once so far has gotten the 8192 tile (finally breaking my own high score). I think to do better than this requires playing with an actual strategy -- so far I have refrained from putting any heuristics into it beyond the most basic, wanting to see what would naturally emerge from the Monte Carlo search. It seemed like the right idea here, but I don't think it actually helps much over a more traditional search, because where MC really wins is when you don't have an easy state evaluation function, as in go. Here, you can just look at score, free squares, etc. Moreover, there is an obvious strategy, that the MC approach is not well suited to discover; that would require expanding the tree far too deeply.

My current version, which does as well as any other, doesn't even do random playouts at all; when it gets to the playout point of the MCTS algorithm, it simply returns free squares as the score. With this approach I am getting about 100,000 "playouts" / second on my MacBook Air; each one adds a node to the search tree. Not huge numbers, but hey, it's JavaScript in a browser. Due to the MCTS approach, the search tree grows unevenly, with the more promising branches searched more deeply. This I think does give some kind of win over say Expectimax. I guess if I added a static evaluator based on the strategy I personally play, it would probably do quite well.

It is fun to watch the program repeatedly get itself out of what for a human would be impossible-looking situations. But I was curious how much better than me a computer could do. With this approach, not much, looks like. There is another guy who wrote an AI for it that is better -- it seems to get the 8192 tile maybe half the time, and at least once got the 16384 tile. But it is running in optimized C, rather than in the browser, so not really a fair comparison! It may well be that even "God's algorithm" could not do much better than get the 16384 tile a small percentage of the time.

Anyway I'm learning some things about JavaScript performance. Looking up into a large table indexed by a string is really, really slow. Also it's just fun to do this kind of programming again, explore the behavioral changes as I tweak the program. Last time I did any real game search was before the MC approaches were a thing.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Sat Apr 05, 2014 7:30 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hey Bob, I'm glad I'm not the only one who works on stuff like this even when I REALLY should be working on other duties.

I know Threes is not a far comparison with 2048 but I wrote a Monte-Carlo search and it plays pretty well. I then wrote a board "ranking" heuristic that scores a board based on things like the amount of open spaces, the number of tiles that can be merged in a single move, etc. If I let my program choose the next move based on whichever leads to the best rank it plays significantly worse than the Monte-Carlo search.

BUT... If I change my Monte-Carlo search so that half the time (random) a move is chosen at random and half it is chosen based on whichever leads to the best rank, the game plays significantly better than either approach alone.

My educated guess for why this is better is that playing random leads to dead-ends fast. You have to do so many trials to get lucky and find your way out that even when you do, the higher resulting score for doing so is drowned out by the much more common dead-end scores. By letting half the moves be chosen "smartly" the trial games are able to explore a lot farther from the current position and find ways out of tough situations.

Edit: me belief that randomly doing a "smart" move may have been due to conformation bias and inadequate testing. I'm still running tests but so far it's clear that Monte-Carlo without any smart play is beating all attempts at adding smarts.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Sun Apr 06, 2014 8:31 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I've abandoned trying to add "smarts" to Monte-Carlo search for the time being. Instead I'm trying to be smarter about selecting the next move based on the trial games.

If I use the average final score of all trial games, the result is pretty good. Here are statistics from 32 test plays (only counting the highest card achieved in each game):
Code:
average:
192  :   32/32    (1.000x)
384  :   31/32    (0.969x)
768  :   29/32    (0.906x)
1536 :   11/32    (0.344x)
3072 :    1/32    (0.031x)


So I decided to test using the median score instead. It does MUCH worse:
Code:
192  :   32/32    (1.000x)
384  :   32/32    (1.000x)
768  :   24/32    (0.750x)
1536 :    3/32    (0.094x)
3072 :    0/32    (0.000x)


So I decided to try the geometric mean of the median and average:
Code:
192  :   32/32    (1.000x)
384  :   32/32    (1.000x)
768  :   31/32    (0.969x)
1536 :   12/32    (0.375x)
3072 :    0/32    (0.000x)

I don't think these results are statistically significantly different than just using the average alone. They're obviously a lot better than using the median alone though.

So I decided to try adding more data to the geometric mean. If I divide the trial games into 4 quartiles, than the mean in the divider between the 2nd and 3rd quartile. So I computed the geometric mean between the average, and the three quartile dividers. The results are really good compared to just the average alone:
Code:
192  :   32/32    (1.000x)
384  :   32/32    (1.000x)
768  :   30/32    (0.938x)
1536 :   15/32    (0.469x)
3072 :    1/32    (0.031x)



I'm thinking about building some sort of adaptive system where at first I try all possible moves with equal probability but as data rolls in about the quality of each move, I slowly reduce the chances of trying poor moves and hone in on whichever is likely the best move. That way I don't need to allocate the same number of trial games to the best and worst moves but can instead focus more trial games on the better ones so that it's easier to tell the best apart from the almost-as-good.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Tue Apr 08, 2014 1:54 am 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
Brandon Enright wrote:
I'm thinking about building some sort of adaptive system where at first I try all possible moves with equal probability but as data rolls in about the quality of each move, I slowly reduce the chances of trying poor moves and hone in on whichever is likely the best move. That way I don't need to allocate the same number of trial games to the best and worst moves but can instead focus more trial games on the better ones so that it's easier to tell the best apart from the almost-as-good.

That's basically the idea behind Monte-Carlo Tree Search, but done recursively. It sounds to me like that's the obvious next step here. The paper I linked to above explains how the algorithm works in a lot of detail. The key is the UCB1 (upper confidence bound 1) formula, specifically chosen to appropriately balance exploitation of known good moves with exploration of undersearched moves.

I made my 2048 MCTS playouts smarter, embodying simple rules that I use myself when I play. Now the MCTS program is much better. It generally makes the 4096 tile, and often makes the 8192 tile. High score so far is 172,812, with a 8192 tile and a 4096 tile.

I think this is probably the right approach for this game. Still haven't posted it to github... I will soon. I use git all the time, but I'm new to figuring out github, and how to publish pages there. Plus I want to clean the code up before pushing it (github repositories are public unless you pay).


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Thu Apr 10, 2014 11:31 am 
Offline
User avatar

Joined: Sun Aug 04, 2013 4:50 am
Location: The Netherlands
A vid about 2048!
https://www.youtube.com/watch?v=OO4tA5i7X9g

And a follow-up vid as well:
https://www.youtube.com/watch?v=TXys0aHASFE

_________________
- Eric


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Thu Apr 10, 2014 4:03 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
1NSAN3 wrote:

Fun, but most of what they assert is wrong, because it assumes that only twos appear. Really kind of defeats the purpose of the videos.

This is what my program is up to:



Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Fri Apr 11, 2014 2:18 am 
Offline
User avatar

Joined: Sun Mar 15, 2009 12:00 am
Location: Jarrow, England
I bet the program was devastated not to break the 300,000 point barrier :shock: :lol:

_________________
My Shapeways Shop: http://www.shapeways.com/shops/gus_shop

Image


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Fri Apr 11, 2014 10:41 am 
Offline
User avatar

Joined: Sun Aug 04, 2013 4:50 am
Location: The Netherlands
bhearn wrote:
1NSAN3 wrote:

Fun, but most of what they assert is wrong, because it assumes that only twos appear. Really kind of defeats the purpose of the videos.

I'm glad to see you didn't watch video's in their entirety! That would be a shame. :roll:

_________________
- Eric


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Fri Apr 11, 2014 5:12 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bhearn wrote:
This is what my program is up to:


That's incredible! 16384 = 2^14 and there are only 16 spots. What percentage of games would you estimate your program can reach 16384?

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Threes!
PostPosted: Wed Jul 09, 2014 11:40 am 
Offline
User avatar

Joined: Fri Mar 06, 2009 9:23 pm
Bump!

Looks like I missed the boat on this one, I have not been on the forums much lately.

I have also caught the 2048 bug, playing more times than I care to count at this point.

Attachment:
File comment: 2048 high score (iphone app)
2048 high score.jpg
2048 high score.jpg [ 34.86 KiB | Viewed 134 times ]


I have pretty much reached my limit of playing, each game at this level takes many hours and keeping concentration for that long is just impossible for me.

As an exercise I'm going to pick up programming (c++) and write an AI that plays, like bob has. He has set the bar pretty high, but I have quite a few ideas about how I want to approach the board evaluation methods. I don’t really know how to program so that will definitely be the limiting factor, but I'm hoping I can push through that with some diligence and google-fu. I'm sure I’ll make a post about it at some point here on the forum :)

_________________
--Eric Vergo

My Shapeways shop


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 66 posts ]  Go to page Previous  1, 2

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group