Back in high school (not that many years ago, I'd like to think), I was in a programming competition that pitted a program I wrote to play a 2-player game against those of all of my classmates in a single-elimination tournament. I made it to the finals and eventually won, though after discussion with the other finalist we both realized that based on our PASCAL code (ok, that many years ago) the winner would have been the program that went first. More importantly, both of us wrote very shortsighted code; that is, we set up a series of rules like "look for a winning move first" and "look for a block second". It was only a matter of time before I learned the more traditional computer science approach to creating algorithms for 2-player games: game trees.
A game tree is a symbolic representation of all the possible outcomes of a game where nodes are the "states" of the game at a given time and the connecting arrows are the possible "moves" (called "plys" in game theory). Think of it as an inverted tree where the root node represents the start of the game and all its branches representing a player's first turn.
The common example for explaining game trees is the well-known game of tic-tac-toe. Player 1 starts out with a blank grid and 9 possible squares to click in. After a spot is chosen (and an "X" is placed), there are 8 other squares from which player 2 can choose (and place an "O"), which then leaves 7 squares for Player 1, and then 6 for Player 2, and so on. You can guess that even a game as simple as tic-tac-toe, guaranteed to be over in 9 moves, can have a pretty large number of possible ways it can be played. At first glance you may even calculate the number of nodes in the game tree to be 9! (362,880), though luckily there are several factors we can use to trim this number down (to 26,830 nodes, in fact).
The first way to trim a game tree is to consider all of the branches that never make it to ply number 9 because the game has already finished. For example, imagine Player 1 winning with 3 spots still on the grid (however unlikely, it's still possible); the last 3 plys for that branch never need to be calculated. Another important way to "prune" the trees is to recognize any kind of symmetry (rotation, reflection) across branches and represent each by one and only one branch. For example, if Player 1's first move is to a corner, any corner, our game tree only needs to have one branch as each of the other 3 nodes where Player 1's first move is a corner can be rotated to look like the first. The same is true of Player 1's first move if to a side spot. Add in the branch that stems from Player 1's first move to the center spot and you now have 3 branches coming out of the root node, not 9...now that's some good and efficient pruning.
In the project below, I've recreated the commonly seen 2-ply game tree for a tic-tac-toe game. Playing with this visual and interactive model may give you a better understanding of how game trees are constructed. The sitemap of the workBench project is what the (beginning of the) game tree would look like. Look at the number of branches each node spawns and see if you can figure out why none of the 2nd-tier nodes spawn 8 branches. Also, there are lots of other, more sophisticated ways of pruning game trees if you are interested, but they are beyond the scope of this post.
So why are game trees important anyway? Why would knowing about them have changed how I made that program all those years ago? The answer is simple: if you can make a model of all possible outcomes, you can choose the path that helps you the most. In a 2-player game tree, this can be done in a variety of ways, though an easy example is to "rate" each node, started from the end of each branch, or leaf nodes. If a node gives Player 1 a win, assign a rating of 1 to that node. If it gives Player 2 a win, rate it -1, and if it is a tie, rate it 0 (this is how I was taught, though you can use any rating system you'd like, such as colors or shapes). Once all of the leaf nodes have been rated, the nodes in the ply above them can be rated as well, all the way up to the top using the following rules:
For each node X on ply Z, look at the parent node Y one level up on ply (Z-1).
If all of node Y's children are rated the same way, give node Y that rating.
If any of node Y's children are rated as a win for the player whose turn is on ply Z, rate node Y a win for that player.
If neither condition applies, rate node Y a tie.
This may seem hard to understand, but in a nutshell all it means is that if you have to choose between a bunch of moves, all of which have ratings already, you don't want to choose one that has at least one outcome where your opponent wins, assuming your opponent will see that opportunity and take it (that's the crux of step 3).
If you are an educator and involved in anything that revolves around game theory, recursion in programming, or even symmetry in high school Geometry, constructing (or filling in already started) game trees for simple 2 player games may be a fun and productive activity.
It may even be the key to you winning a programming tournament in your high school computer class...
The Eagles gave them a run for their money last night, that much is certain, but the New England Patriots are still undefeated improving their 2007 season record to 11-0. The toughest challenge of the remaining games still seems to be Pittsburgh, though Philly showed last night that not every game against the Pats is a blowout.
Who was the player of the game last night? Was it Wes Welker (13 catches, 149 yards), Jabar Gaffney (6 catches, 87 yards, 1 TD), or maybe Asante Samuel (2 interceptions, 1 runback for a TD)?
Of all of the questions, the ones that gained the most publicity (by far) were the questions asking students what they'd settle for in return for their right to vote (forever). I'm not sure if this was multiple choice format, but many headlines read something along the lines of "Students at NYU hapy to give up their right to vote for an iPod".
This is, of course, an oversimplification, but reading the article made me think about my own right to vote. I'd always been taught that voting was perhaps the most important thing I could do as a citizen of this country (right up there with jury duty!), and for all intents and purposes this teaching stuck; I make sure I go out just about every November and cast my ballot. However, I can remember some heavy discussions about recent elections (see election, presidential, 2000), many of which brought the actual value of my singular vote into question as well.
How much is my vote really worth? For the moment, forget monetary value...that is, does my vote really matter for anything? I'd like to believe the answer is "yes", but can anyone be so sure anymore? If, then, one's vote is worth nothing, why not take a million bucks or free tuition?
The answer is simple, to me at least. I believe that the right to vote is priceless, and is one of the reasons, nay, freedoms for which people want to come live in this country. Even if my one vote doesn't sway an election, I treasure the fact that I have the ability to choose who our leaders will be and how our laws will evolve...
TLM showed me this today, which I used as a basis for my post over at TRintuition. Somehow this has been around the net for a long time and I had never seen it until today. Still pretty cool...
You're supposed to see the figure spinning one way, then try to get it to spin the other way. Using the shadow underneath the figure makes this easier, and eventually you will be able to do it, trust me.
To commemorate this year's birthday of Baseball Joe, I'm including a clip from the "Baseball History Podcast", something I think he'd enjoy. Too bad most of this week's episode revolves around the Highlanders (soon to be Yankees) and their totally disreputable star, Hal Chase.
If you want to subscribe to the podcast, you can find it in the iTunes directory, or alternatively just subscribe to http://bhp.libsyn.com/rss. Happy Birthday Pop!
I found this comic on BoingBoing, and I think it's an interesting take on today's holiday, it's history, terrorism, and let's throw in illegal immigration (why not).
I'm not sure if it's a consequence of getting older, and it certainly has nothing to do with what the holiday is supposed to represent. It's everything else about it that makes me crazy. The people in the stores, the pressure to plan out tomorrow making sure to be as inclusive of everyone as you can, and of course then there's the actual family members. As far as I can tell, any plans you make with them prior to the day before Thanksgiving should always be disregarded; they always seem to change at the last minute.
Ah, how I miss the days of my childhood, never having to worry about where or when I had to be somewhere for a family event.
I found this on Joel Spolsky's "Joel on Software" blog...and it's pretty fresh. It's a Google Maps mashup called Walk Score, which, once you supply an address, gives you a list of stores, bars, restaurants, and parks in the area. and, as it's name implies, a "walk score". They are pretty big on getting people to walk places, and identify themselves primarily as a tool to "help homebuyers, renters, and real estate agents find houses and apartments in great neighborhoods."
Our place only got a 58 out of 100 (I believe that's just failing), not surprising since we now live in a suburb. My last place in Eastie got a 75, which leads me to believe whatever algorithm they use to calculate this score doesn't take into account personal safety while walking.
Bust out the Black Sabbath clips - Mike Lowell appears to have come to an agreement with the Red Sox for 3 years. Excellent. Things couldn't have worked out better.
Happy Birthday Al! Sorry the Celtics lost, but the Pats are still undefeated, A-Stupid stayed with the Yankees, and now Mike Lowell gave us some good news today.
We decided it was time to give our facelift, and so last weekend we went out, got some paint and some tiles and went to task. Who knew vinal tiling was this easy?
TLM even found a nice replacement for the whiteboard. Note the coat hooks, er, mega key rack on the bottom.
So it looks like A-Fraud will remain a Yankee after all, and the deal was done without superstar sports agent Scott Boras (haha). Good...he can hit all the home runs he wants, but as long as he's on the Yankees, they will never win a postseason series.
"I like to keep all the people I hate together, so I don't feel conflicted." -TLM on A-Rod staying with the Yankees
I agree. Needless to say many others called up sports radio today and shared the same sentiment. My big question is, why the rush? Wouldn't it have made more sense business wise for A-Broad to hold out until January, like Johnny Damon did? At least another month of shopping himself around was, I think, expected.
Some say he came crawling back because he always wanted to stay with the Yankers (maybe)...that it was his agent who caused all the friction (highly likely). Others will point out that not that many other teams would have been able to afford his hefty price tag (probably true). Still others will claim that he just wants to be on a winning team, a claim to which I respond "...so why is going back to play for the Yankees?".
I think something else is going on here. The Mitchell report is coming out within the next couple of months, and we already know that there are going to be some "big names" on the list, including over 10 current free agents. We also know that those free agents know who they are. Could it be that the big rush to sign a guaranteed contract with a team was, dare I say it, an act of desperation by a man who knows his value is about to go down? Is there a clause somewhere that will let the Yankees opt out of his contract if that's the case? Are purple lips a side-effect of using too many steroids?
Let him play on the Bronx so he can hold them back...while he is still allowed to play.
How cool is that title? "Aquatron" - is it some kind of underwater computer? Might it be an 80's game where you race fish? Perhaps it's a color most men have never heard of.
In fact, the Aquatron was a "Space Age" 8-track stereo put out by Brother in the late 60's / early 70s. I ran into one today when I went over to see Jaz's new place (finally, seeing as how he's been there a year).
The place was nice, and definitely lived up to the description he gave me, including lots of homemade art on the walls, a dance room, and an impressive ready-to-record music room. There was even an office (work is done between painting, dancing and playing music), complete with at least three Macs in sight - laptops and desktops - and it was in this room I saw the Aquatron sitting innocuously on the corner of a table.
It didn't really stand out at first, as there were lots of other interesting objects to look at in the room, but shortly after Jaz pointed out its suction-cup base and hide-away handle, he casually mentioned what I think is its coolest feature (and the reason I'm even posting about it): they have the Aquatron hooked up to play music through Airtunes.
That's right; one can port any music they want to hear directly to this stereo, (thus completely removing the need for 8-track tapes!). In a house where, and I quote, they "don't have cable, man", I find this to be the best use of Airtunes I've seen yet. Nice.
One of the classics is still the best, and is even available as a widget, though I decided to make it a post rather than a permanent part of the site in the name of productivity. Don't waste too much time, you have work to do!
Content found on The Neoteric is of no particular genre, topic, or focus, other than it was all at some point, in some way, interesting enough to me to write about.
