Programming Throwdown - Puzzle Games with Mark Engelberg

Episode Date: August 17, 2017

Today we chat with Mark Engelberg about his background in software engineering and game design. Show notes: http://www.programmingthrowdown.com/2017/08/episode-69-puzzle-games-with-mark.html ★ Support this podcast on Patreon ★

programming throwdown episode 69 puzzle games take it away mark and patrick hi everyone uh we're here with Mark Engelberg, puzzle inventor. Nice. Mark, why don't you start off by telling us a little bit about yourself, your background, and what you're up to. Hi, it's great to be here. I studied computer science and cognitive science at Rice University. And somewhere in the middle of my sophomore year of college, I read an article about virtual reality. This was in the very early 1990s. So there weren't many people doing virtual

reality. There weren't many people talking about it. But I read an article and I thought, wow, this sounds awesome. I want to be a part of this i i'd kind of grown up playing adventure games uh text adventure games oh like zork like zork yeah colossal cave those kinds of things uh and then transition transitioned when text adventure games kind of uh became graphical adventure games like by sierra for example yes king's quest and space Quest and Leisure Suit Larry and all those games. Yeah, Police Quest. They were just wonderful games. And I loved those kinds of games, that melding of story and puzzles. And to me, virtual reality was the obvious next step for this kind of stuff. And of course, I also grew up watching star trek next generation with the holodeck and everything and i i was convinced that you know someday there's going to be this

studio where they're going to be making these virtual reality adventure games for people to play and you know i want to be the steven spielberg of virtual reality so i uh read all about this and i thought i got to get into this industry so i and of course i called my parents from college and i said oh i figured out what i want to do i want to do virtual reality they'd never heard of it and they're just okay sure well actually i grew up in kind of a small town and we had a virtual reality like uh i don't know what you would call it. It was kind of like an arcade, but it just had this one thing. And they charged $10 for about two minutes. And it was the frame rate was like three FPS. Yeah, yeah. And it was just, but it was a pterodactyl one. Was that the pterodactyl one? The only part I really remember was you're in an an elevator an elevator is kind of rising up and

you're having to kind of shoot i don't even remember what i if it's the one i'm thinking of and it might not be but if it's the one i'm thinking of there was a popular one uh at arcade places like dave and busters that had you kind of riding up and down platforms, shooting at pterodactyls flying. It might be that one, yeah. Yeah, so I took all the money I had saved up from a couple summers jobs and flew out to a virtual reality conference. I found that one that was happening in the Bay Area, and I spent all my money to get out there and made contacts with people in the industry. I mean, it was unusual, this college student kind of showing up at this virtual reality conference.

But people kind of remembered me and were impressed that I had taken the initiative to come to the conference. And so the following summer, I went through my business cards and kind of called that I'd collected and called different people. And it turned out that one of the guys I'd spoken with was now the director of the virtual reality lab at NASA.

And he offered me a summer job, which then turned into a full-time job as soon as I graduated. And I was one of the original pioneers in virtual reality. I had the luxury of working with these million-dollar computers. It literally took, back then, a half-a-million-dollar computer to power the graphics for each eye. Oh, wow. So a total of a million dollars of graphics power to power the whole virtual reality headset graphics.

So you can understand why there weren't that many places where you could work on virtual reality. And the lab that I was working in was involved with training, specifically training the astronauts and more importantly, training the ground crew. Because the astronauts have a lot training the ground crew because the astronauts have a lot of hands-on training they can do they can get into a pool underwater and manipulate objects you know to simulate a space mission when i was there the big space mission that was coming up was the hubble space telescope repair mission and there's a ton of ground crew, though, that needs to sit there following through the procedure and talking to the astronaut, walking them through it, having all these contingency plans if anything goes wrong. And it's really hard to train people on memorizing

a whole bunch of dry procedures. And so we thought, hey, we can take virtual reality and people can go into the virtual reality world and kind of be the astronauts and fix the Hubble Space Telescope repair mission themselves. And I'll bet that that will cause them to remember the procedures a lot better than if they just try to memorize it out of the book. And so that's what we were doing. We were kind of trying to be the first people to prove that virtual reality was actually useful for something. And it turned out it was. It really did help people have better recall.

So do you know how to fix the Hubble telescope? I still remember a lot of the details, surprisingly, years later. But yeah, it was pretty neat. And as part of that team, I was part of a lot of virtual reality firsts. I'm pretty sure I wrote the first real-time 3D physics engine, I think. I built a virtual reality physics lab where you could manipulate the magnitude and direction of gravity, for example, with a dial on the wall and then bounce the ball in the room and watch it fly in all kinds of crazy directions based on what you had set the gravity to.

Wow. So you actually did like the Verlet integration and applying the torque and collisions and all of that? Yes. You wrote it all in assembly or something? A lot of the stuff was done in C. Okay. But NASA had their own special language for building expert systems called CLPS. And they used that for a lot of detailed simulations where you have tons of rules you need to pattern

match on. And it was a language kind of optimized for that. And I did a lot of research on how that language was kind of a particularly useful paradigm for building simulations like in virtual reality. So that was something I've always been really interested in programming languages and how different languages cause you to think in different ways and cause certain problems to be easier or harder to solve. And so I was really excited to be working with this unusual programming language and looking at how it made certain kinds of simulation programming to be more accessible.

So that was a lot of what I did at NASA. We also did, I think we did the first over the internet virtual reality, like a teleconferencing internet with another NASA. So it was a fun time. But a couple years into that, I realized that virtual reality wasn't going to be changing much for a very long time. It was just going to gradually, gradually get cheaper. And as long as it was a million dollars to power some goggles, it was going to be a long way off before my dream actually happened, if it was ever going to happen.

So just before you go i should interject what do you think about the state of vr now like now you uh i haven't tried it but i think you can just if you have a samsung phone you can just attach it to this this head mounted display and strap it to your head and you have basically yeah i have done that with my phone, actually. And I've also, I go to virtual reality meetups here in the Seattle area. And I've had a chance, I don't personally own any of the new VR setups, but I have had a chance to try most of them. And it really is astonishing how far the graphics have come. There's no question. I mean, what you can do with an inexpensive computer now is miles better than what we were able to do with a million dollars of computing

power 20 years ago, 25, six years ago. So it really is astonishing how far things have come. But what's fascinating to me is that even back then when the graphics were crude, the sense of immersion was so compelling and so powerful. So it feels really familiar. I've logged so many hours in virtual worlds that for me it just feels familiar and natural when I get back in a virtual reality environment. It just feels exactly how I remember it, kind of. Just it looks better and the what was I gonna say um so you're talking about uh transitioning from VR to your next industry right so I realized it was going to take a while to kind of get to where things are right now where people have access to this stuff

at home and so i realized that if i was going to pursue this vision i had in college of doing entertainment vr the next thing i needed to do was get into the entertainment industry so my wife and i kind of looked around at different parts of the country this we were in houston because that's where john Space Center was. That's where I worked. But we figured it was time to settle down somewhere, kind of looked around where in the country we wanted to live, where the hot tech spots. And I was specifically interested in where is the next kind of gaming boom where can i work on computer games and i we decided on moving to the seattle area and coincidentally that was when sierra online the the company whose adventure games i had grown up playing king's quest space quest leisure suit larry they were founded by a husband wife team in Oakhurst, California, just near Yosemite.

And they had just opened. They had all relocated to Seattle and opened an office here on the east side of Seattle, uh, in Bellevue. And I was the first programmer Sierra online hired here in Bellevue. So I was living my dream working with these adventure game designers that I had grown up playing. One of the first big projects I worked on was a family

game called Torrance Passage written by Al Lowe, famous for the Leisure Suit Larry series. And he is as hilarious in real life as you might imagine if you've ever had a chance to play his games. And it was just a fun environment to work in. And I really enjoyed it. I eventually moved into game design and started writing my own ideas for Sierra. But then the bottom kind of fell out of the adventure game market. And Sierra, I think, got sold to some other company. And things were kind of fell out of the adventure game market and Sierra, I think got sold to some other company and things were kind of falling apart

at Sierra. So I figured that was a good time to get into computer games as you know, the underlying technology that powers computer games. Cause I don't know, do either of you have experience working in the game industry or not? I don't remember. No, I've experienced playing a lot of different games but not working in the industry.

So one thing your listeners might be interested to know is that in the game industry it's pretty common to have kind of a separation of skills between the people who kind of write the game engines and the people who write the logic of the games. And I especially, I have to say, I especially loved writing the logic of the games and not worrying about the engine stuff. That was kind of, to me, that was just the purity of what programming... Programming to me has always been about the fun of creating this virtual world that you can explore all through programming. You can create anything you can imagine.

And it's fun for me when the engine's already written and I can just sit and concentrate on building that world. That is really fun for me that's interesting I actually I feel personally just the opposite and the reason is and it depends obviously on the game but a lot of games are kind of um like like uh induct the law the goombas kind of move the same way and you have to sort of put them in a certain way where the player will execute a certain pattern

but I don't I mean maybe it's just because I've never really done it but I always felt to me like that part was inductive like you would just put them kind of anywhere and then you would see what the player does and then move them a little bit and it felt like the engine you know if you could make something like the engine was a little bit

more procedural or generative um but it might be because you know i think maybe after time maybe you get a handle on sort of the artistic part of it and you could kind of maybe predict that in advance yeah i mean there's there's certainly slightly different skills and appeal to different people so i mean i think that's great that there are people like you that really love working at that lower level um i did it for a while because i wanted that experience i worked worked at a couple different companies, but one was Rad Game Tools. And Rad Game Tools is famous for the Bink video compression. And that's used in just a ton of video games. And I was one of the first employees there

other than the founder of the company. And I helped do a lot of that early work in researching and designing the algorithms that powered the the bink video compression system cool yeah i'm sure i mean so people who are listening at home uh you know start any video game if you're a gamer start the game look at the splash screen right at the beginning you know kind of search you know there's a screen in the beginning which has all the copyright and, you know, maybe the logo, but a bunch of other things.

I guarantee you almost any game you'll see this, it's like a, it almost looks like, you can probably describe it better than I can, but it's like a tornado, but it's made out of different bands of color. That's the Bink video logo, and you'll see it almost anywhere.

Yeah, and I think what I loved the most about that job was it gave me a chance to really use my math background. I mean, I've always been really deep into math, and programming is kind of connected to math, but not necessarily on an everyday basis, depending on what you're doing. And certainly when I was doing high level logic for adventure games I'm not really using math on a daily basis and it was really interesting for me to kind of get back to my math roots in that job and

read up read through papers on compression theory and information theory and figure out how to implement these things. At the time, just to give people a sense for what computers were like at that time when we were developing Bink Video Compression, MP3s, right now MP3s are ubiquitous. But back then, if you wanted to play an MP3, it would pretty much consume your entire CPU of your computer to play back mp3 it would pretty much consume your entire cpu of your computer to play back that mp3 i remember uh yeah there's this uh the song um the men in black theme song for the very first

men in black that was the first mp3 i had and i double clicked it or i dragged it into i think winamp or something and my computer froze like i couldn't move the mouse. I couldn't do anything. I just had to listen to Men in Black. That was it. And then when the song finished, then I could move my mouse again. Yeah. I was a big believer in the MP3 format early on.

I created one of the first MP3 sharing websites specifically to try to connect indie artists with people who wanted to listen to indie music and it was i i kind of ran out of money to fund the website because it wasn't getting a lot of downloads because people did not have mp3 players built into their machine you had to download special players for that and it then consumed all your cpu and i was just a little bit ahead of the curve i think on that and it was a couple years after i gave up on that that mp3s really exploded as kind of the mainstream consumer way to to to consume music but before we leave the topic of the you know sort of

dichotomy between building game engines and designing games i will uh i think i've had it as a book of the show before but masters of doom which is sort of a a kind of review of the id software uh has a lot of intertwining with sierra online and the adventure games um and then the sort of counterbalance between uh carmack and romero uh as sort of game designer and engine programmer uh plays out in great detail through that book and so to you know jason was sort of mentioning some about it and you were too that you know i think if if people are interested in that that's actually a really good read it's it's pretty easy uh and as far as I know it's not fictional but uh it's a lively telling of the the id software the guys who made Wolfenstein 3d and doom uh and a lot of those games that a lot of us probably remember yeah it's funny even

though I'm into video games and I'm into 3D stuff, I never really got into the whole Doom phase for two reasons. One was because at the time I was sitting playing in 3D environments on million dollar computers. So I kind of turned up my nose at these games like Doom that were just played on a PC. And the other thing was I also, I think, a little bit resented games like Doom as kind of the killers of adventure games in a way. It seemed like people lost their taste for the puzzle immersion things in favor of shooter immersion experiences. That's probably not inaccurate.

Yeah, I mean, further down in the brainstem, right? Yeah, I think I had a little bit of a grudge about that for a while. So I think for both of those reasons i i never quite got into the doom thing but i certainly it's an incredibly popular field and i i would not be surprised if that book you described is a great resource for that kind of thing but the the point i was going to make about compression was that if decoding that compression is consuming all your CPU, how are you going to put something like that in a game, right?

In your game, you've got all kinds of stuff going on. And you want to have a soundtrack playing. And maybe on top of that, a layer of some voices or character voices. And maybe you even want a little video panel in the screen. And how do you do that if each of these compression things is going to take all your CPUs? That's where a company like Rad Game Tools comes in. They realized there was this specialized niche for compression technology that maybe it takes a longer time to compress it and maybe it doesn't

even compress it quite as well but the decoding is incredibly fast and by making that trade-off and optimizing for the speed and and low cpu usage of decoding they were able to address this entire niche that the whole video gaming industry needed, but that no one else was really addressing. And so that's what I would do. I would sit and, you know, I'd go read about how MP3s worked. And then I would sit down and write something that was, you know, maybe a little crappier than MP3, but not in terms of sound quality, but in terms of how much it would compress and would play back a million times faster than an MP3 would. Nice.

And then did the same thing for video. But audio compression is kind of a subset of video compression because you've got to compress the soundtrack also. So would it be fair to say your first programming language was the NASA? What was the NASA one called again? The expert system one? Clips. And interestingly, Sierra, where I worked for a couple of years, had their own programming language, too, to write all these high level adventure games.

In college, I had learned as my first programming language scheme, which is a dialect of Lisp. And then we immediately transitioned to using C++ and kind of used C++ for the rest of our college years. And so I got hired at a lot of these jobs for my C++ skills. But then ironically, everywhere I worked, they had these domain specific languages that worked a lot like Scheme and Lisp. And I was using and the reason for that is because Scheme was one of the first easily kind of embeddable interpreted languages. These days we have a lot of choices, like Lua is really popular as an embedded language for scripting video game logic, because it can be embedded as a high level layer to write your logic on top of a low level engine.

It does that kind of thing really well. But back then, if you wanted to create a language, a domain specific language to empower your programmers, you would typically write it as a dialect of Lisp because everybody understood how you parse Lisp, how you interpret a Lisp program. I mean, it's a simple enough exercise that a lot of college classes would have you do that as an exercise. And so there were so many tools back then. Like if you went out and got a CAD system or whatever to do 3D modeling, the built-in scripting language was some dialect of Lisp.

Most tools, if you wanted to be able to program it, they would include some kind of Lisp layer, some scheme-like layer for you as the programmer to do that scripting. It was just ironic that I was hired mainly for my C++ skills, and in a lot of these jobs I ended up basically doing scheme and Lisp programming programming or effectively in their own languages. That makes sense. And so that kind of explains the sort of, um, your, your sort of passion for functional languages. Like what would you say is your, your favorite language now? Well, I am really into the language Clojure and I've become a very active member of that community. I started using Closure as my primary programming language back when it turned 1.0. I kind of came at that through Python. I kind of went from C++. And then after Rad Game Tools, my son was born and I decided I wanted to be the one to stay home with my kids. And so I was at home.

I was the stay-at-home dad for many years. And I wanted to start doing some of my own programming projects. And I also wanted to perhaps pick up some contracting jobs. And I had to think about what programming language would give me the maximum productivity as an individual. And what I was finding, you know, C++ was what I had one of, you know, to some degree, the most training in. But C++ programs, like I could make really fast C++ programs, but it would take me a long time to build them. I was used to building them as part of big teams at Sierra when we well, I wasn't doing C++ programming there. But I was in general used to working on big teams with big budgets like at Sierra. It was very typical in that era for an adventure game to cost a million dollars to build.

You have a team of programmers and animators and artists and testers and even art techs whose main job is just to convert one file format to another and use some of the tools. But I was used to that kind of working process. And what I was finding is that when I would try to use C++ for my home projects, it was taking me too long to build things. So like I said, I've always been a programming language person, always out there trying new languages, trying new things. And one of the first ones to strike a chord with me was Python because I found it wasn't as fast as C, but for the things that it was fast enough for, I could build things way faster.

And that's because it has a really rich set of data structures built into it. And it's just so easy to use those data structures to kind of combine them in different ways to build whatever you need to build without having to do a lot of custom data structure work. You can just use the ones built into the language. But I found myself a little dissatisfied with Python at the same time.

And part of that dissatisfaction came from that I missed some of the immutability principles that come with functional programming. And I should probably explain that a little bit for people who aren't as understand that functional programming is about, well, is about functions and building your program in a way where functions are kind of the primary components that you're composing together. But what I think is the important thing about functional programming is that it mostly deals with what I would call pure functions, meaning something that for a given set of inputs always returns the same output. It's very predictable. Most of the things we write in other programming languages have most functions we write are mutating something or they're changing the value of something, some kind of object destructively

or they're updating the contents of some hash table, or, you know, everything is a very destructive mindset, typically. And when you're building your programs like that, your functions aren't pure functions. And there was something both intellectually unsatisfying about that to me. I mean, like, when you do two plus three, you're not destroying the number two and replacing it with five. So I kind of wanted that same, the same elegance that you associate with arithmetic operations, um, with, with other kinds of data structures. And we see that, uh, I think a lot of the world has caught on that this is a

useful concept and you can see evidence for that in the way string handling has changed over time. If you go back to C and C++, strings are mutable, right? It's really easy to change any character of a string in place, in memory. And it turns out that can really be a nightmare because it's very hard to keep track of what's responsible for changing what things and you can accidentally change a string you didn't intend to because you extract some substring out of a string

and it's actually sharing the same space in memory and then you change the character in this one thing and it ends up changing this other character. It's a problem. And so Java and Python and a lot of, you know, almost every modern language I can think of, strings by default are immutable. And it frees us up from, I mean, there are times where that's less efficient, and you need some way to drop down to some kind of immutable data structure when it's really necessary for performance. But we have saved ourselves tremendous headaches by making strings now immutable in most languages. And I think I have found that you can get those same benefits by making all your objects,

all your data structures by default immutable, all your collections. You know, I have a list. When I add something to the list, I shouldn collections. I have a list. When I add something to the list, I shouldn't necessarily destroy the original list. I just now have a new list that is one item added on. Now, a language that's built around this concept then allows you to write more pure functions because you're passing in inputs that are immutable and you're getting pure outputs. It makes your program way easier to analyze. And I just find that to be a much better way of thinking about it. And it came into play, like at the time, this was around when I was starting to do my own puzzle development.

And I'm sure we'll be talking a lot more about that. But one of the first puzzles that I analyzed was a puzzle game by ThinkFun that's kind of a famous puzzle game called Rush Hour. And Rush Hour is a physical puzzle toy where you have a grid and you set up cars, these physical cars on the grid. You have a puzzle card that's kind of showing you the right way to set the cars up on the grid. And then you slide these cars around and you're trying to get the special red car out the exit. So some of you may have played that as a physical puzzle toy. There are also a lot of different iPhone implementations and things like that. Yep.

Yeah, just the idea for people who haven't played this is you have this sort of gridlock of cars. And it just feels like, you know, you want to move this one car that's in your way, but you can't because it's blocked, you know, on either side by these two other cars. And so there's all these sort of dependencies. And you have to sort of unravel all of that by moving cars all the way on the other side of the board, and kind of, you know, using that as leverage to eventually move the cars you do want to move and get yourself out. Now to analyze that, I wanted to build a graph data structure where for a given puzzle, I want to think of every possible board state that you can get into of sliding these cars around as kind of a node in a graph data structure. And I want edges or arrows kind of connecting this board state to all the other legal board states I can get to from this one with one sliding action. So by building up that data structure, I now have a

complete snapshot of every single way I can possibly slide these cars around for a given puzzle. Well, in something like Python, so the first time I tackled this, this was in the era when I was using Python. One natural way to do a graph data structure is, like I said, one of the things I like about Python is you don't necessarily have to build a lot of custom data structures, you can just use the built-in ones. So a natural way to do that is the built-in data structure of, in Python, a dictionary,

which in other languages is often called a hash table and you are your dictionary the keys are the state that you're in and the value it would be the list of all the states you can get to that that would be one way to model this graph data structure using a hash table. Well, Python has a restriction for good reason that the keys in your dictionary object have to be immutable. Well, that the most part, the built-in data structures in Python are not immutable. There are only a few things in Python that are immutable, numbers, strings, and tuples. But what I ended up doing was using strings to represent my states,

my board states. So I had this kind of crazy flow to my program where I'd be representing a state as a string. I would unpack that string into some kind of mutable object so I could actually make moves on the board. And then when I got to the new states, I would convert them back to strings so that I could store all these things in the dict object. And I was thinking, this is kind of crazy. I mean, there's got to be a better way than this. And so, like I said, I was exploring lots of programming language. It's always kind of keeping tabs. And when I like I said, I was exploring lots of programming languages, always kind of keeping tabs. And when I saw Clojure, I just kind of fell in love with it right away because a lot of the older functional programming languages like Scheme, they really focus on one immutable data structure, usually the linked list. And there's only so far you can go with a linked list,

which is why I wasn't using Scheme for my own hobby project. But Clojure has a full suite of data structures, just like the ones built in a Python. You've got not only lists, but you've got things like arrays, you've got sets, you've got things like hash tables, and all of them are immutable. All of them can be used as keys and values and other hash tables are put in other collections, and you can nest these things however you want. And I found that rich tool set of immutable data structures, just this incredibly powerful toolkit for building up complicated representations of data and the functions that operate on them. So I really fell in love with that. And then once I started using Clojure, I found all these other benefits and then just never

turned back. So Clojure, because it runs on the JVM, is way faster than Python. So I just got an enormous performance boost switching from Python to Clojure. Clojure has a real strong emphasis on concurrency. And a lot of the puzzle analysis work I do is very parallelizable, but Python didn't give me very great tools to do that with. And so suddenly with Clojure, I was able to write a program to solve puzzles and generate puzzles. And pretty trivially, I could spin that out to multiple processors. It has just a wonderful set of tools for working with concurrency. Yeah, Python has the global interpreter lock. Yeah, exactly.

Yeah, which for people who don't know, it's basically, you know, let's say in Python, you can have two threads. And the first thread could be trying to access a database. And so while it's, you know, using some low level C++ library to hit the database, your other thread could be doing something else useful. But if both threads are just doing Python code, let's say both threads just have a for loop and they're adding numbers, Python won't let both of them execute at the same time. So it'll actually let you go to the first thread and have that one add a number,

and it'll go to the second thread, have that one add a number. And so no matter how many cores you have on your computer, it's only going to use one. But you can get around it no matter how many cores you have on your computer, it's only going to use one. But, you know, you can get around it using the multi-processing library in Python, but

that's, it's almost like using Unix sockets. You really have to send things over the socket between the processes. It's very, very low level. But Java, you know, and all the JVM languages, they just are way better at the the processes is very very low level but uh but java you know and all the jvm languages they just are way better at at uh at the concurrency kind of routines yeah i mean that

that is exactly the kind of issues i i was having with python and uh the python gives you a little bit of that kind of interactive window to interact with your code, but Clojure kind of takes that to the next level also. In the Clojure community, they call it REPL-oriented development, where REPL stands for redevelop print loop. And they have a really rich set of tools for interacting with your code. And that turns out to be great for me when I'm doing my puzzle work. And I think most people when they're writing programs, they're sort of writing one program with a main function that's going to run and they're okay with compiling it and then running it. But what I was doing was building a set of tools for myself to use. And so my programs were more like a workbench of,

you know, this can generate this kind of puzzle and this can solve this kind of use. And so my programs were more like a workbench of, you know, this can generate this kind of puzzle and this can solve this kind of puzzle. And I would write these things as independent functions and there was no real main function or something that I would run. I would just go into the REPL. I've built my whole workbench of tools and I would just type in commands to kind of like generate some puzzles and interact with them and try solving them and evaluating them and analyzing them and then make some tweaks to the puzzle and then solve it again and make sure it still has a unique solution. And I could do all this interactively from my Ruppel window, just fluidly interacting with all the code that I had written. So I just love that feeling of, you know, I'm building myself a workbench with all these great tools. And it's just a wonderful workflow.

And finally, a couple of years in a Clojure, they came out with Clojure Script, which is a version of Clojure that compiles to JavaScript. And for me, that was a huge benefit because I've always found the semantics of JavaScript just a little clunky and awkward. And for me, being able to apply these concepts that to me make Clojure so natural and so wonderful to web programming and to building graphical programs and websites and HTML games, you know, all these things I can do from ClojureScript. And it's easy to use the same logic that I've written and tested for building and solving my puzzles. In the JVM version of Clojure,

a lot of it can just be ported right over the ClojureScript version, and I can get the same behavior right there in the browser. Yeah, in episode 61, we had Eric Normand on the show who runs a website called Purely Functional where he teaches Clojure and ClojureScript. And he actually mentioned you can now even use ClojureScript

to write for mobile. So you could actually take your games and assuming you have to redo the UI, but you can actually use the same language and target mobile. Yeah, I think a lot of the people who are doing mobile are using tools that are built on top of Facebook's React native toolkit.

So it actually is a lot. I think a lot of the same UI code that you've written for the web, if you're using that toolkit, does translate over directly to the mobile platform too, because that's how React Native works. But yeah, I know Eric and he's a great Clojure trainer and he's probably done more than anyone else to put out a lot of high quality videos and training materials especially for people who are interested in using closure to build websites that's one that she's done a lot to provide great materials on cool so yeah uh yeah one question so so solving the puzzles, you know, that seems, let's say, intuitive, right? I mean, it could be difficult mp complete you know type search where you know

hopefully you use some heuristics or maybe there's some tricks like it decomposes but it always ends up involving some type of you know kind of search or planning um how does the generation work you know like like how do you go about generating it just because you could write a Sudoku solver? It doesn't necessarily mean that you could make a Sudoku level. And it definitely doesn't mean you could make a level targeted to a particular audience. Like if you want to make a Sudoku level for children or if you want to make a Sudoku level for, you know, experts. Like how do you go about parameterizing that and actually you know you've made three board games which we'll talk about and and that's the part that I find fascinating is how do you actually

create the levels and how do you sort of guarantee that that they're sort of playable and usable right yeah I mean that's that's the heart of what I do so yeah I'm happy to explain it although I'll tell you in advance that it's kind of like when a magician shows you how the trick is done, you go, oh, is that all there is? I'm sure that'll happen here. I'll explain to you how it is and it'll no longer seem mystifying. You go, really? Is that all there is to that? So I kind of view the process as three steps for most puzzle games. It kind of breaks down the three steps. The first step, like you said, is to write the solver. And I think that's the piece that most people can get their head around. Like you said, most problems boil down to some kind of search. I would recommend to your listeners out there who are just learning computer science,

learn how to write an A-star search. That's a famous algorithm for searching. And it is, I would say 99% of what I do boils down to some flavor of an A-star search. So that is, and surprisingly, I mean, a lot of people don't know how to write that and that's fine, but it's actually not that hard. So learn it and it's an incredibly powerful tool. There are also other tools that allow you, as you said, a lot of puzzles boil down to NP complete problems. And we actually have a lot of tools out there for solving NP-complete problems as long as they're not ridiculously hard and take forever to run, right? And fortunately, most puzzle games, for a human to be able to solve

them, are usually relatively small problem sizes relative to what a computer can solve. So even when these things are NP-complete, usually they're quite tractable on a computer. And you can apply some of these tools and for example there are constraint solving engines there are boolean satisfiability problem engines i actually gave a talk about this at the last closure conference people can find it online if they want either the talk i gave was called solving problems declaratively and i took that to the show yeah i took i took a sample classic puzzle and i walked through how you would solve that with a few different kind of declarative problem solving tools that let you just kind of model you don't even have to worry about how to express the

solving process these tools are so robust that in a lot of cases you can just model the problem write down a model of how the problem works and then pass it into this solver and it'll just solve it for you nice yeah i just just to sort of expound on that a bit a lot of people don't know this but basically so so a star is a type of what's called a fixed beam search and what that means is uh you know a fixed beam search is where um imagine you know you have some tree and and you know at the bottom of this tree are a bunch of leaves and each leaf has has some score but you have some intuition as to what the score is going to be as you're going down in the tree. So if you're thinking about, say, a game tree, you know if you're losing. If it's a monopoly and everyone around you has hotels and you don't,

you know you're in trouble. But you might pull it off and win the whole game, but you have some intuition. And so what beam search does, fixed beam search, is it will try to use its intuition to sort of go down the best path that it thinks about the moment and when it finds the answer then it goes back up the tree and it says well let me check some more answers near the one i found to see if there's an even better one and sort of depending on how you construct it, you can get an approximate

solution or you can get an exact solution. In other words, you can say, look, these things here, because I know some bounds on them, I don't have to explore that part of the tree anymore. You know, I know that all the leaves in this part of the tree are going to be between one and 10 and already have an 11 over there. So I know I could just drop this part of the tree are going to be between one and 10 and already have an 11 over there so i know i could just drop that part of the tree um and that's that's basically how like the entire tech industry works right if you're on amazon.com and and amazon suggests items to you they have three billion or maybe 30 billion things that they're selling, and they can show you 10, and they could do it every time you hit refresh.

The reason why they can do that is because they're doing a fixed beam search. So they basically, they have what's called an embedding or a latent space or a projection. They have a projection of you, and they have a projection of all their inventory and they try to line those up but they don't line them up one at a time they use this tree and so the same with like google the search engine you know facebook the ordering of the things in the feed twitter like the whole internet runs on effectively fixed beam search, which ASTAR is a member of. And so, yeah, ASTAR is something absolutely everybody should learn and code up. And there's an awesome Wikipedia page on ASTAR, which kind of has the code.

Literally, you could copy-paste it and also kind of graphically shows you what it's doing. And I might be able to make that a little more concrete even by talking about that in the context of that Rush Hour game that we were talking about. In Rush Hour, you've got the tangle of cars and you're trying to get that special red car out of the exit. And if you're going to search for a solution, you ideally want to search the moves that are going to be more likely to lead you to a solution, things that are get your red car closer to the exit. So the key there and the key part of any A-star search is to come up with a lower bound on how many moves it's going to take you from this state to the solution. So a simple lower bound for rush hour is, you know, how many spaces do I have to slide this red car over and how many things are in its way? Because each thing that in its way

is a minimum of one move to get that car out of the way. So you can look at a position and say, okay, this is going to take a minimum of seven moves to get the red car out. Maybe a lot more than that, but I know it's going to take at least seven. So I'm going to look for moves that move me towards something where the lower bound is six. Like I've basically moved the red car a little bit closer to the exit, or I've gotten one of those cars out of the way. Anything that helps reduce that lower bound is more likely to lead me to a solution. So that's kind of the heart, in my mind, of what A-star search is all about.

So you've written the solver. Yeah. So now you have to generate the levels. How do you go about doing that? Okay, well, the simplest way to do it is to randomly generate a ton of puzzles and then find the good ones.

This is where I said the revealing the trick. And you need to have a fast solver to do that, which is why having a good fast solver is always the first step. But at this point, like, you know, let's take Rush Hour again, for example, since we've already described how that game works.

You can kind of set up a random car configuration by kind of working backwards, like placing cars one at a time onto the board. So you put the red car down, and this is the thing I'm going to try to slide out the exit, and then I stick a car in front of it to block it. And then I stick a car in front of that car, you know, the car that's going to need to be slid out of the way. I put something to block that and I put a few more cars down. And now I have this random configuration of cars and I solve it. And maybe it's not solvable,

in which case I just throw it away but if it is solvable now I have a puzzle and so I can create a database of you know 20 30 000 puzzles and now the key becomes to analyze those and to figure out which ones are good and that that is actually the that that turns out most people think it's the generation that's the hard part, but it's actually the figuring out the good ones that is the hard part. Early on when I was doing this Rush Hour work, at the time, well, first, as a little bit of background context, ThinkFun, the company that makes Rush Hour, their tradition has always been to come out with puzzles where you have this beautiful handcrafted collection of 40 puzzle cards that come with the game when you buy

it. And they're just clever and well designed. And they're just, it's a beautiful sequence of 40 puzzles. Well, when the iPhone came out, you know, there were kind of knockoff versions that were, that would put in a bunch of random puzzles, a lot more than 40 puzzles, and maybe they're not so good and not, but you got a lot more puzzles. And so that becomes attractive to people. And so ThinkFun came to me and said, we want to learn how to make these rush hour puzzles on kind of a large scale so that we can also have our own app with hundreds of puzzles but we want our quality to be better than these competitors we want these puzzles to rival the handcrafted quality of the original set that's how we want to you know surpass these knockoffs and i thought that was a wonderful challenge. And that's why I got excited

about the project. And that was, you know, one of the first major projects I did, puzzle research projects I did for ThinkFun. You're sort of tapping into your cognitive psychology background again. Yeah. But when I studied cognitive science at Rice, I thought a lot about, a big part of what I did in the cognitive science program was look at how people solved puzzles because that's what had always fascinated me um and so what i realized like i said is the generation is the easy part now the hard part is how do i figure out which of these are good like a lot of these you know random generators, they would use some very naive measure to figure out how hard a puzzle is, like how long is the solution. I mean, that seems like

a reasonable measure, but it turns out to not be the best measure. So players would kind of play through the puzzle sequence, this randomly generated puzzle sequence of another product, and something that was labeled as easy would actually be a hard puzzle or something that was a hard puzzle labeled would actually turn out to be easy. And that's frustrating for the players. So how do we calibrate the difficult? How do we figure out exactly what the difficulty of these puzzles are? How do we make sure they're good quality puzzles? That's where the challenge lies. And what i found is that the key is to kind of throw away the solver you've built for this third phase even though it's it's fundamentally a solving problem

what i want to know now is how would a human solve this puzzle that's the question so you know that's going to be maybe a slower process to emulate than like these speedy off the shelf solvers that can just crank through a model of a problem and generate a solution fast. And you need that fast solver to do the random generation process and quickly screen for solvable and unsolvable puzzles. You want to write a more deeper model, a more complex program that models how you think humans would solve it. And you also want to do a lot of measurements on the puzzle space, the state space. Not just how many moves there are, but how many different states you can get into. What does the shape of that state space look like? How many dead ends are there? Like you kind of want to map out what the puzzle looks like.

And so, and then you want to synthesize all those measures and your model of maybe even one or more models of how humans might solve this. And you have all these measurements and you want to come up with some kind of way to combine those measurements into an overall rating. And that's kind of the same problem that like machine learning is used for right now. You've got all these different numerical attributes and you're trying to use it to predict some overall numerical attribute of a system.

Yeah, I was about to say it sounds a lot like uh like policy gradient so so policy gradient is this idea where um you know instead of saying whether something is good or bad you you um you basically have an expert so this case would be you the designer or some other human play the game and you'd have a system that learns what that person would do so in other words given a game that the the algorithm hasn't seen before it will try to make the same moves that the human being would have made whether those moves are good or not and this is actually how they bootstrap like the world champion go player and things like that they they boot because the state space is so large for Go, they bootstrap it with policy gradient.

So they basically say, look, there's all these expert human players. They all have these things in common. Maybe they're the best. Maybe they're not. Maybe there's a better way. But the state space is so big, we're just going to start by, you know, doing policy gradient and putting our algorithm in this niche where it's, you know, emulating all these expert players.

And then we'll start to do some planning after that. Yeah, I mean, that's exactly right. Now, what would be nice is if I had tons of people playing through these puzzles and rating them, and then I could literally pass it through a machine learning algorithm to figure out how to map all these measures I've created to the overall rating. But in practice, we don't do that. What it really comes down to is I use my own knowledge of puzzles and puzzle solving. I play through the puzzles, a lot of random sample puzzles, and kind of compare my own ratings of puzzles and puzzle solving. I play through the puzzles, a lot of random sample puzzles, and kind of compare my own ratings of the puzzles to what is being produced by these

different measures. And I kind of find a way to, I kind of keep tweaking the formula of how I'm going to combine these, kind of the way a machine learning program might do it, but I just kind of do it manually and with my own sampling process until I come up with a formula that hopefully does a pretty good job of measuring the interestingness and the difficulty of these puzzles. What does the formula do? So the formula takes into account like the graph, like the state space and that adjacency graph like like what's the formula based on so some of the measures might be the number of moves in a solution uh it might be how uh it depends on the game rush hour doesn't exactly have dead ends but you can imagine like you can get into state spaces that are maybe further away from a goal than where you started. And so understanding, like, the average distance of

a given state to the solution, like, so I can come up with, you know, 10 different measures that seem like they might work. But the heart of it, the key is, again, the most useful measure is going to be how long is it going to take a human player to solve it? And so here's an example of the kind of thing I might do. I've tried a lot of different heuristics with rush hour, for example, to kind of get a feeling for what feels like the, what, what is producing something that maps well to real level difficulty. And one of the things I found was that if you imagine a really naive player, one of the ways they might play is they might kind of make random moves for a while.

And if they get about three or four moves away from the solution, they can see that. And then they go make a beeline for the solution. And they might be a little more intelligent about it in terms of not just making purely random moves, but at least making moves that don't undo what they just did. Like that would be something that most people wouldn't do is just immediately undo the move they do for no reason. So you can program in maybe a preference for making moves that are novel, that take you to some kind of new state space. And so I would code up this kind of logic and then I would run it. And it has a certain amount of randomness to it.

But I would so I would run it multiple times and see like this, this virtual player. How many moves does it take this virtual player to solve this puzzle and running that and taking an average of a bunch of times it turns out to be a really really useful measure and then combining it with those other statistics i can get a really good handle on the difficulty level of a puzzle cool that's amazing i mean i just want something i always wondered and uh and uh yeah you totally you totally cracked uh but actually you know i uh i'm going to challenge you on that a little bit i think it actually was was really super insightful like i i was expecting when you prep when you prefaced it

i was expecting it to be uh you know we just count count distance from the goal and then i was actually in my head i was kind of thinking, well, you know, there might be some that are very deceptive and things like that. But yeah, I mean, this idea of sort of you model the human and then you try to refine that model by observing how it plays. Like, that's really cool.

And that's, so you put all of that to the test when you made these new three games that are coming out this month. That's right. Very cool. So, yeah, we should we should dive into them. So why don't you tell everyone about the three games you made? So so Patrick and I, super lucky we got early copies and we played them with with our families and uh we had a ton of fun with them um but yeah why don't you why don't you kind of explain to everyone uh you know what they're in for this month well a few years ago think fun approached me and because they know that i'm a programming guy and i i do puzzles and i approach puzzles with a programming mindset. And I also work as an educator in the programming field, teaching other homeschool students in the area. science activities, games and puzzles that would teach kids who play them computer science

principles just by playing these puzzle games and having fun. And they shared this vision with me and asked me to create products that accomplished that. And the first product I did for that was a game for ThinkFun called Codemaster. And Codemaster came out a couple years ago. And Codemaster started out as a Target exclusive for the first year. And it was a big success. And people really enjoyed it and really liked it. And Target wanted more and this was a good thing. So they came back to me and said can you develop a line of three new games that, you know, explore different kinds of computer science principles, each one doing something a little different so that the three kind of go together and help build a picture of, you know, what it's like to think as a computer scientist that kids can do this. As a teacher, I was really inspired by this project because as a teacher, and I think

all computer science teachers find this, there are some kids in the class that just immediately seem to get it when you teach programming. They're like, yes, it's intuitive. They just get it from the outset. And there are others that really struggle. And so the question teachers always ask each other when they get together at conferences and things like that is, why is it that, you know, some kids struggle and some kids just get it right off the bat? Is it something innate? Is it something that can be taught? You know, what's going on here?

And I, after having a lot of these discussions and doing a lot of research, it's become pretty clear to me that it is teachable. And you want to teach that as early as possible. Because what you want, like my hope with these puzzle games, and I'll go into the details of what each one does and what each principle, each one illustrates. But they don't literally teach programming in the sense like you're not going to play the puzzle games and sit down at the computer and start programming and see. That's not the goal. The goal is that you get kids playing these games and they're going to get a good mental model of how computers interpret and execute programs. They're going to get a good mental model of how logical statements are evaluated. You know, all these things, they're going to gain the mental frameworks that when they get

into a classroom later, these kids are going to be the ones that just get it. And that's my dream, is that like a generation of kids play these games. And then, you know, 10 years from now, teachers are saying, what's going on all these kids are showing up in my class and they're all finding programming really easy you know that that's my dream that's what i want and that makes sense i mean we both i don't know about pat i'll let patrick go second but but we we uh we both played a bunch of games growing up i used to i used to play this game called delta drawing which uh was just turtle turtle graphics if you've ever done this which is like uh how do you describe it like uh um like an

off-centric uh drawing tool so you have this little arrow and you say you know go forward three spaces then draw for three spaces and turn left and then draw and so you have to kind of understand that when the arrow turns left even though you didn't move it kind of like you have to sort of project yourself onto the arrow and write some simple code and it had a bunch of instructions of how to draw a square how to draw you know uh you know a hexagon and things like that and uh that i felt like things like that are really what sort of give people the right mindset when they're young. Yeah, definitely.

And so I started. So let me talk about the three games specifically. So the first game in the series is called On the Brink. And I would say that this is the one that's maybe the most accessible to the youngest kids. All the games are rated as ages eight and up, but this one is maybe skews a little bit easier. The basically you were talking about turtle graphics just now. And for many years, the basic computer game model and the model for getting kids working with programming was turtle graphics. The idea of a robot character, a turtle robot character that you can give it movements like move forward, turn left, turn right, and you're moving around a board or you're drawing some kind

of shape with it. And these are very, very common activities to do with kids. And what I wanted to do was accomplish two things with On the Brink. I wanted to take kids and show them this, you know, turtle graphics paradigm, but I wanted to give them some actual concrete puzzles they could solve. Because my experience is that kids get really motivated by solving puzzles in a way that they might not if you just give them an open-ended activity. You know, make this turtle move around any way you want is a little different than figure out how to solve this puzzle. And for certain kind of kids, they get really excited about this puzzle solving process. And it'll, you know, to get better at something in life,

you need to constantly challenge yourself to kind of work at the threshold of what you're comfortable. And most people don't like that feeling innately of kind of stretching themselves, but puzzles that naturally build in sequence kind of do that automatically for kids. Once they get hooked on the game and get hooked on the puzzle, each one is a little bit harder than the one before, and they're stretching themselves without realizing it. And by the end, they've accomplished all this so i wanted to to do something that was built out of turtle graphics instructions forward turn left turn right and you know make a puzzle out of it so that was that was the basic concept but the skill that i wanted to tackle with this was the idea of procedural abstraction um the idea of procedural abstraction.

The idea, like to me, one of the most beautiful things about computer science and the one thing, like even if someone doesn't go into computer science as a profession, the one thing I hope they walk away with with exposure to computer science is the idea that computer science is all about building components out of smaller components and then taking these new components we built and reusing those and building bigger things out of that.

Like that's what allows us to build the amazing programs we do as software engineers is everything's kind of built on top of another level. And that's what I wanted to give kids a taste of. So what I did is I set it up. The idea behind On the Brink is you've got a board that's a bunch of colored spaces and you've got a robot. And the way it works is it kind of looks at what color it's standing on. It could be red or blue or green. And if it's standing on red, it goes and executes the red procedure. And then wherever it, let's say it's standing on red, it executes the red procedure. it's standing and then wherever it let's say it's standing on red it executes the red procedure and then wherever it lands it looks at that color space and if it's now on blue it's going to go execute the blue procedure and so on and the puzzle is this the player is given these cards, these instruction cards, forward, turn left, turn right, and they're trying to assemble the procedures, and we keep it really simple so it's accessible

to younger kids and they can do this, you know, in a reasonable way. They're just worrying about two-step procedures. But what they're having to think about is that level of abstraction. You know, there's a bunch of red spaces on the board and whatever procedure they write, it has to work at all the red locations on the board. It's got to make sense everywhere. So you're figuring out how to make this reusable piece. And then as they get to later levels, we kick it up a notch.

And instead of giving them the instruction cards that are just forward, left, and right, we give them a new set of cards where each card is a procedure built out of forward, left and right. So, for example, there's I think there's an instruction there called like long turn right, which is a combination of forward, turn right and move forward again. So it kind of moves the robot in kind of a bigger arc than just turning in place. And so you have these bigger instructions and now they're building procedures out of procedures. So again, they're seeing firsthand through play that you can, you know, reuse components to build other components. So we give them things that feel familiar from their first, you know, built out of the forward left and right, they're building the procedures out

of those procedures now. And then by the, for most of the puzzles, we kind of tell them which cards they're going to need to use. But the last expert level, we don't even tell them what cards they need to use. So now it's getting a little more freeform. It's starting to feel a little bit more like the real programming process. But all along the way, they've gotten a taste of what it's like to abstract a problem out to bigger and bigger levels of abstraction, composing pieces into bigger pieces, and trying to find something that can be reusable across many different sites.

So I actually played through this one, my wife and I did. So I went through all the levels and mostly just sort of let my wife try, who's not a computer programmer. And the thing that I really liked is by the end, realizing that you may be on a certain color square, but that isn't sufficient to tell you what's going to happen. You actually have to know how you got there. And that's a pretty high level concept that matters a lot. That the state of your program when you get into a function matters, especially if you don't write in a functional programming language

can matter on a lot of other things right so that leaving aside that but i mean that's sort of a very abstract concept that if i sort of enter a red square from the left what's going to happen is different than if i enter a red square from the top um and which way i'm facing and so uh you know that is a very abstract concept that i thought was introduced very nicely that it was like, oh, OK, now I need to know I may be revisiting the same square multiple times. Or maybe I'm spoiling stuff, but I need to revisit the same square multiple times. Coming at it from different directions. Yeah. And that was sort of like, oh, uh-huh. Like, now I get it.

So I thought it was really nice. And also the fact that you can, and I don't know that it's considered cheating, but you can sort of work backwards. If you know where you need to get, you can sort of figure out what moves are valid to get you there. And then that sort of, you can work from both ends. And then that also often simplifies your problem. Yeah, and I don't consider that cheating at all.

I think that's an essential thing that I want kids to hopefully discover as they play this, is that, yeah, working backwards or maybe there's some, maybe the front and backwards are kind of unclear. The front end and the back end might be unclear, but there's something in the middle that is kind of clear for whatever reason. And so you focus on whatever part is tractable and then figure out how to tackle the other pieces from there once that's constrained. So yeah, that's a big part of what I hope players will learn and experience while playing through this. Yeah, so like you said, I can imagine, you know, someone playing this game isn't going to come away debugging a broken C program.

But, you know, if you're introducing them to a concept, they're going to recall, oh, my brain knows how to do this. I've seen this before. This function, I write this function, and then I can put it in different places and get it to do different things, even though it's the same function.

Yeah, it's about laying that foundation, setting up that mindset of how programmers and computer scientists approach things. It's kind of like martial arts. They teach you self-defense and these things, and you make it sort of innate. And if you're in some terrible situation, you're probably not going to exactly do the right form and do a figure eight in cartwheels or something but you have to have that instinct to sort of use the leverage

you need to use to escape that situation and it's the same kind of thing where you're not going to sit your eight year old down and say hey I want you to write this C program but what you can do is you can play this game with them

and give them the instincts so that when they invariably end up in coding 101 in 11th grade or whenever, that they have this huge advantage and it feels natural. Yeah, that is exactly what I'm aiming for. So thank you. I'm glad that came across. Cool. Yeah, I actually played the,

I didn't play this one that you just described yet, but I played the Rover Control game. Yeah, so you want me to talk a little bit? Yeah, absolutely. I'll talk a little more about Rover Control. So Rover Control is where I feel this is kind of the second game of the series. And here we're starting to get into what I think is the really core skill that separates the kids who kind of get it from those who don't. And this is the key skill that I want kids to learn.

And that is the ability to mentally step through code. For those of us who are in the programming profession, maybe that seems so obvious that we don't even think about that as a skill that one needs to acquire. But my understanding of the research from having read up on this a lot and looking at different investigations into this is that the key thing that separates the kids who get it from those who don't is the kids who get it have this kind of ability to role play the computer in their mind and and step through the the steps of their program mentally And if you can't do that, then, I mean, if you can't predict how your program is going to be interpreted, how can you possibly write a program? You have to understand how this thing is going to be evaluated. And where it gets especially tricky and what

Rover Control focuses on is things like while loops, if then else branches. When I would go to these teacher conferences, one thing I'd hear over and over again is, oh my God, while loops are so hard to teach. And when I was a new teacher, I would think, why are while loops hard to teach that I don't see what's so hard about that? Well, it turns out there are certain common conceptions that kids have when

they're learning programming when you see the with while loops the common misconception is that if the condition that governs the while loop is violated in them or becomes false in the middle of the body of the loop students think that it just kind of magically jumps out of a loop as soon as the condition becomes false this is this is like one of the number one misconceptions that students have about while loops and i when i heard that yeah i had kind of that same reaction whoa yeah now i see why kids aren't seeing it yeah like that is a reasonable thing to think would happen it's just not the way computers work but it it's totally reasonable to think that they might work that way so now i'm going to go write a language that does that right just to mess with people

yeah exactly so i'm. I won't do that. So Rover Control shows programs for this. The idea is you have this line-following robot on a Martian landscape. And your job is, there's this program that explains to the robot, follow the red line, then follow the green line. Check if you're at this particular location. If you are, do this one thing. Otherwise, do this other thing. This program is written out, but to make it accessible to kids, it's written in a graphical format. Kind of a visual flowchart kind of system that I came up with drawing from

a bunch of different inspirational sources. But it's a visual representation of the program. And the idea is you're trying to color the lines of the map to make this program actually work, to do what it's supposed to do, which is to get the robot from this location to this other location. And for some of the puzzles, there's the equivalent of like debug print line statements that print out where the robot's supposed to be at certain points in the program. And you got to make sure the program matches that as well. So the idea here that the skills that this is exercising is they're learning, like let's say you have a program. One of the puzzles might be based around a visual representation of a while loop.

And they're stepping through this in kind of a flowchart way using the graphical system. And they're seeing that you only reevaluate that while condition after you're done with the body of the loop and you kind of come back to the condition. And they're learning as they try drawing different maps and drawing the colored lines. They're using logic. Like if we just made a game that was an exercise of here's a program, figure out where the robot ends up. Like that's not interesting right kids aren't going to do something that feels like an exercise but the idea is you give them something interesting to do with that here's this program figure out how to color the map and even once you

can understand even if you're a good programmer and you can read this program flawlessly and understand how this works there's still a puzzle to be solved and you still have to figure out the right way to color the lines and there's a little bit of trickiness there because the the robot might overlap on its own path at a certain point in the program and you got to make sure it's colored the right way for you know there's different kinds of tricks that might happen um so that's the heart of it, though, is that they're practicing stepping through this code mentally, and they're learning the way computers actually evaluate these sorts of programs. And now when a teacher shows a student a while loop in their future programming

class, it's going to make perfect sense. They're going to be one of the ones that it's intuitively obvious that you only evaluate the condition when it comes back to the top because they've seen that model and they're used to stepping through code in that way and it's going to seem completely natural to them that that's how computers process programs because they had already practiced being the role of the computer mentally while they interpreted and executed these programs while playing Rover Control. Yeah, that totally makes sense. I've been developing for teachers to use. I've been developing a version of all the Rover Control puzzles that are written in actual code rather than the graphical language. And I actually have some of that up on a GitHub repository

that I can give you the link towards. But you can play through the same puzzles looking at, you know, the JavaScript version, for example, of each of these programs. And again, there's a puzzle to be solved. And if you're playing through it and you don't understand how to interpret the while loop, you flip the page over and now you got the graphical version. You can kind of go back and forth between the two. Oh, this is the graphical version. This is the written version.

I understand now how to interpret this. So it can really be used as a powerful educational device. But even if they're not going back and forth between the regular code and the graphical code, just by playing this graphical version, they are going to build that mental model of how to how computers interpret programs how they can mentally step through things on their own yeah the uh when i played it with my my son my son's four so so he's it's you know we didn't get to while loops but uh um you know we played the first level where um just to give people sort of like a mental model, sort of picture of this, basically you have these different colors. And as you sort of trace this path and these colors, there's some spots on the maze, we'll

call it, that are already colored in with a certain color before you even started. So, for example, you know, if your colors are sort of, let's say, red, blue, red, you know, there might be a path that gets you to the goal, but that path, you know, the first link in that path was blue. And since your first link, you know, from the program has to be red you can't take that path so so uh the first thing you do is you kind of fill in all the parts that are you know dictated in advance and then my son saw oh you know i can't take this path that goes straight to the goal because there's a blue one on there and i have to put a red one and so he put a red one somewhere else uh and then you know after a couple of tries

he kind of figured out that that oh you know if i put a red one then i have to follow the the blue one and so that means i have to go this way that way and then and then go to the goal so the first one was was was super accessible like you really like uh you almost can't really mess it up. And then it gives you kind of stepping stones to harder and harder, more complex problems. But the cool thing is, as Mark alluded to earlier, you have these stepping stones. And so there's sort of this I got it moment

that almost anyone can get. And that will give them the momentum to invest that time and energy to go to the next level and then the next level. Have either of you encountered the game I mentioned, Codemaster, the one I did a couple of years ago? No, I was looking at the picture. I don't actually think I've played it before.

So Codemaster and Rover Control are in a sense, companion puzzles. You can almost think of Rover Control as like the sequel to Codemaster, but they can be played in any order because they both use the same visual language to describe programs. And they're both kind of about the same thing of mentally stepping through code, understanding flow control constructs. The difference is that in Codemaster, the maps are already colored in and you've got programming tokens that you're shuffling around on the flow chart. In Rover Control, the instructions are already filled in and you're coloring in the map. So they're like inverse directions

of what you're trying to accomplish but using the same basic system. Cool, that makes sense. And so, I don't know, Patrick, did you play the third one? Oh, I didn't. Oh, go ahead. I thought of one more thing I wanted to mention about Rover Control, which is that because I was doing it

in kind of the other direction for this one, and you're looking at the programs and building the map, I was able to do some more complicated kinds of programs. And like in Codemaster, I had to kind of restrict myself to 12 basic program shapes. Whereas in Rover Control, almost every program is different. And I really took that opportunity to kind of kick it up a different. And I really took that opportunity to kind of kick it up a notch. And for example, when you get to the advanced puzzles, we already talked about if, then else, and while loop. But at the advanced level, I introduced something very similar to for loops. And when you get to the expert puzzles, there's actually two different

robots running around this map. And you have to draw the map in such a way that the same program will work for both robots starting in different locations on the map. So it gets pretty tricky once you get to the expert level. I will say this is the one I looked at the last puzzle. I was a bad person. I opened them up and immediately went to the hardest puzzle. And of all the three, this was the one when i flipped to the hardest puzzle i was like oh that's not gonna work uh the other two i will say i did i actually managed to just go straight

to the hardest puzzle and you know figure it out but you know i these aren't i don't think these are designed for adult programmers uh so that that's not all the kids in the schoolyard would be intimidated you'd be the one taking everyone's lunch money that's a critique. That's not a critique of the games at all. It's just a statement that I will say. Yeah, I believe this one probably has the most intricacies associated with it, from what I could tell. Yeah, I was just saying that when you go to the middle school where the kids are playing this game,

you will be sort of the alpha student. You can go back to your alma mater middle school where the kids are playing this game, you will be sort of the alpha student. You can go back to your alma mater middle school. So I'm a very awkward and just happen to be smart. I don't want to go back to middle school. Middle school was terrible. Middle school was terrible. Oh, no, no, no, no, no, no, no, no, no. No side tricks. That's true. Yeah, that would probably take a whole hour to explain.

But middle school just seems to be terrible forever. Actually, so, okay, quick side track. They actually say the, you know, like when you have toddlers, like the terrible twos, that the, you know, your kid can kind of rage at their tantrums. That's because they're releasing a certain chemical in their brain. And that chemical is just flooding their brain. And that's what's're releasing a certain chemical in their brain, and that chemical is just flooding their brain, and that's what's causing all this rage. Well, you actually released the same chemical in middle school.

I mean, I'm not just making that up. That's true. And probably when you're debugging programs. Yeah, that's true. I don't think I ever gave it up, apparently. So, yeah, unfortunately, I didn't get to the third game uh but but yeah please explain it because i'm looking forward to it okay so the third game uh came about another another hot button issue for computer science teachers is that the students it's very hard to communicate to them a deep understanding of logical expressions logical connectives like and and or and not and then when you get to more complicated things like x or you know that it gets even more

complicated but um like i was and part of that is simply because most curricula for computer science just don't allow a whole lot of time in the curriculum sequence for that. So what happens is teachers get to the part where they're teaching logic. And you need to know it because it's going to show up in all your if statements as the condition. And you're going to need to know how to do this stuff. And they just kind of say, okay, here's and, here's or, here's not. And they kind of expect students to use their intuition, maybe from the English language, you know, just their experience with it in English to guide how these things are evaluated in programming.

And they just kind of move on from there the problem with that is that like or is a classic example or is not quite the same in math and programming as it is in everyday conversation most people do not think of or as the inclusive or where if both things are true like if i said to somebody when i'm teaching logic to kids i'll give the example something like um tonight i am going to dinner or i am going to the movies now if you later find out that i ate dinner and i went to the movies was i lying and a lot of them yeah you were lying you said you're going to either go to the dinner or go to the movies and you did both. So you're lying. And I'm like, no, in math and computer science, if you do both things of an or, it's still good.

What? You know, I mean, this is, and this is fundamental, not just a computer science, but this is how all math works, math proofs, scientific language. I mean, anytime you use or in a precise context, the inclusive or is assumed unless otherwise specified. So we really lead kids astray. And then as soon as you throw a not in there, I mean, when kids try to process double negatives, it takes them a while just to get that. But as soon as you start to say something like, well, just as a classic example, in programming, you might want to say, you know, X is between 1 and 5. So how might I do that? I might go, you know, 1 is less than or equal to X, and X is less than or equal to 5. Well, how do I not that? Well, I might, you know, the obvious way is i can put a knot around

that whole and expression but a lot of kids will get it wrong though they'll do like not x is greater than equal to one and not x is less five which is exactly what you don't want to do if you if you're not in the individual parts you need to change the and to an or. That's the Morgan's law. These things do not come naturally to kids just from thinking about it from English language. You kind of need to learn how to evaluate it, how to reason about it, and that kind of thing just takes practice. So I started from the premise of,

I want to create a game that is going, you know, logic is fundamental to programming. We don't usually think about that. When we think about programming games, we usually think about the other kinds of games we've already talked about, sequencing games, where you're programming some robot to do something. But logic is pretty fundamental. I want to come up with a game, a logic puzzle, you know, something kind of like a Sudoku, a logic puzzle, but where the clues are expressed in terms of and and or and not, and maybe getting into the more complicated things like XOR and if and only if and and and nor.

I want to make a puzzle that does that, where you have a clue system based on these logical connectives so that kids can gradually, as they work their way through the mastery, over how to reason about all you connectives that's what I set out to do and and the the inspiration I got was around the time I was reading Knuth's late book I don't know if your listeners know a lot about Donald Knuth but he is a amazing computer scientist and a lot about donald knuth but he is uh a amazing computer scientist who's invented a lot of the pioneered a lot of the fundamental algorithms that programmers use every day and he wrote this tremendous book called the art of computer programming it's his life's work he's

been i think he's in his late 80s now and he's been working on this almost his whole life uh he was so passionate about writing the art of computer programming that I think he's in his late 80s now, and he's been working on this almost his whole life. He was so passionate about writing the art of computer programming that when the first copy came back from the typesetter and it didn't look as good as he wanted, he took 10 years off to develop LaTeX so that he could have it look good. But it's this amazing compendium of algorithms and ways of thinking about algorithms. And he's still developing it to this day. He's still adding new chapters to this book that are released on Amazon every year or two. Yeah, and he has prizes, too. If you can find errors in his book, he actually has prizes on his website. I missed that by a few days on the last one.

I worked his latest chapter as soon as it came out, and I was reading through it, and a few pages into it, I saw some typo, and I was like, oh my goodness, I've got to write this. Because everybody, he sends the checks, I think they're $2.56 if I remember correctly, like a hexadecimal dollar calls it, to anyone who finds the first person to find each bug. And I get the impression most people don't even cash the check.

They just frame it because it's such an honor to get it. And I saw this typo and I wrote in and I got back an email saying someone reported it three days before you but thank you but yeah I really his books I've gone back and re-read it maybe once every ten years or something and every time I because it's so dense like you read it and you understand some small fraction of what you're reading and even what you understand is already blowing your mind

and each time i read through it i get something different out of it because i'm at a new stage as a programmer i know more and i i have a different perspective on things so i go back every 10 years and kind of reread it and learn a whole new set of things that I didn't even notice before because I wasn't at that level before. So it's a really phenomenal series of books that you can learn a lot from. But I got the latest, his latest chapter

is about the Boolean satisfiability problem. The Boolean satisfiability problem. The Boolean satisfiability problem is a famous NP-complete problem. And the basic idea is you have a logical formula built out of a bunch of variables, and it's either the variable by itself or the variable with a not on it. And you have some logical expression out of these variables

and nots connected with and and or. There's kind of a normal, what they call a conjunctive normal form, which is a standard way to express. This is like two sat versus three sat. Exactly. Yeah, yeah. Yep. So there's different, but the general problem is still NP-complete.

It's that there are some more precise subsets that are easier to prove that they're NP-complete. But the basic problem is you got this logical formula and you have to find which combination of trues and falses for assignments variables make this overall formula come out to be true and i was reading this and and this is in a recent talk he kind of said that he thinks that satisfiability problem is something that every programmer should have in their toolbox and one of the reasons behind that is because there's a lot of state-of-the-art research that has gone into writing these SAT solvers. And I was talking before about declarative modeling of problems. Like you've got some really hard problem you want to solve. Instead of writing the logic to solve it, it's great if you can figure out a way to express that clarity and just pass it to a fast solver. So it turns out because these are NP, you know, it's an NP complete problem.

What that means is that there's all these other NP complete problems, every NP complete problem, we often know the mapping of how that can be mapped to the satisfiability problem, because that's how you prove something is NP complete. You show it can be reduced in polynomial time to some other NP complete problem. So we have these mappings where we know, like, if I have this crazy hard problem, I could turn it into this satisfiability problem. It's kind of like, I mean, a good analogy here is, maybe it's not that good, I should move it up. This might be terrible, actually, but kind of like a socket wrench, right?

Like if you go to Home Depot and you buy, you know, a socket wrench, so you buy, you know, the top of the wrench, you buy all these bits, you might have like 30 bits, right? And you put that in your toolbox. And you have sort of some level of confidence that when you need to take apart like your kid's tricycle or something, that's either going to be, you know, an Allen wrench, sorry, you're either going to need like an Allen screwdriver or a phillips head or a flathead but that there's that there's all these kind of standard forms and there might be different sizes but you bought this one tool that can solve you know 99 percent of it right and so you just buy that tool from home depot put in your toolbox and you just take it

out whatever you need to and and so mpcomplete problems are kind of like that class where they're all sort of variants. It's very easy to go from one to the other because it's some kind of size change or some minor tweak. And so something that's really, really good at solving one of them can kind of solve all of them. Right. And the Boolean satisfiability problem is like your 99 tool like you said it's it's intimately connected to these empty complete problems so i was reading about this he has this whole new chapter of his book devoted to uh understanding how state-of-the-art sat solvers are actually built and walking you through the algorithms that drive these solvers and it's really fascinating stuff but as i like simulated and healing genetic algorithm type stuff or or what um

i he touches on there are some random processes that will get you there uh for certain classes of problems but that's not the the this that's not the state of the art as far as I understand. Oh, cool. I'll have to read it. I'll have to check it out. At least not for these particular satisfiability problems. Yeah, it's a really wonderful... And of course, Knuth is famous for literate programming, which is a form of programming where every bit of code is wrapped in a lot of very clear explanatory text explaining how this code works. And Knuth is the inventor of that style and the master of that style.

And this new chapter basically reads like a literate programming version of a state of the art SAT solver so that you're reading through this program and understanding how it works. It's a really fascinating read. But as I was reading this, I thought, you know, I can make a game out of this. I think I see how I can make a logic puzzle built on top of the satisfiability problem. And if I do that, that will also serve the other purpose I talked about of a clue system that can be expressed in terms of and and or and not and get kids really comfortable with reasoning about these logical expressions. So the basic concept of the game is you're looking at a map of a robot brain and it's a bunch of nodes

connected by these colored wires and the idea is you have these power cells and when you put the power cell on a node it activates all the colored wires that are touching it on the other on the the other page of the puzzle there's so you're looking at the map and then you're looking at the clue system. There's a clue system, which is a big logical formula about which wires need to be active or inactive. And from those clues, you need to figure out where to place the power cells. So the key here in the, it's almost exactly like the Boolean satisfiability problem in the sense that in the Boolean satisfiability problem, you have a formula, you're trying to figure out which variables are true and false. If this were exactly like the satisfiability problem, the equivalent would be, I have this

formula about which wires are on or off, and you need to figure out which wires are on or off. But I added one level of indirection, and that was like the secret sauce to make this a fun game, as opposed to feeling like just an exercise. And the secret sauce is you can't directly control whether the wires are on or off. You can only control them by where you place the power cells. So you're solving the logical formula, but you're also the puzzly aspect because you're trying to figure out where to place the power cells. And the topography of how the wires are connected to one another comes into play as well, not just the... It would be very dry if all you were doing is cranking through the logical implications of the formula.

But the puzzles are designed in such a way that you have to go back and forth between kind of analyzing the formula and then going over and placing what you can on the map and then figuring out, oh, you know, I've already placed a power cell here and I've only got one left. And that means this other wire is active and this one can't be active. And like using the partial knowledge you have to go back to the formulas and do some more logical deductions over there. So you're kind of going back and forth between making these logical deductions, doing some placements on the map. And that's what makes it a fun puzzle. Yeah. So depending on where you place it, you may turn one, two or three. I think three might be the most. But one, two or three I think three might be the most but one two or three different

colors on so that's what you're talking about is that you have to be strategic and where you place you're not just simply saying red is on you're saying I'm placing at this node and this mode node makes both red and orange on exactly yeah and so up circuit for people who like you know logic puzzles this is this is the most logic-y of the three right it's not about sequencing it's not quite like the same as the others it's about logical formulas i i don't know about you but i grew up on raymond smullion puzzles are you familiar with raymond smullion no i haven't heard that oh he was he he died recently but he was this famous logician who wrote all these books

um with these puzzles about knights and knaves and knights always tell the truth and knaves always lie and there would be some combination of statements of a you know the person a says make some statement about b and b make some statement about a and they'd be, you know, some kind of logical statement like A is a knight or B is a knave. And you're told some kind of meta knowledge, like exactly one of them is a knight and the other two are knaves or something. And you have to kind of figure out what each person is. And like one of his first books i think was called what is the name of this book uh two of my favorite books of his are the lady or the tiger and alice in puzzle land which is a whole series of puzzles based on alice in wonderland material um but i grew up on these

puzzles and just loved solving these logic puzzles and And I'm trying to capture that kind of in a visual system here. And that really pushes the ability to read the different kinds of connectives. Yeah, I think this one was very obvious to me that when you play it, it's very clear how once someone figures out how this works,

how they would debug a broken if statement. That, you know, if you have this if statement with some complex ands and ors, like this would very much set them up for being able to understand that you have to sort of look at what has to be true, what can't be true, and sort of track down which variables are in what state, you know, sort of how to evaluate it so that pretty much covers the whole series of three games they just arrived in target today um these are going to be exclusive to target for the rest of the year i went over to my local target

today and showed up because i wanted to see them for myself they it says on the website they're in stock but when i got there the lady who was oh, we're actually rebuilding the toy game section. And a lot of them are still on pallets in the back. But I'll be unpacking it in a couple of days. Did you say this is my game? Well, my daughter was with me and she mentioned it. And the lady got kind of excited about that, that I was there to sort of see my games on the shelf. And she felt really bad that they were in the pallets in the back oh no i'll have to go

back in a couple days to see it for myself but it's it's in stock at a lot of targets already it should like like my local target i'm expecting it to trickle to the rest as they set it up this week there are different displays um all three of these games are available. They're all priced at a retail price of $14.99, which is relatively inexpensive for this kind of thing. And some of that comes from the fact that these are unplugged games, too. A lot of the competing products out there, I mean, they're cool. They might have some kind of physical robot that zooms around or something but oh yeah but those those will cost two or three hundred dollars

right because you got yeah and i think it's good to have it this way too because i think it's too easy to be distracted with the other ones and just you know sort of play with it and i think this yeah you this is forces you to do the mental processing of playing the computer which is what i was saying I think is the key skill. So yeah, I think you get a lot out of this. Kids already spend so much time on iPad and TV and things like that. Yeah, I've totally turned into my dad. I mean, when my dad would tell me to get off the computer,

I remember, and we all probably remember this saying, oh, when I become a parent, I'm going to let my kids, you know, play on the computer all day long. And then sure enough, like the cycle just repeats, right? Like you can't, you know, you grow older and you realize like that's just not a very, you know, healthy environment. And so it's really good to have something that's tangible, physical, that isn't glowing black at you that you can play. Yeah, as a parent, I definitely got to the point where I started looking for unplugged things for my kids, things that wouldn't use up precious screen time. And my experience is I found that kids often have a very different kind of attention span on the computer versus physical things. Like on the computer, we are so used to clicking so fast as we navigate

through the web. And, you know, anything that comes on the screen, we want to be able to click in two seconds or we get bored. And I was finding that if you show a puzzle or something like that on a computer screen, kids don't want to take the time to solve that. They just want to click on something within a couple seconds. But you set up a puzzle in physical fashion and put it in front of them and they get engrossed in it and they'll spend hours sitting there and kind of working through puzzles. And they're much more willing to work and try different combinations to solve a really hard puzzle that's my personal experience working with different kids yeah well we're running pretty long this is a long show no no it's okay um so i yeah i think it's very cool you know talking to someone who's designed games you

know that's always been interesting to me we all grew up playing games and solving puzzles think it's very cool, you know, talking to someone who's designed games, you know, that's always been interesting to me. We all grew up playing games and solving puzzles. So it's great to hear a lot of the insight you've given us about sort of how games get made, how puzzles get solved and rated. That's, you know, all enormously fascinating to me. So I very much appreciated your time. Well, it's been a pleasure. Is there you have any final questions for me?

Where is it? Oh, go for it. Yeah, I was gonna say, yeah, give us a plug for, you know, well it's been a pleasure do you have any final questions for me? where is oh go for it give us a plug for ThinkFun's website has the games the code series on the brink robot repair and rover control where else can people

go to sort of find out about what you're doing what you're up to or learn more about you? Yeah, and also where can people go if they're not in the US or Canada or wherever there's a target? Where else can people go to pick up the games? Well, that is the challenge

with it being a Target exclusive for the first year. It will eventually get to other countries, but I don't know how accessible that is. Oh, got it. Okay. I'm not sure the answer to that. Sure.

But I do know like Codemaster, after its year at Target, it's now made its way to a lot of other countries. So that does happen over time. Oh, cool. So they can start with that. They might not be able to get these new three games just yet. Okay. I actually, I was at a board game convention recently and a board game designer from Germany, because a lot of the great board games are designed in Germany, was over here and I overheard him at a table next to me saying, you know, oh, I got

to run out to Target because I'm in the US and I can go get Codemaster for my kids. Oh, that's awesome. I was really happy about that. So as far as finding other things that I announce, I'm on Twitter as Mark underscore Engelberg. That's M-A-R-K underscore E-N-G-E-L-B-E-R-G. And I don't tweet a whole lot, but I try to tweet, you know, like if I've got a new game coming out or if I gave a talk at a Closure conference and I'll post the video there or something. So it's a good way of if people were excited by what I talked about and want to kind of keep tabs on what I'm doing, that would be a great way to follow me. Very good. Very cool.

Thank you so much for coming on the show. This is I think people are absolutely going to love this or have loved this. It touches on so many things that almost everyone field. People coming into the field now have a new sort of platform to learn and teach their kids. And so thank you for kind of, you know, sharing all of that with us. It was a pleasure. Thank you for having me. All right. Thanks, Mark. The intro music is Axo by Binar Pilot. Programming Throwdown is distributed under a Creative Commons Attribution Sharealike 2.0 license. You're free to share, copy, distribute, transmit the work, to remix, adapt the work,

but you must provide attribution to Patrick and I and sharealike in kind.