Thursday, December 31, 2015

Monte-Carlo Battleship!

I’m going to do something a little different in this post, which is geared more towards grown-ups who like playing around with programming and recreational mathematics. Even so, there might be some good stuff here for kids who are comfortable with some programming basics. Instead of a problem set, I thought I’d tell you about a random bit of modeling I ended up doing over the holiday that you might have fun playing with too. One of the things I think is great about learning how to write code is that it gives you the tools to chase down lots of fun questions and see how different kinds of system work by building them and then changing things around. In this post, I’m going to tell you about my efforts this past week or so to learn some things about a system I bet you’re familiar with.

My daughter got a Battleship set for Christmas just a few days ago after learning how to play the game at after-school daycare. Before we got this for her for Christmas, I made up a bunch of paper-and-pencil versions we could use to play at home (You can download a PDF of these here, if you like). Like any game, the finer points of strategy took some time to impart, and she’s still working out how to plan her missile shots to efficiently search the grid. The game also can take a fair bit of time (and a lot of disappointing missed shots) to complete, so like we’ve done with other games, I’ve occasionally introduced some changes to speed things up just a bit. These have included: (1) A smaller board (8x8 rather than 10x10), (2) 2 shots per turn rather than 1, (3) Different ship sizes. One of the nice things about the paper-and-pencil version is that you can invent whatever sizes and shapes of ships you want, which makes these changes very easy to implement.

Playing (and talking through) the game with her a bunch of times, the different formats we invented got me thinking about how this simple system works and what you, the player, might want to know about it. Board games as simple as this one are kind of fun to poke at this way because you can usually see your way to some aspects of the game’s structure by either writing some expressions that describe how the game works formally, or when all else fails, writing some code that helps you understand some aspect of the game.

For Battleship, I decided to tackle a straightforward question Blaise and I face every time we play: Where should you take your first shot? How does that depend on the size of the board and the ships that are available to place on the grid?

The answer certainly will depend on whatever biases human opponents have for placing ships on the grid. There are probably some general factors that come into play, like the fact that most people have a left visual-field bias that affects a lot of different tasks. There are also probably lots of individual differences as well: Do you really like to put ships on the edges? Do you like to bunch everything up in one place? Do you hate/love using the corners? What these biases are could be it’s own fun problem to consider, but for now we’re going to act like they don’t exist. This way, we can start to develop a kind of simulation called a Monte-Carlo model that will let us understand some things about Battleship and how to plan your first shot.

What is a Monte Carlo model? Basically, it’s a way of simulating a probabilistic system by making lots of random draws and keeping track of what happens each time. For example, suppose you have 10 coins you want to flip and you want to know how often you’ll get exactly 3 heads – that’s something you can work out analytically, but if you didn’t know how (or just didn’t want to), you could also just flip the 10 coins lots of times and see how often you got 3 heads. That latter approach is more or less what we’re doing in a Monte Carlo simulation: Given a random process, we “draw” an outcome and record what features of the outcome we care about so we can estimate properties of the system that we’re interested in. While this strategy has been around for a long time, the advent of computers capable of doing the random draws and multiple iterations for us meant that MC simulations became much more widely used in the mid 20th century. To my knowledge, a mathematician named Stanislaw Ulam (who is a fascinating person to read about) is responsible for developing modern MC approaches, which he and others including John Von Neumann and Enrico Fermi used to examine issues in nuclear physics arising from the Manhattan Project. This was a case where they really didn’t know how to write down deterministic equations to explain the systems they cared about, so simulating them with random draws was about the only way forward.

OK, so how do we use these methods to talk about Battleship? First, let’s define what we want to know: Where should we take our first shot? I’m going to rephrase this as, “How likely is it that any given square will be occupied by a ship?” After all, if a square isn’t likely to be occupied, we wouldn’t want to waste time shooting at it. Second, let’s define how we think this system works in terms of a random process. Here are the rules I’ll use for our Battleship simulations:

1) There are five ships. One ships takes up 2 squares, two ships take up 3 squares, one ship takes up 4 squares, and one ship takes up 5 squares.
2) No square may be occupied by more than one ship (no overlap).
3) The ships are placed on a 10x10 board.
4) The ships are placed randomly by the opponent. For each ship, each legal ship position is equally likely to be selected.

Note: It’s really rule #2 that makes things a little tricky to compute deterministically, since the placing of one ship constrains the possible positions of the others.

So now what? The next step is to write code that allows us to randomly arrange the 5 ships for a single game and record where they were positioned. Here’s a picture showing you what a single game looks like using code that implements the four rules above.

Now that we can do this, we run that code thousands of times, keeping track of the ship positions for each simulation. When we’re done, we’ll count up how often each square was occupied across all of our thousands of random games. The result is a map of the game grid, with a number in each square telling us how often that square was occupied across the whole set of simulations. When I tried it out with 10,000 iterations, I got the following map:

What do we see? Well, it’s definitely a good idea to shoot for the center, but we can even say roughly how good an idea it is relative to other spots. For example, the center squares are occupied about 3 times more often than the corner squares! That’s not a bad thing to know about the game, and it all comes from the constraints placed on ship positions imposed by our rules.

My guess is that at this point this basically matches your intuitions about the game, so you may not be very impressed. Sure, we got some quantitative data about the relative merits of the center vs. the other locations, but how big a deal is that? Arguably, not much of a big deal, but the real fun starts by messing with those rules and seeing how things change. See, I wrote all my code so I can manipulate the size of the board, and the size and number of ships and do all this over again. Let’s see how the maps change when we use a smaller board (9 squares and then 8 squares).

The same overall structure, but the absolute numbers change a good bit (note that the ~3:1 ratio for center vs. corner is roughly preserved, though). What about changing the ships? Let’s see a version where we only have ships that are 4 squares long:

Now let’s compare that to what happens if our fleet is only made up of ships that are 6 squares long:

Check out that cross shape! The center isn't really favored any more than the arms of the plus sign - see if you can figure out why this changed the way it did intuitively.

There’s tons of other stuff you can do with this little game by simulating different scenarios, and these are nice ways to see how some candidate rule changes might make the game more or less fun. What if you introduce squares that can never be occupied? How about ships with different shapes? What if you make your game toroidal by letting ships “wrap around” the edges of the grid? Suppose we let the “no overlap” rule go? There are lots of possibilities to explore, and an MC simulation lets you quickly get some insight into how they work.

That’s the end of my grown-up post, and I hope you found it at least somewhat fun. I really think learning how to play with mathematical objects opens the door to lots of great ways to explore ordinary stuff, and hopefully this was a good example of why I think that’s fun to do. Please feel free to play with the code yourself, and I’ll try to develop a few more posts about similar topics. Thanks for reading, and happy modeling!

Tuesday, December 29, 2015

Free books!

This isn't a new problem set, but I thought this was too good to not post here. Springer has made a large number of graduate and undergraduate mathematics textbooks available for free! Obviously these are for grown-ups who want to learn more mathematics rather than kids, but go get yourself some PDFs if you want to brush up on just about anything!

Stay tuned for another non-problem set post about some adventures in monte carlo modeling!

Friday, December 18, 2015

Ice Skating (approximately)!

Link to PSet
Answer Key: Pending


It's been a while since I posted a new problem set (and I still owe everyone an answer key for HW8), but hopefully I can make up for that with the return of Boofernaut and Boofinski. This time, the two of them are doing some ice skating together and Boofernaut is trying to figure out how to make the best copy (or approximation) that she can of the paths her brother makes on the pond.

The goal of this assignment is to get kids thinking about how to make a model of something complicated with simpler tools. We tackle this in one dimension by trying to make piecewise-linear approximations of curved paths and then in two-dimensions by using LEGO bricks to make a model of a closed contour. In both questions, we ask kids to think about what changes in their approximations as they get to use a lower vs. higher resolution model (more lines in 1D, or making the shape bigger/smaller in 2D) as well as how they decide what approximation is the best. How do you choose what details to leave out and which ones to model?

I also ask kids to think about the "inverse problem" in each case: If you only have the approximation to start with, what do you think the original curve or shape was? This is particularly fun because there is definitely not just one right answer - there are endless original curves that could lead to the same simpler model. Inverse problems are everywhere in science and mathematics (we deal with them in my lab when we try to use EEG measured on someone's scalp to make guesses about where in the brain activity is coming from), and hopefully this is a nice introduction to the challenges of making inferences from sparse data.

We ask you to use some LEGO bricks to solve the second set of problems here, so I thought I'd include a link to one of my favorite 3D shape approximations - the LEGO sphere! The instructions at this link are not mine, but we did manage to follow them a while ago to make a pretty sweet approximation of a half-dome out of standard bricks (we didn't have enough unused bricks to make the whole thing). Enjoy!

Friday, November 6, 2015

Adding Arrows!

Link to PSet
Answer Key: Pending

You know what we're doing a lot of in first-grade math at school? Adding small numbers. Over and over and over again.

Needless to say this is wearing a bit thin already, so I thought we could extend addition a bit by introducing vector addition in this problem set. If you've ever worked with vectors, you know that all we're really doing is adding numbers in two dimensions, but my thought here was that this was a nice way to start developing intuitions for how to alternate between geometric and algebraic viewpoints. We talk a bit in this problem set about how to develop a notation for vectors that will allow us to work with them algebraically, but most of the actual questions are about drawing vectors in the plane.

Compared to some of the other Psets, this one is likely to be a bit easier, but hopefully still interesting. I'm still working on finding the right level of difficulty and the right level of fun stuff to do, so if you've been working through any of these with your kids, I'd love any thoughts about what kinds of questions have been the most fun to work on. Enjoy!

Monday, October 26, 2015

Halloween Geometry

Link to PSet

Since Halloween's nearly here, I thought a problem set with some spooky shapes would be fun. There's no answer key for this one because these are more like exercises than real problems: We walk through two fairly simple compass and straightedge constructions to make some Halloween-y moons and ghosts that have some special properties. If you end up making either of one of these (or both) feel free to send them my way and I'll post some student images here on the site!

A practical note: I suggest in the PS that you may want some graph paper for Exercise 2 in particular. If you don't feel like buying yourself a whole pad, you can find some patterns to print out a sheet at a time here. This site also has hexagonal graph paper and some other fun options we may use in later problem sets.

We're really only introducing two new topics here, but they may lead you to some fun ways to play around with Euclidean constructions. Once you know how to bisect lines and arcs, there's a lot of neat stuff you can do to play around making symmetrical shapes of your own design. Those shapes may also be a fun starting point for making your own tessellating shapes, per Exercise 2. I don't really talk about tesselations in depth here (I figured this could be more of a "follow-the-steps" kind of problem set), but we'll almost certainly return to them in future assignments and talk about their properties in more detail. For now, I'd say that trying to work out why the ghost works (especially how his final zig-zag needs to be drawn) is a good way to build some intuitions about tesselations.

If you like tesselations (and who doesn't?), you may want to try playing around with the two shapes below, which are called the "Kite" and the "Dart." These are prototiles for an aperiodic tiling of the plane, which means that try as you might, you won't be able to come up with a way to make a repeating pattern with these.



If you want to find out more about aperiodic tiling, go check out the wikipedia page for Penrose Tiling, which will point you to more fun ways to cover the plane. Happy Halloween, and happy constructing!

Sunday, October 18, 2015

Cookie Cutting in HW5!

Link to PSet
Link to Answer Key.

In this assignment, I've decided to go back to some problems that are more geometric and encourage kids to play with making (and breaking) shapes. You may find that you want either a compass or a small circle stencil for some of these problems...I found a pretty handy stencil for about $2, and they're are fun things to play with that may come up again in future problem sets. If you're really stuck, however, coins of different sizes would probably do the trick.

My main goal in these problems was to give kids an excuse to experiment. To that end you'll find two worksheets worth of "cookies" to chop up in whatever way you like, and I'd definitely say that trying out different kinds of shapes (especially concave vs. convex shapes) is a great way to extend what's going on here.

Finally, if you want to read more about cutting up pastries for the sake of mathematics, Martin Gardner's article about cutting up a real donut is quite funny (especially the reader mail from people who tried to do it and found that real donut-cutting is heavily constrained by the crumbliness of actual donut matter).

Friday, October 9, 2015

Alternate Q2 and Q3 for HW4

Link to revised PSet

Last time I mentioned that the last two questions of HW4 seemed too hard (or at least too tedious), so I've revised those to be a little simpler. We're still asking you to think about how to count up the mismatched sets that Boofernaut can wear, but the number of colors is reduced from 5 to 4, which ought to make this easier to think through.

The last question is now one about rearranging a set of 3 colors into distinct orders, and I decided to actually give the answer but challenge students to fill in the possibilities. In general, we've found this is a decent strategy for making problems easier to attack: The uncertainty of knowing whether or not you're done is a big stumbling block sometimes.

Somewhat unrelated to the homework, but I just finished Siobhain Roberts' book "Genius at Play" about John Conway, who is an incredible mathematician who you can find lurking around the biographies of other incredible mathematicians and in lots of material about recreational mathematics. His own biography is fantastic and includes lots of great descriptions of games, puzzles, and pure mathematics.