00:00:15.379
Thanks all for coming today. I'm Cameron Dutro, and my talk is titled "Cheating with Ruby."
00:00:21.410
I work at a company called Lumos Labs, where we create a product called Lumosity. I want to give a special shout-out to my wonderful coworkers sitting down here in the front row for being so supportive. You can find me online on GitHub at camerontron and on Twitter at @camerontron.
00:00:37.440
Now, a couple of personal things about me: I am not a mathematician, nor am I a computer vision expert, and I am definitely not an LA Rams fan—Seahawks all the way! By the way, I got married this year, which was a lot of fun. Thank you!
00:00:49.800
This is my wife, Kelly, and this is my cat, Chester. I figured that if Gorby Puffs Thunderhorse gets to be in slides, Chester should get to be in there too.
00:01:12.450
So let's talk about cheating. Chances are, if you have any moral compass, you understand that cheating is wrong, right? So why are you here? Well, hopefully you think I'm super handsome and you understand that occasionally, cheating can be a good thing for educational purposes.
00:01:19.619
In this case, cheating provided me with the opportunity to explore some elements of Ruby that I hadn’t really gotten to explore before, like image manipulation and computer vision. It also helped me unblock myself from this game called "Pet Detective," which we're going to discuss in serious depth.
00:01:39.020
This game is one of the many brain games we have at Lumosity. If you haven't used our app before, we offer around 35 mobile games and also some on desktop. Pet Detective is designed to help you improve your problem-solving skills. Your goal in this game is to return all the pets to their houses.
00:02:03.299
On the screen, you can see several pets and their corresponding houses. The image of each pet appears on the front of its house. Your car drives around picking those pets up and dropping them off at their homes along the black roads shown on the screen. Each block traveled costs one gas unit, and in this screenshot, the number above the car indicates you have 25 gas units for this round.
00:02:22.800
If you run out of gas before you've dropped off all the pets at their respective houses, you lose the round. By the way, your car can only hold four pets at a time, which is indicated by the bar at the bottom of the screen next to the replay button where your pets will appear when you pick them up.
00:02:48.350
Your car automatically travels along the best path, so as a player, you don't direct it manually up, down, left, or right. Instead, you simply tap on a pet or a house, and the car chooses the shortest path available. Let’s run through an example of how a round might work.
00:03:20.610
First, I pick up a turtle. With 25 gas for the round and no pets currently in the car, I now go to the right, up, and to the left, costing me four gas units. The turtle is now removed from the game board and added to my car.
00:03:37.830
Next, I will go up one square to pick up the Siamese pet. This costs an additional unit of gas, bringing the total to five gas units used. Now, both the turtle and the Siamese are in the car. The next step is to drop off the turtle, which is located two spaces away, leaving me with 18 gas. The turtle is now no longer in the car.
00:04:04.740
Next, I drop off the Siamese, which is six gases away, leaving me with zero pets in the car and 12 gas units remaining to complete the rest of the board.
00:04:23.630
The game mechanics are fairly simple, and you can progress through it with ease. Early levels are designed to help you learn how to play. However, as I progressed to levels six through eight, it became more challenging.
00:04:43.880
I noticed that levels eight to ten made me sweat a bit because they were getting really hard. By the time I reached levels eleven and twelve, my brain was just exploding, as they presented extremely difficult puzzles. I was stuck at level twelve, which spurred me to develop something called Pet Detector.
00:05:07.190
Considering that the game has a total of twenty levels, I found myself wondering how I would get past level thirteen, fourteen, and so on. I thought about what I really wanted from the game and realized I just wanted to know how to play it smarter. I was determined not to get the right answer handed to me—that'd be true cheating.
00:05:40.670
Instead, I wanted to learn what I was doing wrong. Was it best to pick up the nearest pet first? I had no idea. I wanted to discover the right order after the game concluded.
00:06:10.820
As I reflected on my experience, I realized I could leverage my knowledge of Ruby and the Ruby gem RMagick to manipulate image data. Understanding the game's grid layout and the parameters affecting the game would also aid in my quest to find a solution.
00:06:33.980
I created a Ruby gem called Pet Detector, designed to analyze a screenshot of the game. It would extract the locations of all the pets, houses, and roads, attempting to generate an in-memory map of the entire game board.
00:07:05.580
Using Dijkstra's search algorithm, Pet Detector could find the shortest distances between all pets and houses, providing an effective solution path. You pass the relevant file, level, and gas into the script, and it provides the correct answer.
00:07:39.460
I am about to do a live demo without fully explaining how it works yet. So, just keep your fingers crossed that it works. I will start by firing up my terminal, which is running a copy of the backend. Here’s the Pet Detector repository.
00:08:17.500
Now, I’ll go to my iOS simulator and navigate to the game. Let’s play level twelve since that’s the one I struggled with. I should note this is a simulated version, and I haven’t made it past level sixteen yet.
00:08:50.270
The game starts up, and I take a screenshot, saving it to my desktop. Now I’ll run a command to invoke Pet Detector.
00:09:04.010
The program should now show the order in which I need to pick up and drop off the pets. Just to show that I’m not cheating here, the screenshot is exactly the same as what’s on this display.
00:09:27.440
Let's see if it works: First is the cockatiel, then the husky, followed by the turtle, Siamese, other pets, and so on. As you can see, it provides the optimal route.
00:10:11.840
Let's do one more demo, this time with some debug output and a simulation of how the game could be solved. I’ll delete the previous screenshot.
00:10:43.000
Now I will run another round in the same game. I also want to integrate some features that would simulate the path visually instead of just showing text.
00:11:09.740
I saw an incredible graphics talk from Ryan Davis, and I thought to use a similar approach to illustrate the route the car would take rather than print text just telling you where to drop off and pick up. I’ll enable debug mode and run level twelve again.
00:12:49.460
It should now output not only the answer but also debug information, showing locations of pets and a simulated route.
00:13:40.680
Okay, so that was Pet Detector. Does it work every single time? No, but I’m really glad that it worked twice in a row for you today. Now let’s discuss how Pet Detector operates by analyzing the game board and ultimately solving it.
00:14:45.560
First, we identify the boundaries of the game board. The technique I used is simplified and helps to define the working area in 2D space. The top level API design involves loading the level information and corresponding grid data.
00:15:51.310
I utilize the boundary detector to find the outer edges using specific probing techniques to determine the overall rectangle dimensions.
00:16:06.290
Probing operates by starting at one edge, such as x equals 0 or y equals 0, and stopping when a pixel of a certain color is encountered, determining the edges of the detection area. After performing a series of probes, we gather the coordinates to evaluate the outer boundaries.
00:17:20.160
Next, we divide the game board into equal-sized quadrants and overlay them over the image, which helps to analyze the features within those quadrants.
00:17:59.520
This allows us to clearly identify the track, pets, and houses in each quadrant, which forms the basis for detecting the entities relevant to the game.
00:18:42.620
With this established framework, we begin building accurate histograms of the images from the game, filtering out any background noise while comparing to the original game assets.
00:19:56.890
Initially, I tried using naïve histogram comparison, but accuracy was low. I later improved it significantly by utilizing perceptual hashing, which allowed me to determine similarity between images based on their overall content.
00:21:36.460
This method became drastically more reliable, allowing the algorithm to recognize pets and houses accurately across all levels.
00:21:59.410
The animal detector goes through each quadrant, assesses the image for animals or objects, and pulls out important data. We then assign these to their respective locations on the game board.
00:23:13.260
Next, we define the roads in the same manner as finding boundaries, utilizing similar probes to ascertain the locations of pathways and ensuring that we account for any overlapping objects like houses.
00:24:33.870
Now that we have identified all items, we need to establish a logical sequence to visit them. This requires constructing a graph from containers, thereby outlining the distance between each pet and house.
00:25:24.490
Dijkstra's algorithm is then employed, which provides the shortest route options necessary to solve the game within set parameters. This ensures the players maximize their efficiency when navigating the board.
00:26:55.950
Finally, I designed an efficient recursive function that considers available gas and possible candidates at each step to ascertain the best next move, refining the process and eliminating inefficient routes.
00:28:37.560
Thanks to this comprehensive algorithm, I was able to finally get past level twelve!
00:29:10.490
As a final note, I learned that it’s effective to approach the game strategically, favoring certain movements and prioritizing pickups based on proximity.
00:30:07.640
Thank you all very much for attending. I really appreciate your time!
