A game is considered to be “solved” when all of the possible moves have been mapped out in a mathematical tree and thus the perfect set of moves can be determined regardless of an opponent’s play.

Tic-Tac-Toe is a pretty easy one. You solved this as a kid. There are three opening moves - corner, edge, center. And then you work from there.

Connect Four was solved in 1988. That’s because those new-fangled computer thingies were starting to get some real power behind them. If you want to play Connect Four against the best opponent you’ve ever played in your life, check out the applet on John’s Connect Four Playground which is programmed to play flawlessly, based on a database of pre-determined best moves. But if you go first, and play just as flawlessly, you can beat it.

Checkers was solved this past April by researchers from the University of Alberta. You can play against Chinook, which will play flawlessly, but the best you can hope for is a draw. It doesn’t matter how amazingly good you are at checkers. You will never win. For me, there’s something a little disturbing about that.

Could chess be next? There are an incredibly large number of possible games, but it must be finite. And if it’s finite, then the tree must conceptually exist even if nobody has been able to come close to mapping it yet. Some see chess playing ability as intutive and creative, and not merely a number cruching process. But if number crunching continues to get better, it might evolve to the point where we get a chess-playing program as unbeatable as Chinook.

To be clear, we’re not talking about a really, really good chess-playing program. We have that now. We’re talking about a program that can access an exhaustive database of pre-determined best moves in order to ensure the most favorable outcome possible.

What do you think?

Will computers ever solve chess?

From the American Research Group:

November 13, 2007 - Impeachment

A total of 64% of American voters say that President George W. Bush has abused his powers as president. Of the 64%, 14% (9% of all voters) say the abuses are not serious enough to warrant impeachment, 33% (21% of all voters) say the abuses rise to the level of impeachable offenses, but he should not be impeached, and 53% (34% of all voters) say the abuses rise to the level of impeachable offenses and Mr. Bush should be impeached and removed from office.

The respondents didn’t specify whether they were specifically referring to the administration’s policy on torture. They didn’t say if they were talking about how they cherry-picked intelligence to justify a wrong-headed war, or how they compromised national security by outing a covert CIA operative, merely as retribution for her husband calling them on their lies. The respondents may not have been specifically responding to warrantless wiretapping and secret military tribunals. They may have simply been thinking of how the administration handed over all government regulation to the industries being regulated. The data doesn’t say. All they were asked was if President Bush abused his power, and 64% said he did. The data also doesn’t show what the other 36% were thinking.

When you look at the data, though, something else is striking.

I’m surprised, though I guess I shouldn’t be, that so few people gave Response 2. Imagine a graph of this data. Usually a distribution like this would slope up, slope down, or rise in the middle like a bell curve. That this data set has such a sharp dip in the middle is a testament to just how polarizing this president has been. 64% of Republicans feel that President Bush has not abused his powers as president at all, while 50% of Democrats feel he should be impeached for it.

Also, more than one-fifth of respondents in general felt that his abuses had risen to the level of an impeachable offense, but that he shouldn’t be impeached. Isn’t that being soft on crime? Or perhaps we just remember the last time an opposition Congress impeached a sitting president, and are unwilling to go through all of that again, even if it’s warranted this time.

Because for 36% of the population, warrants are sooooo 20th century.

Ro has a thought-provoking post about the relationship between learning something and knowing it. Before I address that question, it might be worth taking a moment to consider what it means to know something.

What do we mean when we say we know something? For the individual, it might be the same as saying we unequivocally believe it. But is that enough? If Iago believes his wife has been unfaithful, and he has no evidence to support his belief, does that count as knowledge? Probably not.

Socrates argued that a belief must be justified to be considered knowledge. Othello might say that he knows his wife Desdemona has been faithful, because he has reason to believe in her love and trustworthiness. His belief is justified. But that doesn’t necessarily make it true, and so that probably doesn’t count as knowledge either. Knowledge must be both true and justified.

When we say someone else knows something, that might mean that they believe it and we believe it too. If Iago uses manufactured evidence to manipulate Othello into believing that Desdemona has been having an affair with Cassio, Othello can say that he knows that Desdemona has been unfaithful, because his belief is justified by evidence that has been presented to him. But we would not say that Othello knows it. He still believes it, but we do not.

Which brings us to the Gettier problem. Imagine that while Othello is being manipulated by Iago, Desdemona has been secretly having an affair with the Duke. Othello makes the statement that he knows Desdemona has been unfaithful. Does he know it? This time, his belief is both true and justified. And yet Gettier would not count this as knowledge, because Othello’s belief, while true and justified, is based on false evidence. He has no knowledge of the actual affair. Robert Nozick would point out that if the statement weren’t true, Othello would still believe it.

Now let’s go back and look at the question originally posed by Ro, which has to do with the relationship between knowledge and learning. If I say I learned something, that means I know it, which means I believe it. If I say you learned something, that means you believe it and I believe it. For example, President Bush got into a bit of trouble for including the following in the 2003 State of the Union address:

The British government has learned that Saddam Hussein recently sought significant quantities of uranium from Africa.

By citing the British government, Bush’s speechwriters sought to insulate the administration from claims they already knew were false. But by using the word “learned” they implied the word “knew” which means that Bush was essentially saying that he also believed that the statement was true. It was later discovered that the statement was not true, and that the Bush administration was aware it was not true at the time the speech was written. Saying “The British government has learned” did not provide the out they were hoping it would.

Ro’s other question was whether knowing something implies that one has learned it. A strict empiricist might say yes, but even John Locke allowed for some a priori knowledge gained through reason alone. The classic example is from René Descartes: Cogito ergo sum. I think, therefore I am. Is this knowledge? Was it learned?

Finally, I can also attest that it is possible to have learned something and not know it. I demonstrate this condition several times every day.

In a poll taken over a decade ago, 96% of Canadians said they preferred their health care system to ours.

A more recent poll indicates that 64% of Americans think “the government should provide a national health insurance program for all Americans, even if this would require higher taxes”.

Michael Moore’s film Sicko is the fourth highest grossing documentary of all time.

And millions of Americans have no health insurance at all.

What specifically is it going to take to get Universal Health Care in this country?

I caught the Republican debate this morning.  Bush and Cheney were praised for keeping us safe for the last six years. 

Actually, for the past six years, an average of over 500 Americans have died each year on American soil in 9/11 terrorist attacks.

Think about it.

The Center on Education Policy released a disturbing new study this week, measuring the effects of No Child Left Behind:

The report finds that approximately 62% of school districts increased the amount of time spent in elementary schools on English language arts and or math, while 44% of districts cut time on science, social studies, art and music, physical education, lunch or recess.

Now, I’m pretty much appalled by all of the cutbacks, but I’ll leave the bulk of it to ScienceTeacher.com, SocialStudiesTeacher.com, and LunchTeacher.com. I’m ShakespeareTeacher.com, so I want to talk about arts education.

(And let’s make no mistake - the extra time being spent on ELA isn’t being spent on literature. It’s being spent on test prep, and more test prep.)

Arts education is absolutely essential for students preparing for the world that we’re currently living in. With the image continuing to gain dominance over the written word, people who can demonstrate artistic ability are highly marketable in today’s economy. From graphic designers to documentary filmmakers, those who can master today’s tools of communication are able to command a wider audience and expand their range of communication. In the connected world, this is real currency.

And even if all of that weren’t true, the arts teach us how to identify problems and sovle them with creativity and discipline. Those skills help us in any endeavor.

I came across a website for an artist named Jen Stark, who creates sculptures from construction paper that won’t help anyone pass a reading test any time soon. But they bring beauty into the world, which is worth at least a link from my blog. Take a look at her work, and tell me she didn’t have to develop some pretty sophisticated math skills along the way.

Or take French artist Huber Duprat, who recruited caddis fly larvae, who typically create protective shells out of silk and their surrounding materials, and placed them in an environment of gold flakes and precious gems. The result is a combination of art and science that boggles the mind. Click the picture below to see the video.

Or take a look at the Universcale by Nikon, an application of the mathematics of scale to allow human comprehension of the natural universe, and tell me your appreciation of it isn’t primarily aesthetic.

I wonder what Leonardo DaVinci would have thought about eliminating arts education to teach math. What would Shakespeare have thought about eliminating arts education to teach literacy? What would Descartes say about eliminating science to teach math? What would Hemmingway think of eliminating social studies to teach literacy?

Reading and math are important skills. But even if an educational system were somehow able to acheive 100 percent literacy and numeracy, and nothing else, it would still be a failure.

I often like to come up with games of chance. There have been times in my life when this has been profitable, but mostly I’m just interested in questions of statistics and probability.

I had considered the math behind putting together my own Deal or No Deal style game, but with greatly reduced suitcase amounts and with a cost to play. Determining a fair cost (one which I would agree to if I were the player or the banker) at first seems like a hopelessly difficult problem, but the math is actually quite simple. The player has the option of keeping the initial suitcase until the end, and the banker has the option of offering whatever small amount he wants. At any given time the chosen suitcase is worth the average of all unopened cases. The banker certainly isn’t going to offer more, and if the player accepts less it’s just because he’s hedging his bets. The cost to play should be the average of all of the cases, whatever they may be.

A couple of months ago, while discussing the Two Envelopes problem, we briefly discussed what’s known as the Monty Hall problem, after the host of Let’s Make A Deal. Thinking of that problem has inspired another gambling proposition which is this week’s Conundrum.

Let’s continue to call our two gamblers the banker and the player. The banker has three boxes and hides a $10 bill in one of the boxes and a $1 bill in each of the other two. The player pays a set amount to the banker and chooses one of the three boxes. The banker must then open one of the other two boxes and show the player a $1 bill. Then the player can decide whether to keep the contents of the box he chose or switch to the other unopened box.

What would be the fair amount for the player to pay the banker to play this game?

UPDATE: Question solved by David. See comments for the answer.

How do they calculate the digits of pi?

I mean, they’ve calculated the number out to billions of places. When they get a billion digits out, how do they know they’re right? Just think about how incredibly precise that is. A quark’s diameter can be described in 18 decimal places, so surely a billion places is far beyond the realm of any practical scientific purpose or authentic human experience.

From a purely mathematical standpoint, pi is defined as the ratio between a circle’s circumference and its diameter. But the only way we have of measuring such things mathematically is by using pi.

Wikipedia has this article on the subject, but I doubt you’ll be suprised when I tell you it is not helpful to me. We could ask Daniel Tammet but he’d probably just tell us what the algorithm tastes like.

Anyway, if all this math stuff is boring to you, check out this discussion thread putting a more philosophical spin on the digits of pi:

“Somewhere inside the digits of pi is a representation for all of us — the atomic coordinates of all our atoms, our genetic code, all our thoughts, all our memories. Given this fact, all of us are alive, and hopefully happy, in pi. Pi makes us live forever. We all lead virtual lives in pi. We are immortal.” - Cliff Pickover

This means that we exist in pi, as if in a Matrix. This means that romance is never dead. Somewhere you are running through fields of wheat, holding hands with someone you love, as the sun sets — all in the digits of pi. You are happy. You will live forever.

Silly, perhaps, but technically true. And somewhere in the digits of pi, there’s a version of the Shakespeare Teacher who understands how they calculate the digits of pi.

When I first started this blog, one of my very first posts suggested that almost all of the current natives of Mongolia and China were probably descendants of Genghis Khan. I literally had no readers at the time - I hadn’t yet told anyone about the blog - and so there was nobody to challenge my sweeping statement. I didn’t even make an argument. I’d like to give my argument now, and reopen the question as a Conundrum.

The idea was based on a National Geographic article about the biological legacy of Genghis Khan:

An international group of geneticists studying Y-chromosome data have found that nearly 8 percent of the men living in the region of the former Mongol empire carry y-chromosomes that are nearly identical. That translates to 0.5 percent of the male population in the world, or roughly 16 million descendants living today.

I went on to note:

16 million descendants. And that’s only men descended from Khan directly through the male line, father to son, for the past 800 years. The total number of Khan’s descendants living today is truly incalculable.

If you figure an average of four generations per century, that’s 32 generations between Genghis and his living descendants. Each person living today should have around 2 to the power of 32, or roughly 4.3 billion, living ancestors that are contemporary with Khan. Obviously, many individuals will have to be counted more than once, so let’s take a different tack.

Let’s pick a year somewhere between 1200 and 2000, say 1500. The total population of mainland Asia in 1500 was 268,400,000. Each living person today would have approximately 2 to the power of 20, or about a million, ancestors who were around in 1500 (and that’s if we don’t count anyone with a living parent).

So how many of the 268,400,000 around in 1500 were Khan’s descendants? Well, there are 16 million men living today that share the Y chomosome. If Khan and his direct male heirs had an average of 1.68 sons over 32 generations, that would give us our 16 million. That would only account for 505 men carrying that Y chromosome in 1500. But that calcuation leaves out two factors.

First, by 1500, Khan’s seed had been pretty well spread. The factors that account for his prevalence today came mostly into play during Khan’s life and the few generations following (see the article for details). So the distribution was a lot more top-heavy than the calculation above would suggest.

Second, we’re only counting direct male-line heirs. Passing a Y chromosome down from father to son over 32 generations is only one of 4.3 billion different permutations of inheritance. Each of those 16 million Y chromosome carriers alive today probably has an average of at least one sister or daughter. That doubles the known descendants right there. Extend that back over 32 generations, then consider all of their descendants, and you get the idea. If we change “average of 1.68 sons over 32 generations” (which we know is true) to “average of 2 children of either sex over 32 generations” (which doesn’t seem like too great of a leap from there), then 16 million becomes 4.3 billion, greater than the population of mainland Asia today.

It seems to me that today’s ethnic Mongolians and Chinese would almost all have to be descended from Khan, some many times over.

Now I am no math expert. I’m a Shakespeare Teacher. It’s very possible I could be wrong about this. I’d be interested to hear what other people think, particularly people with more professional experience with statistical analysis.

And I should also point out that I pin no political, moral, or judgmental significance to being a descendant of Genghis Khan. This is simply a math, history, and logistical Conundrum. I truly hope no offense is taken (though if you read my original post and the Economist article it is based on, it actually seems to be a point of pride for both Mongolia and China to be the descendants of Khan). And my family comes from Belarus, so this would mean I’m probably a descendant of Khan as well. So don’t screw with me.

Now, with all that in mind, for this week’s Conundrum, I hereby submit my original conclusion up for public scrutiny:

So, China and Mongolia should probably stop arguing over which of their people are the true heirs of Genghis Khan. My guess is, almost all of them are.

In a Venn Diagram puzzle, there are three overlapping circles, marked A, B, and C. Each circle has a different rule about who or what can go inside. The challenge is to guess the rule for each circle. You can find a more detailed explanation of Venn Diagram puzzles, along with an example, here.

You’ve told me that there’s not enough math on this site, and I have listened. Each of the eight items below is a number.

Have you figured out one of the rules? Two? All three? Feel free to post whatever you’ve got in the comments below. Just tell us which circle you’re solving, and what the rule is.

Enjoy!

UPDATE: Circles B and C solved by Kenneth W. Davis. See comments for all answers.