While in Ohio over Christmas, a daughter of Jen's cousin got one of my old favorite games, Toss Across. If you're not familar with this game, it's basically tic-tac-toe but you have to throw beanbags at the board to place your mark (the X or the O). Since your throw can be slightly off (assuming you don't have my deadly accuracy), there is always the chance that you'll put your opponents mark on the board in place of your own.

Interesting side note, one of the other guys and I also discovered that this can be turned into a rather amusing drinking game. But I digress.

While playing this game, I started thinking... everyone knows that, with a properly written program, a computer will never lose a game of tic-tac-toe. In fact, if you set two such computers up against each other, they will always play to a tie. Further, if the computer exists in the world of a Matthew Broderick movie, this knowledge will drive the computer over the edge. But, again, I digress. So the big question becomes, what would happen if, instead of always placing the desired mark on the board, there was some uncertainty in the mark that is placed on the board?

A vexing question indeed.

First, a little terminology to help the conversation along its way. A mark is a symbol placed on the board. In general, these are referred to as X's and O's. A location is one of the nine squares in the board into which a mark can be placed. A rank is three board locations in sequence; they can either be three across in a row, three on top of each other in a column, or either of the two diagonals. There are eight ranks on the board.

Nowadays, it seems that whenever somebody considers a problem where there is a non-deterministic chance of an event occurring, they have to refer to it as Quantum-Something. Well, I don't want to be left out in the cold during quantum mania; consider this Quantum Tic-Tac-Toe. Instead of placing your mark, you're placing some quantum bit that can decay into either of the two states (the marks) with some pre-defined probability.

The easiest case to consider is when there is a 50-50 chance of placing the correct mark. With a 50-50 chance of placing the correct mark, in a tie condition, the board will be filled with randomly placed marks. The probability of any one rank not containing three marks of the same type is 1 - 2 * (1/2) ^ 3, or 0.75. The probability of all eight ranks not meeting this condition is 0.75 ^ 8, or about 10.0%. However, this assumes that there is no correlation between the ranks. Sadly, for those such as me seeking the easy way out, this will greatly complicate things. The correlations will act to reduce the number of allowable combinations, and thus 10% can only be consider an upper limit. Another note about this condition is that there should be no advantage to moving first since the marks are basically random.

Another place where we can make a guess as to the expected is behavior is when the probability of placing the correct mark is very high. In this case, we can assume that placing an incorrect mark will lead to a loss since our opponent does not make any mistakes. Therefore, the probability of a tie will be reduced linearly as the probability of making an incorrect mark increases. Of course, as the probability of making more than one incorrect mark increases, this approximation will go right out the window.

Clearly, this problem is far more complicated than a simpe childrens game would lead one to suspect. Now, the smart person would sit down and crank out some exhaustive mathematical proof describing the behavior of this system. I'm not such a person. I am however rather adept at computer simulations, and, thank goodness, brute force is easily applied to this problem.

To start, we need a computer that can play tic-tac-toe. This is pretty easy. When making a move, we first look to any location where placing our mark will win the game. If no such move exists, we then look to any location where placing our mark will prevent our opponent from winning the game. Barring that, we need to evaluate each location on the board and evaluate the strength of placing our mark there.

To determine the strength of a location, we evaluate each rank affected by this location. If placing our mark in this location gives us a rank with only our marks in it, we give the location a unit of strength. If placing our mark in this location gives us a rank where our opponent used to control the rank (we had no marks in it), we give the location half a unit of strength. If the rank already contains our mark and our opponents mark, there is no strength. The strength of each location is the summation of the strengths of each of the ranks it affects. In the case when multiple locations have the same high value of strength, a location is selected randomly from the highest strength locations.

When the mark is placed with 100% accuracy, I've found that this simple algorithm can never lose a game. And, given the chance against an imperfect opponent, it will always win the game when possible.

All that remains is to set this lose.

I varied the probability of making the correct mark, and played 200,000 games of tic-tac-toe at each setting. The results are shown below.

As expected, when the probability of making the correct mark is 50-50, the chance of a tie game is less than 10%; turns out to be closer to 6%. Also, as expected, at this probability, there is no advantage to going first.

As the probability of making the correct mark goes below 100%, there is indeed a linear slope which is proportional to the chance of making one incorrect mark.

I wasn't sure if moving first would actually provided an advantage at the "in-between" probabilities. It appears that, though small, there is an advantage to going first.

I suspect that this is just about the most application-free simulation I've ever performed, but I must say that it was quite fun.

Last year the US government claimed that it was not going to go forward with its plans to open a department dedicated to promoting US interests through propoganda. So, how to explain a story in the news like this?

The headline boldly declares, "Once Fans, Arabs Now Souring on Saddam." It goes on to offer many supposed examples of people (Arabs) who used to support Saddam, but who support him no longer.

After reading this story, one things sticks out like an elephant hiding under a card table: nowhere do they give the results of an actual study concerning Saddam's popularity among Arabs. Are we supposed to believe that no such study exists? Or are the results just a little too embarassing to include in a report with this angle?

Here's a disturbing news story. Since tax revenues are falling (gee, I wonder why?), some states are once again sounding the drum to tax sales on the internet. To quote one of the lobbyist in favor of such a measure, "We can no longer ignore an entire segment of the retail marketplace."

Well, actually, I think you can. Forget about the logistical mess invloved since sales taxes vary in every city/township/special tax zone/county/state and ask yourself this: why do states, or other local communities, think they have a right to a piece of this pie? The only reason they seem to offer is that they need more money, therefore they should be able to go get it any way they like.

For all of you Arnie fans out there, the trailer for Terminator 3 is now available. I must say, it looks damn cool.

In addition, I have it on good authority that this film features a Pinzgauer.

As the end of the year draws near, it's time for the annual ritual of the lists. Yes, lists of the top this, the worst that, the most memorable something-or-other. Boring, boring, boring. I like this list from The Beast; The 50 Most Loathsome People in America, 2002.

Not only does this list skewer one and all, I actually agree their choice for Number 1.

They say that President Bush no longer drinks booze. I guess I believe that, but after seeing the Barney-cam, I'd say that someone in the White House is knocking back some fortified egg nog. Somebody though it'd be a good idea to strap a camera onto the Bush's dog, Barney, while he ran around and checked out the White House Christmas decorations. Frankly, I think this is the best idea to come out of the White House in several years.

I hope David Letterman gets some royalties out of this.

Next time you're flying, before you select your seat, check out seatguru.com. For a variety of airlines and planes, this maps out the best and worst seats on the plane. Very useful for the frequent flier.

In an effort to facilitate the consumption of mass quantities, Modern Drunkard magazine has come up with a list of bar signs for non-verbal communication. The thinking is, the more you talk, the less you can drink. Usage of these signs removes a significant hurdle in anyone's attempt to get lit.

Just in time for the holiday travel crunch, the government is enacting new procedures that will be sure to result in longer delays. You will no longer be able to check in at the gate. For me, this doesn't sounds like too big of a deal since I never do this anyway. But many people do. And that means that all of those people will now be at the main ticket counter, resulting in even more monsterous lines.

I have to wonder, how much more secure is this going to make the airport?

Google has a cool new tool available called the Google Viewer. Instead of just showing you the search results, it displays the actual pages that it finds as a scrolling slideshow. It's kind of like the scan button on your radio; when you find the page you want, you can tell it to stop scanning.

Wow. Here's a headline I never thought I'd see on Yahoo: Stocks Up After Recent Fall; Maxtor Helps. It's a sad day when the disk-drive business has to prop up the stock market.

The can of worms that is the internet continues to grow. A judge in Australia has ruled that an Australian man can sue a US company, in Australia, for defamation based on an article they published in the United States. Why? Because the article was later published on the internet.

According to the judge, "What it means is that foreign publishers writing material about persons in Australia had better have regards to the standards of Australian law before they upload material to the Internet." Now excuse me, but this article states that there are 190 countries with defamation laws. If I follow this judge's reasoning to its logical conclusion, that means that you can't publish anything on the internet without ensuring that it does not break the defamation laws in any of over 190 countries. Um, that sounds like a bit of a pain.

There was a very interesting story on 60 Minutes last night. It talked about how during the first Gulf War, stories were told to congress and the UN about the atrocities being commited by the Iraqi soldiers. The purpose of the stories being to make this look like a situation in which we would should intervene. These stories were not told for the benefit of our leaders, they were told to drum up support from the public. Only one problem though, they were all lies.

The story goes on to investigate the claims being made this time around by the Bush administration. Big surprise, once again most of these stories don't stand up to any sort of scrutiny. It appears we are once again being knowingly lied to in an attempt to build a pretext for war.

At least last time Iraq actually did something, they invaded Kuwait. Whether would should have cared is a matter for debate. But this time, they don't appear to have done a single thing. I have a hard time reading headlines where President Bush says Hussien can't be trusted, or that he's obfuscating. It's not that I doubt the truth of the statements, it's just that I hate to see the pot calling the kettle black.

A man in Seattle claims to have been behind the bigfoot hoax. What, it was a hoax?

Now if they can just find the guy who lives near Loch Ness in Scotland who happens to own a big sea serpent suit, then we'll really be putting some things behind us.

At our house, the great automobile reorganization has begun. Our current car configuration consists of a GMC Sonoma, and a Nissan Pathfinder. Because we live in the mountains, we really need two 4WD vehicles. Also, we need a truck since we have to haul firewood, slash, and whatever cool stuff we buy at the hardware store.

Only problem, the Sonoma is fairly new and it's getting kind of beat up with all the work around the yard. Imagine that, using a truck for actual truck-like activities. Unheard of, I know. In addition, both of our cars get pretty poor mileage.

Enter the re-org.

Yesterday, we traded in the Sonoma for a Civic Hybrid. That takes care of the poor gas mileage problem since this baby gets about 50 mpg. Frankly, after driving this car, it's a mystery to me why more companies aren't making more cars like these. It costs about $3000 more than a regular Civic, but you get a $2000 tac credit, not to mention the savings in fuel. Over the life of the car, it'll probably be marginally more expensive, but for using half the gas it seems well worth it.

In addition, we bought a Pinzgauer which is a truck used for many years by the Swiss Army. For some reason, the previous owner decided to paint ours red. This truck will be better for the work around the house since it has great ground clearance and hauling capability. And, when we both need to be out and about in inclement weather, it will serve as the second 4WD vehicle.

Yet another reason not to shop at Wal-Mart.

Taking a page from the tobacco companies that sponsored all of that great scientific research that found no link between cigarattes and cancer, Microsoft has sponsored a study that, hang on to your seats, finds that running Windows 2000 on servers is cheaper than running Linux. Never mind that fact that Microsoft was recently outed as mounting a covert campaign to discredit open source software.

Ah the humor... conservatives are getting on Bush for portraying Islam as a religion that is generally peaceful. You see, unlike their religion, they think that Islam is inherently violent and prone to war. And they want Bush to call a spade a spade.

To quote one of the proponents of this belief, "After all, its founder, Mohammed, was a warrior, not a peace advocate like Jesus."

To these people, I have two questions: 1) Have you ever read the old testament? and 2) Have you ever read the history concerning the crusades?

Yesterday, Jen and I went to look at the Honda Civic Hybrid. For those not familiar, this is a "normal" Civic car, with an electric motor/battery system that assists the engine. With the automatic transmission, this car gets about 50 mpg on the freeway and in the city.

After driving it, I am surprised to say that it drives like a normal car. It has plenty of power going up hills (due to the high tourque of the electric motor) and ample acceleration.

The best part about driving it is that you get instant feedback concerning your fuel economy and the battery usage/charging. I can imagine that driving one of these on a daily basis would make any commute more interesting as you try to figure out the braking and acceleration patterns that lead to the best fuel economy.

Also cool is the Continuously Variable Transmission. It's an automatic transmission that has no set gears; it's infinitely adjustable. It's a little odd at first because when you accelerate from a stop, you expect to feel gears changing. But you get used to it real quick and, as I understand it, this is another way they squeak out more fuel efficency.