Cheating with Ruby

by Cameron Dutro

The video "Cheating with Ruby" presented by Cameron Dutro at RubyConf 2018 delves into the use of Ruby for developing a game solver intended to assist in playing the computer game "Pet Detective". The speaker introduces the concept of cheating not in the traditional sense, but as a means of enhancing one’s understanding of programming and image analysis.

Key points discussed include:

- Introduction to the speaker's background and personal insights

- Overview of the game "Pet Detective" and its mechanics, which involve picking up and returning pets to their homes while managing gas units.

- The motivation behind creating a tool, Pet Detector, was to learn the most efficient way to play the game rather than simply obtaining answers.

- Explanation of how the Pet Detector uses Ruby and the RMagick library for manipulating images to analyze screenshots of the game.

- Description of the development process, including leveraging Dijkstra's search algorithm for calculating optimal routes within the game.

- Detailing the image analysis techniques employed, such as:

- Boundary detection through probing to identify the game board's dimensions.

- Quadrant analysis to effectively locate game elements such as pets and houses.

- Use of perceptual hashing for accurate identification of pets in varying scenarios within the game.

- Live demos showcasing the Pet Detector in action, leading to the discovery of the most efficient paths to complete game levels.

- Emphasis on strategic play and prioritization when tackling game challenges.

The presentation concludes with key takeaways on the importance of utilizing programming to enhance problem-solving abilities in gaming and encourages the audience to think of cheating as a pathway to learning rather than moral failure.

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!