Tetris, Puzzles, & Size Comparison

[00:00:00]
>> Tetris, many of you have probably played this game. I've certainly played it. I've made Tetris games for fun before. It's harder to implement than you might think. But I got to thinking, as most people do that play games, what if I wrote a bot to play this?

[00:00:16]
What if I wrote a Tetris bot that just sat there so I could go take a snack break and come back and the game would still be going or whatever. And that's a similar kind of question. How would you model the current state of a Tetris board the next piece that's coming up, and where best to put that piece?

[00:00:37]
There are many places to put that piece. Not all of them are gonna produce the same output. So how would you model solving a Tetris or even just playing a Tetris game in some sort of remotely optimal way? What would be the things that would matter? Here's some questions that would come to my mind.

[00:00:56]
What am I optimizing for? [LAUGH] Am I optimizing for longest gameplay like prolonging the inevitable? Am I optimizing for as many lines cleared or am I optimizing for clearing four lines so I get more of the bonus points? What are the things that my gameplay needs to optimize for I'd play it differently?

[00:01:13]
Now truth be told complex problems like this are rarely solved directly programmatically these days. Most of these are solved through machine learning. You effectively reverse engineer the perfect solution by playing a bunch of really bad games and selecting the best of the bad games and then keep doing that and keep doing that.

[00:01:33]
And then you end up with a style of play that is almost completely unlike what any human would do. But it ends up being the best gameplay. That's how a lot of those kinds of tools work now. But if you were to write a direct non-machine learning algorithm to this, not reverse engineering it.

[00:01:51]
You would translate some of the things that you think of as a player, some of the things that you optimize for, you would translate those into steps. And you'd say I think if I see one left side of it really, really tall, I'd try to put all of the pieces on the right hand side.

[00:02:06]
That might be one of your informal game playing rules. A machine learning algorithm might literally come up with the exact opposite rule and still do better than us. But the point is, if you were writing your own algorithm to represent your gameplay in Tetris, what are the steps you'd take?

[00:02:24]
What questions would you ask? What diagrams would you draw? All fundamental steps to being a better algorithmist. Very similar question during the pandemic, as many people did, my wife and I did a lot of puzzles. And we did some that were fairly straightforward, it took us a day or two.

[00:02:49]
We had one puzzle that a relative sent us that was really evil. First of all, it was a 1500 piece puzzle, so really tiny pieces and it was tons of color repetition. So it was gonna be a nightmare. And we poured it out, and I like looked at it and then about ten minutes in I was like, I refuse to do this puzzle.

[00:03:14]
[LAUGH] First of all, I don't need to waste weeks of my life on this puzzle. I was looking for something for a few hours, not something that I'm gonna worry about for weeks and weeks and weeks. But secondly, the pieces the way they fit, the way they cut that puzzle.

[00:03:30]
And I think this is probably just true, the more pieces that you have, the more likely it is that you have pieces that are almost a perfect fit but aren't. And I had a few of those, so I had no color clue. And then I was trying to pair the pieces by their shape, and it was ever so slightly, and I'm talking about half a millimeter not quite perfectly correct.

[00:03:53]
And then you're wondering, is it wrong? Or is this just the imperfection in the cutting of the cardboard piece? I was, no, I'm not gonna spend my life mad at this puzzle, so we just gave up on that one. But I got to thinking, what if I could just take a picture of this pile of my puzzle pieces and tell the computer, at least give me the edge pieces.

[00:04:15]
Give me a head start. [LAUGH] Not even solving the whole puzzle, how would you just solve the edges of a puzzle? How would you write that algorithm? There's ways to do it. There's image recognition and all kinds of stuff like that. But if you were gonna write code to do that, what steps would you take?

[00:04:38]
What are the base conditions that you would wanna look at? We know every rectangular puzzle has four corner pieces, so let's identify those first. That's what I do as a human, I identify the corner pieces and then the straight edge pieces. So that's probably the steps that you'd start writing code.

[00:04:55]
Use your image recognition to find all of those and start kind of shuffling them together. Then you'd probably sort by average color or something like that just to kind of get them approximately. And then you'd probably just start trying permutations of shapes fitting together until you found the right pieces to fit.

[00:05:16]
All right, I've put this up here as a representation. I know we already saw a map, but there's a classic computer science problem, which is given a map. And in the case of the map that we're gonna be talking about, it's just a two-dimensional array of zeros and ones.

[00:05:32]
That represent islands, okay? So here are some islands. Given this two dimensional grid of zeros and ones, not a complex map like we see here. How would you determine the size of the largest island, which is the size of the largest contiguous group of ones in that two-dimensional array?

[00:05:56]
How would you go through and find that the largest island is six versus four or whatever? This is a classic computer science problem and there's classic known solutions to it. Lots of different applications to this besides geographic maps by the way. You could think about this in image editing programs like filling of paint, find the largest, you could think about it in an image representation.

[00:06:30]
Like if you were doing a scaling or thumbnailing of a picture, and you might take a grid of some pixels and try to find the average colors within it. So you need to find the largest section of contiguous color within a grouping of pixels. Lots of different ways that this kind of algorithm can show up in the programming that we do besides geographic maps.

[00:06:51]
What are the steps that you might take to finding the largest island? For this particular problem, I actually have a link here to a just where I implemented it two different ways. I'm not claiming that this is good code. This is just my attempt. I solved it first with the recursive approach, the depth first, as we call it, recursive approach.

[00:07:23]
And then I went back and resolved it again, and that's what this code here is, is a snapshot of the breadth-first approach. And it's very small code, but I just want you to, if you can see there on line 9, you see some for loops. I'm not doing any recursion at all.

[00:07:39]
This is a couple of nested loops and a queue. I'm doing a breadth-first search through the tree or graph of information. You can treat this two-dimensional array of pixels as if it's kind of a graph, and I'm doing a breadth-first traversal through that. Once I find an island, basically spreading out until I found all the edges of the island and keeping track of how many units I found in that island.

[00:08:06]
And then I've got a set in there to make sure that I don't revisit that island from some other direction as I keep going looking for other islands. So that's my approach. Maybe it's a good one. Maybe it's a terrible approach. I don't know, there's probably much more efficient algorithms.

[00:08:25]
If this is your first foray into algorithmic programming, I'm gonna go out on a limb and suggest that some of you might feel a little bit intimidated by looking at code like that. And the reason I wanted to show you this code is that you will build up code like that in this workshop.

[00:08:42]
And it won't feel intimidating when you build it piece by piece. The intimidation comes when you look at the final solution and you say, I wouldn't even know where to start. Part of the purpose of this workshop is helping you learn where to start, okay? But you're gonna end up getting to more and more complex solutions piece by piece by piece.