 |
 |
 |
 |
|
|
|
|||||
|
|||||
|
|
Recursions
Let's talk about recursion. If you aren't a computer or math geek the term might not mean much to you, or at least not the same thing. But that's okay, we'll have some fun with it. Here's a dictionary entry:
Another type of recursion is found in conversations with two year olds: "why is the sky blue" "due to refraction of certain wavelengths of light by the atmosphere" "why" "because particles travelling through a medium respond differently based on their wavelength" "why" "something to do with subtle variances in...oh, never mind" "why" "because I'm not going to explain everything to you" "why" "because" "why" "I want you to stop this right now" "why" ... Inside your computer recursion isn't quite so annoying and in most cases is used to perform meaningful work. Think of it as a computer function that calls itself and keeps doing so until a certain condition is met (or the computer crashes). Here's a simple recursive function for measuring the height to the moon:
There's a couple of things to make a note of here. First off we need to check if we have reached the moon and if so print something out so all of that measuring didn't go to waste. Secondly if we find that we haven't reached the moon quite yet we take the previous measurement, add twelve inches to it, and call the function go_to_the_moon with the new distance, in other words call ourself all over again.
go_to_the_moon (0)
go_to_the_moon (12)
go_to_the_moon (24)
go_to_the_moon (36)
go_to_the_moon (48)
go_to_the_moon (60)
...and so on...
The first check is really important since otherwise you'd simply keep stacking rulers on top of each other forever. In this case our check probably isn't a reliable one since it assumes that the moon is going to be directly overhead and that we'll climb right to it. But a slight wind could bend our stack of rulers and send us off into infinity...and beyond. We could fix this "bug" by putting in another check or fail safe, maybe giving up if we reach a bazillion miles or it's time for supper. Another thing to consider is when a computer function calls itself over and over like this it will eventually have to "unwind." That's usually how the answer finds it's way back, the unwinding go_to_the_moon returns the value passed down from above and so on until we finally unwind them all and have the answer.
That was fun but otherwise it looks like a supreme waste of time. What good is recursion then? Well, there's some great mathematical functions which use recursion but they probably aren't very exciting either. The one place where recursion is used that you might be able to make a connection is in games.
When you play a game of tic-tac-toe, checkers, or even chess you are most likely using a form of recursion to decide on your moves. Certainly your mind's version of recursion is far to elegant and difficult to completely understand. But we do our best to mimic some of the brain's reasoning when making a computer opponent.
| |
___|___|___
| |
___|___|___
| |
| |
Let's look at tic-tac-toe for a bit. Already you have probably formed a move or two in your mind just out of habit. If you get to go first then it's straight to the center, otherwise you decide to try a corner and sucker the other guy into something foolish or at least drive things to a draw. You may have even thought out a few moves by now. That's a form of recursion, you are mentally placing a piece, weighing the result, then either putting down another piece and doing the same weighing or back tracking because the result didn't look so good.
It's more than recursion though. If you've played the game before you have stored away some "tips" that you've learned. Like the bit about putting a piece in the very center; if that's one of your options then you don't even go into a recursive thinking mode you just do it. With enough experience you may not even think about followup moves. It's not that you don't need to do the recursion/weighing, it's that you've already done it enough times and have stored it permanently in your mind, either as a picture, a gut feeling, or a step by step process...depending on how your mind works best.
Now let's try and tell our computer program how to play the game. Since the computer has NO IDEA about human nature we have to be very explicit. You can't say things like "oh, no one ever plays the first piece here" because if someone ever did the computer can't simply freeze up and refuse to play.
Yeah, so what's the big deal? Why don't we tell the computer what to do with every possible move, how hard can that be? With tic-tac-toe it's not that hard, but moving onto other games it becomes complex very quickly.
Let's do a little exercise to illustrate how the options in tic-tac-toe work and how best to express them to the computer. You and I think of games mostly by the visual grid we play on. Sometimes that works well inside the computer other times different structures are needed or at least we think of them in slightly different ways. In fact let's think of each square as a tree in the back yard. That gives us nine tree trunks representing the nine open squares at the beginning of play:
1 | 2 | 3
___|___|___
4 | 5 | 6
___|___|___
7 | 8 | 9
| |
Which we'll flatten out into a sequential list of "tree trunks" like this:
| | | | | | | | |
1 2 3 4 5 6 7 8 9
Player one comes along and of course puts their X into square 5.
X
| | | | | | | | |
1 2 3 4 5 6 7 8 9
That leaves the computer with only eight possible choices, hey, it's getting easier already! In fact, to celebrate our newly realized narrowing of choices let's re-organize things a bit and put branches on tree five.
| | | | | | | |
1 2 3 4 6 7 8 9
/______________ __________________/
|
X
| | | | | | | | |
1 2 3 4 5 6 7 8 9
That makes it easier for the computer to think about it and takes our tree metaphor up a notch, er, branch. We've set it up such that whenever someone plays on a 5 then these are all the possible counter moves the computer can respond with. Since our computer is pretty stupid (no stored knowledge about the game) it simply picks one at random or, even worse, picks the first one it runs across.
O
| | | | | | | |
1 2 3 4 6 7 8 9
/______________ __________________/
|
X
| | | | | | | | |
1 2 3 4 5 6 7 8 9
Which nicely reduces our consideration for pieces yet again
| | | | | | |
2 3 4 6 7 8 9
/______________ _____________/
|
O
| | | | | | | |
1 2 3 4 6 7 8 9
/______________ __________________/
|
X
| | | | | | | | |
1 2 3 4 5 6 7 8 9
Boy, this is going to get hairy real soon and we're only two moves into the game. The worst part is that we still haven't helped the computer out much. We've setup some structure for showing the "tree" branches of possibility but nothing that alerts the computer to the possibility of winning or losing, much less strategies to start on a winning path from the very beginning. We'll stop using our trees for a while but they'll be useful when we get back to talking about recursion (oh, yeah, recursion).
What we need is a measurement mechanism. Something that can look at the playing field and say "wow, O is hosed!".
O | |
___|___|___
| X |
___|___|___
| |
| |
That's what we've done so far. You look at it and think "X is doing ok but O isn't out of the game yet." What is your measuring criteria? You most likely have assigned slightly different values to parts of the board, something like:
1 |0 |1
___|___|___
0 |2 |0
___|___|___
1 |0 |1
| |
That's good. The computer can store something like that in it's memory and use it as a cheat sheet to help determine where to move. The human player may or may not have the same scoring method, in fact for the sake of this exercise X does the following:
O | |
___|___|___
| X |
___|___|___
| X |
| |
Yikes, O needs to block! But if the computer were to use our previous measuring system it would respond with something like:
O | | O
___|___|___
| X |
___|___|___
| X |
| |
And we'd all groan as X finished the computer off. So our measuring system needs to be a bit more dynamic. In fact it really needs to change each time either side makes a move. There are two ways to do this, the brute force method is to store a "weighted" version of the board for every possible move. At each of its turns the computer simply looks up the right cheat sheet for the current state of the game and uses that to make the next move.
That is certainly possible with a game like tic-tac-toe, you have a grid of nine scores for the first move and for each of those moves there are eight scores, for each of those seven, and on down. Tiresome but doable, but it doesn't scale well into other games. Imagine trying to sit down and make these cheat sheets for checkers? Chess? Uhg! No thanks.
But drudgery is something that computers are good at. We need to initially sit down and lay out some rules and guidelines for the computer to follow, but once we've done that the computer can use them for countless iterations and not get bored. How the heck do we make computer rules for weighing a board? Are there any patterns that make it easier? Well, sure, you need to look at the horizontal, vertical, and diagonal lines on the board since those are the only way that you can win a game.
1 | 2 | 3
___|___|___
4 | 5 | 6
___|___|___
7 | 8 | 9
| |
Dissecting our board into such lines we get: 123, 456, 789, 147, 258, 369, 159, 357 Hey, that's not so bad, eight "shapes" that the computer needs to keep an eye on. What else can we say about our shapes? Well, if any shape has both an X and an O in it then we can ignore it completely, it's basically out of the game. Something else we notice is that the number 5 (center box) shows up in the most shapes, another interesting tidbit the computer can use when trying to choose which spot to take. Looking at the boxes another way we can organize the boxes by how many shapes they show up in
shapes| box# | score
------+------------+------
4 | 5 | 2
3 | 1, 3, 7, 9 | 1
2 | 4, 2, 6, 8 | 0
Which matches right up with our initial scoring cheat sheet earlier. Now we are getting enough information together to making a scoring system for our tic-tac-toe board that the computer can implement.
We want the computer to be able to "weigh" the overall score of the game for a side after a move has been made. In other words, O moves to box 2 what is the score? Or what's the score for a move to box 3, 4, 6, 7 and 9? That helps us decide which move is a keeper.
O | |
___|___|___
| X |
___|___|___
| X |
| |
Hopefully this algorithm that we are making for the computer will be able to help it make the right move here. Unlike you and I the computer can't really "imagine" that it's making the moves, it has to actually make all of these moves, measure things, repeat until done and then clean things back up before making the move on the screen you see. You can best think of the computer having two game boards, the one you see and the copy of it that it is playing with inside it's "mind". Let's make the scoring algorithm, but first we need something to score, so the computer makes a tentative first move in its "mind" based on it's last cheat sheet:
O | * |
___|___|___
| X |
___|___|___
| X |
| |
We check each of our "lines" and find that "123" has two O's and "258" has two X's, both scoring evenly, let's give two of a kind in on line a score of 5. O = 5 X = 5 But remember we decided that certain positions on the board are worth extra points (box 5=2 : boxes 1,3,7,9=1 : others=0) so we need to add those into our scoring.
O = 5 + 1 + 0 = 6 X = 5 + 2 + 0 = 7
Well, boogers, that's not such a good spot after all. Since the computer is simply executing a routine we'll have it do so for all of the open spots so we can tally up the scores and pick the best one.
O | | * O | | O | | O | | O | |
___|___|___ ___|___|___ ___|___|___ ___|___|___ ___|___|___
| X | * | X | | X | * | X | | X |
___|___|___ ___|___|___ ___|___|___ ___|___|___ ___|___|___
| X | | X | | X | * | X | | X | *
| | | | | | | | | |
O = 7 O = 6 O = 1 O = 7 O = 2
Best that O can do looks like 7 and, being a computer, it picks the first one it ran across and we get a move like:
O | | O
___|___|___
| X |
___|___|___
| X |
| |
Pretty darn depressing after all of that work to make a smart weighing algorithm. The problem isn't what we've done it's simply how we've done it. You and I both look at the board and don't really think so much about OUR next move, but the next move by X which we know has to be blocked. On the other hand the computer was told to weigh the current state of the game for its current move and it did a pretty good job of optimizing for the best immediate score.
Remember recursion? This is when we pull recursion out of our hat to save the day...or at least the next move. We need the computer to not look at just the immediate horizon, but to get out the binoculars and really look at what might be coming down the road. The only way to do this, at least in this discussion, is to have the computer play more than just the next move, but the next two or three moves for BOTH sides.
Remember our trip to the moon? Let's make another trip but this time something less celestial. We'll have a few "magic" things happening in our function but that's only to keep it readable.
Dang, things are starting to get more complicated but bear with me, it's pretty straightforward. When it's the computer's turn it may do something like this to figure out the best next move: take_a_turn(2)
Which means it's going to make two complete sets of moves, or in other words it's going to try every move for both players, itself and the opponent. The trip into take_a_turn goes like this:
Wow, imagine how messy that would be if I printed out each of the moves? It makes my head ache just thinking about it. Another way to envision this is with our previous "tree" slightly pruned to show the current state of the board when the computer goes to call take_a_turn(2) above.
| | | | | |
2 3 4 6 7 9
/_________ _____________/
|
X
|
8
/
O
|
1
/
X
|
5
Our first call to take_a_turn would make the following move (box 2) on O's behalf, and then call take_a_turn which essentially ends up making moves 3, 4, 6, 7, 9 for X and returns the "best" score.
| | | | |
3 4 6 7 9
/__________ ________/
|
O
| | | | | |
2 3 4 6 7 9
/_________ _____________/
|
X
|
8
/
O
|
1
/
X
|
5
take_a_turn then undoes the move to 2, makes a move to 3 for O and does the same sequence moving X to all of the remaining boxes (2,4,6,7,9). On and on until each possible O move and X counter move is completed. For a computer this is simple and takes less than a blink of an eye, while it's taking me half an hour to describe and diagram just a few of the moves and it's looking remarkably like noodle soup.
What do we get from all of this hard computer work? It's a little subtle and partially hidden under the "best_score" place holder I put up above. Think of best_score as the best score in relationship to O. So a high score (or a win) for O during it's moves and a low score for X during it's moves. Actually we get the highest score for each, but in the case of the returning X score we negate it (make it a negative number) before adding it to the O score for that move. Let's look at it with our real-world example. By the way remember that our scoring algorithm gives a score of 5 for two of the same in a line, let's give out 50 points for three of the same kind.
O | X | O
___|___|___
| X |
___|___|___
| X |
| |
O = 5 + 1 + 1 = 6 (scored before X moves)
X = 50 + 2 + 0 = 52
O | O | X
___|___|___
| X |
___|___|___
| X |
| |
O = 5 + 1 = 6
X = 5 + 1 = 6
To figure out O's score for these two moves we first turn the X numbers negative before adding things together. The first move turns out to be (6-52) = -46 while the second move is (6-6) = 0. Obviously in trying to get the highest score for O we'd pick the zero, even though the computer doesn't know why.
Given the time, horsepower, and computer memory we might have the computer opponent evaluate ALL turns each time, recursing all of the way down until the game is won or the game is a draw. When you get into larger and more complex games like Chess and Go you start facing issues of computer capabilities, or at least the limited patience of the human counterpart waiting for their turn.
There is much more that can be done to not only improve the speed of this kind of method, but also to increase the apparent intelligence of the computer program in other ways.
That's about all I had to share today on the subject of recursion. I've been writing a computer opponent for a more complicated game than tic-tac-toe and sitting down to think through and write out this article has helped in keeping my own recursions from flying out past the moon.
|
