Friday, March 8, 2013

Drop7 with Lego Mindstorms NXT

I posted a video on youtube of a Lego Mindstorms NXT robot of mine, playing Drop7 in sequence mode to a score of 5,205,955.  Some of my friends told me I should blog about it to explain how I did it, so here is a rather lengthy explanation of everything that went into the video.  The robot plays to the end of Level 71, it clears the board 23 times, the longest chain is x29 and is worth 367,087 points. There are also chains of x26, x25, x24, two x23s, two x22s, etc, etc.


The Inspiration

I started playing Drop7 on my phone a few months ago and eventually stumbled across a video of someone who scored 5,000,000 points on Drop7 in sequence mode.  For those of you that have never played Drop7 is it sort of like a math based version of Tetris.  You have a 7x7 grid where you select which column to drop a disc in.  You earn points by making discs explode, preferably in a long chain which earns more points. Making a disc explode is easy, if you place a disc with a 4 in a column with 4 discs, all of the 4s in that column explode.  The same rule apples to having 4 discs in a row, when that happens all of the 4s in the row explode.

Anyway, I started thinking about how the person that made the video figured out what sequence to play the discs in to get such a high score.  They were playing in sequence mode which means that the same discs are played every time you play the game.  I was sure they wrote a program to figure out how to get such a high score and I like to do geeky little projects so I wrote my own program that simulates Drop7.   I figured I would have it run through a few million permutations that one could play the discs in and see which permutation produced the highest score.

Permutations

Just how many permutations can the discs be played in? Let's say you only know what the first four discs will be in sequence mode. There are 7 different columns you can drop each disc in so the permutations will be as follows (the numbers represent which column to place a disc in):
CountPermutation
#11 1 1 1
#21 1 1 2
#31 1 1 3
. . . .
#23997 7 7 5
#24007 7 7 6
#24017 7 7 7

This comes out to 7^4 or 2401 permutations. OK 2401 isn't such a huge number for a computer but let's expand this and assume you know what the first 100 discs are in sequence mode.  7^100 is  a GIGANTIC number of permutations,  3.2344765096247579913446477691002e+84 to be exact.  That number is so huge it is hard to wrap your head around it. To put it in perspective if you stacked up 3.2344765096247579913446477691002e+84 sheets of printer paper the stack of paper would be about 3.29 light years tall! Needless to say I don't have access to enough computing power to crunch through that many permutations of Drop7 within the next few billion years.

I decided to break the first 100 discs down into groups of 8. I could run through every permutation that one could play the first 8 discs in, find the permutation that resulted in the best score and then move on to the next batch of 8 discs, etc. This wouldn't give the absolute best possible score one could get out of the first 100 discs but it would spit out a sequence to play the discs in that would produce a very high score.

Drop7 Simulator

At this point the little simulator program I wrote was in a language called PERL which is an easy language to program with but is slow compared to a complied language like C. It took my PERL program quite a while (days) to crunch through the first 100 discs in groups of 8 so I rewrote my simulator in C which is much much faster, in this case the C version was 74x faster than the PERL version!!  I then moved from analyzing the discs in groups of 8 to groups of 12.

I was doing all of this on my home PC which has four 2.8Ghz cores.  Crunching through the discs in groups of 12 took a long time, each group of 12 was 13.8 billion permutations (7^12) to simulate.  I knew I wouldn't be able to do move up to groups of 13 on my home machine, not unless I was willing to let it run for months.  The larger the groups of discs you analyze the higher scoring sequences the program is able to find so I wanted to move from 12 to 13 if not higher.  I was chatting about this little project with a co-worker and he gave me access to one of his machines at work that has 32 cores.  It is a Linux machine running on a Cisco UCS B200-M3 to be exact.  It isn't often that one maxes out 32 cores for days on end...here is a screen capture that shows them all pegged at 100% :)


In the end I was able to crunch through the discs in groups of 14, each group of 14 has 678 billion permutations.  I knew what the first 680 discs were in sequence mode which means there were ~49 groups of 14 discs to analyze.  So 678 billion permutations per group x 49 groups x 14 discs per group = 465 TRILLION discs were "dropped" in my Drop7 simulator.  Even with 32 cores running 24 hours a day it took weeks for it to produce the sequence I used for the video.

I posted all of my code for the Drop7 simulator on github.  If anyone wants to tweak it to find a better Drop7 algorithm you have my permission to use my code.
https://github.com/dwalton76/Drop7-Sequence-Mode

Sequence Mode Discs

I found a post on a forum somewhere that listed all of the discs that would come in sequence mode for the first 10 levels.  To figure out the future disc beyond level 10 I would play to level 10, then record a video of myself playing, then watch the video to figure out what the new discs were.  The only problem with this approach was that I had to keep playing from the beginning of the game up to Level 10, or 11, or whatever level I was stuck on at the time, in order to figure out what the next discs were.  This was taking a while and either my wife or I jokingly said that we should build a Lego robot to play it for us.  I'll go into the robot more in second but here is a table of all discs (a disc with a "?" means it is a solid disc) for the first 71 levels of sequence mode.  Should someone else ever decide to do a project like this they shouldn't have to analyze game film of themselves playing Drop7....that part was pretty boring.

LvlLevel Up DiscsOne-By-One Discs
16?4?5?7?5?1?3?2116?455?5?1?615753632?64?25712?51?3?2?4
21?3?6?3?3?4?4?552?1?6?2?3232?3?627763?2?6?474543616?1
36?4?5?7?3?3?4?57?4635?743526?2721474?42735?551?7?
42?2?7?1?7?1?5?77?27?23?232?26?5?4?6?57?267?7?5?423?723
52?3?7?1?5?4?1?2?13?413?1?161?575?2556?35?4?57413?5
65?2?3?6?2?7?1?1647?37377?44?151?514?43?474314?
73?6?7?1?3?7?3?55?7?5?5?136?2?2375456167?112?73
81?5?4?1?6?3?3?722?7?74?6?57576?746516?347?75
93?7?3?1?1?1?4?26137?647376?55?624335?74?7
102?1?6?3?2?3?7?1?5?43?651?7?7156174?636111?
115?3?4?5?4?5?3?5647744?2?5?3?4?4?4?3?43?32?14?
126?1?6?6?7?3?3?7275?3?63?2?462257175?37
136?4?2?5?7?7?5?143?227?3242?6713462?4?
147?7?4?2?5?1?1?3?2?275?567?1?1?43?43?165?
155?1?3?3?5?3?5?22?5?31?72211777?144
164?7?4?5?7?6?7?11?4?44441457?224?7
171?4?3?3?5?2?3?45323?714?7?7?32?62
181?5?1?3?6?4?3?3?225?6?46273?761
191?5?7?4?1?7?6?2?35465?6?13411
207?3?6?7?1?6?2?1?1364?1?1?6773?
213?2?1?2?5?5?6?53346342?11?
226?4?2?2?5?5?2?45?3?665?624
236?2?7?3?7?3?2?177152?27?
242?3?6?6?4?6?1?5323?212
254?5?4?7?5?6?2?1?5?6?356?
264?4?6?6?2?5?5?27?615?
271?3?3?5?4?4?7?4?4371
283?4?5?2?2?3?3?22773
292?5?1?4?5?5?6?6216?7
303?3?4?6?1?2?4?235?14
312?5?1?2?6?2?5?47311
325?1?1?5?4?2?3?714?45
337?2?6?4?7?3?3?6?44?34
346?3?7?2?5?6?3?46172?
355?4?1?6?7?4?6?525?51
364?6?3?7?3?3?5?151?63
374?7?7?6?3?7?7?67374
381?5?1?1?6?5?5?5224?7
392?2?6?4?2?1?2?44445?
401?6?5?4?1?2?5?65346?
411?1?2?2?6?1?1?1?667?2
427?4?3?7?3?3?2?7?6134?
432?6?2?6?5?2?4?277?4?6
446?4?6?3?4?4?3?5363?5?
457?2?3?4?5?4?6?14472
462?3?1?7?3?7?6?65?722
473?7?7?5?2?1?1?417?3?7
487?4?5?6?3?3?6?654?21
492?2?5?1?5?7?7?55362?
505?6?1?7?2?7?4?36?523
512?4?7?3?2?6?7?6417?7
525?3?5?7?5?4?6?2?1774?
534?2?6?6?1?5?7?43114?
541?1?6?3?1?6?2?3?7?31?5
554?2?6?4?7?1?6?624?16?
561?3?4?1?3?2?3?7?71?4?7
576?4?7?7?6?5?4?731?11
584?5?6?7?6?7?3?1367?2
595?2?4?7?5?3?6?47741?
604?5?2?6?5?1?5?2?3?7?75
611?6?3?5?4?7?3?237?17
621?7?5?2?5?6?5?524?44
637?6?1?4?3?4?5?71252?
643?2?7?6?1?5?7?4?464?4
656?6?7?5?4?2?2?2?5713
663?6?3?3?2?4?7?33?452?
674?2?7?5?4?6?2?31451
684?3?5?5?3?3?3?13?17?5?
692?7?3?1?4?5?2?36?4?33
702?3?1?3?3?3?3?524?73
714?7?5?5?5?6?7?17?4?16

Scoring

You get 7,000 points for each level and 70,000 points every time you clear the grid. You also get points when discs explode but the number of points depends on the "chain" length of your explosions.  The formula for determining the value of a chain explosion is 7*n^2.5 where 'n' is the chain length.

Here is a table that shows the value of a disc for a given chain length along with the total score for that chain...assuming only one disc exploded at each level of the chain. The longest chain I have been able to find is x29.

Chain
Length
Disc ScoreTotal Score
177
23946
3109155
4224379
5391770
66171387
79072294
812673561
917015262
1022137475
11280910284
12349113775
13426518040
14513323173
15609929272
16716836440
17834144781
18962254403
191101465417
201252177938
211414692084
2215891107975
2317758125733
2419752145485
2521875167360
2624128191488
2726515218003
2829039247042
2931702278744
3034506313250
3137454350704
3240548391252
3343790435042
3447184482226
3550730532956
3654432587388
3758291645679
3862309707988
3966490774478
4070835845313
4175345920658
42800241000682
43848721085554
44898931175447
45950881270535
461004591370994
471060081477002
481117381588740
491176491776389

The Robot

I should be clear here that the robot I built doesn't make any decisions on its own about where to play the disc, the robot can't see the screen and therefore can't play the game by itself.  My Drop7 simulator figured out what sequence to play the discs in to achieve a high score, I just programmed the robot to touch the screen in a specific pattern so that the discs would be played in that sequence.

The Stylus

One tricky part of this project was figuring out how to get the robot to touch the screen in a way that would register with the iPad.  iPad screens aren't pressure sensitive, they are capacitive screens so you can't just stick a stylus in a robot's hand and have it work.  I tried grounding a stylus but that didn't work either.  After a bit of googling I found where some people had used frozen sausages as a stylus and that made me wonder if that would work for a robot since it is made of flesh like your finger.  I was all out of those little breakfast sausages but I did have some hot dogs in the fridge so I gave one of those a try and BINGO!



Now there are a few downsides here
  • Hot dogs touch a large part of the screen at once compared to a normal stylus
  • Hot dogs dry out and the touch doesn't always register
  • Your iPad smells like a hot dog at the end of the day
  • If you think little kid fingers can make your iPad screen disgusting, try touching it with a hot dog a few hundred times.
I eventually figured out that when I had tried grounding a regular stylus I wasn't grounding it properly and that is why it didn't work.  You have to take the little rubber tip off the end of the stylus, wrap some wire around the metal there, then put the rubber tip back on.  Ground the wire and that should do the trick.

Hardware

I went through a few different styles of robots before settling on the one used in the video.  My original robot is the one you see in the hot dog photo.  It had problems consistently dropping discs in column 1 and column 7 though because the angle was so narrow by the time the motor moved the stylus that far to one side.

Next I tried building a little rover that would drive forward and backwards to the appropriate column.  This wasn't accurate enough though because if the wheels slipped at all it would end up dropping the disc on the wrong column.














I decided I needed a platform that moved on a track so I could get the stylus exactly over the middle of a Drop7 column.  I'll post some instructions later on how to build the robot.  The only parts I used that did not come with the Lego Mindstorms kit were the gear racks.  These were used to move the platform from side to side.




Here you can see the gear racks underneath the platform.  A motor turns a gear which moves the gear rack which in turn slides the platform to the left or right on the track depending on which way I tell the motor to turn.  Once the platform is centered over the right column, the motor on top of the platform turns a few degrees to touch the screen with the stylus then reverses direction to pick the stylus up.








Software

I am completely new to the world of Lego Mindstorms but I have to say it is amazing they are as popular as they are given how horrific the NXT-G software is that Lego provides.  It is slow as Christmas, it locks up, it crashes, things that once worked randomly stop working, etc.  Needless to say I didn't use it for very long until I started googling for an alternative.  I settled on BricxCC which allows you to program Lego Mindstorm in NXC "Not eXactly C".  If you have any programming experience at all I would say go with BricxCC over NXT-G, it will save you a lot of frustration.

My BricxCC code for this project is also on github.

The End

This was a lot of fun. I hadn't written a line of C in 6 years and had never used Lego Mindstorms so I learned a lot via this little project :)



6 comments:

  1. Hi, great work there, how about the timing of the press by the robot? Was that also programmed?

    ReplyDelete
  2. Thanks :) Yep, once the platform was over the right column I had the C motor turn 25 degrees which would touch the stylus to the screen, wait 100 milliseconds then turn in reverse 25 degrees to lift it.

    ReplyDelete
  3. But I mean the interval of each press, because sometimes u need to wait for a long combo until u can press for the next step.

    ReplyDelete
  4. ah, yes the wait interval is also programmed. I know how many discs will explode, will there be a level-up, will the board clear, etc so I used that to figure out how many seconds to pause before continuing. I did think about using a sound sensor to figure out when the disc had stopped exploding but the base lego kit didn't come with one and I never got around to buying one.

    ReplyDelete
  5. Does it come with light sensor? If so, you could 'watch' for the new disk to pop up at the top of the screen.

    ReplyDelete
  6. yep, it does come with a light sensor. That is a good idea, I imagine that would work.

    ReplyDelete