Claude Shannon on Chess

KnightClaude Shannon’s paper Programming a computer to play chess from 1950. Good stuff from the history of computer science.

Technorati Tags: ,

Addendum: A terrific collection of computer chess links.

Addendum2: An equally famous paper was Arthur Samuel’s 1959 publication on writing a Checkers program. Unlike Shannon’s work, Samuel was interested in creating a checkers program which learned how to play the game automatically. While it was never really very strong, Samuel’s work was highly influential in the field of machine learning.

Morning Baseball Learnin’…

I was bored with the scouting reports on XM this morning, so I surfed over to channel 200 where Bob Dylan was playing music with a baseball theme. One of the songs that he played was Teddy Reynolds singing “Strike one”, which is all about pitcher Don Newcombe. I wasn’t paying too much attention, and I had only the vaguest recollection of who Don Newcombe was, so I decided to do a little bit of research to educate myself. It turns out that Don was a pretty interesting guy. He first played for the Newark Eagles in the Negro Leagues, and then came up through the Nashua Dodgers (a racially integrated team) in the old New England League before joining the Brooklyn Dodgers in 1949. In his rookie year, he had 17 wins with 5 shutouts, and pitched a string of 32 scoreless innings. He is the only player to win Rookie of the Year, the Cy Young, and MVP (he won the MVP and the Cy Young in 1956). In 1957 he posted a record of 27-7, with an ERA 3.06 with 18 complete games. His Wikipedia bio has some cool facts: he was apparently a good enough hitter that he was used as a pinch hitter, he once stole home (the only NL pitcher in the 1950s to do so, despite only having two career steals), and he hit two homeruns in a game three different times. He’s apparrently now 80 some odd years old, and still in the Dodgers organization.

Hats off, Don!

2007 Veterans Committee Profile: Don Newcombe
Wikipedia’s Don Newcombe page

Technorati Tags:

92 ways to place 8 queens on a chessboard…

such that no queen attacks any other queen. It’s a simple (really simple) program to write, but I can’t remember having done it. So I did it. And then I had to make a picture of one of the solutions.

8 queens on the chessboard

Technorati Tags: , , ,

Addendum: Wikipedia has a page on the puzzle, naturally. This kind of program would be a good one to test out Knuth’s “Dancing Links” idea. I might have to do that.

Addendum2: I swiped the chess font and methodology from this website, keeping with my long tradition of drawing stuff on my website using PostScript.

Addendum3: I made a different picture using the Adobe Cheq font:

8 Queens using Adobe Cheq font

The Debate On Net Neutrality by Hsing Kenneth Cheng et. al…

A few weeks ago, I remember this research getting a bit of press, but I didn’t have the time to track down the link to the actual report, rather than reading the rather unhelpful press summaries of the work.

Here’s a link to the PDF.

Their game theoretic model showed that the likely result of the abandonment of net neutrality by ISPs would be the decrease of bandwidth to consumers and a stifling of innovation. I thought the result was unsurprising, but also wanted to look at the details of their model. My initial skimming of the first few pages of this paper indicates that the previous synopsys (gleaned mostly from popular reports of the work) may not be entirely accurate. I’ll try again after I read some more.

Technorati Tags:

Why is it so hard to find a file with the MLB schedule in it?

Baseball ScheduleShame on you Major League Baseball. I was hoping to find a file that contained the date and times for all the major league games that would occur in the 2007 season. It turns out that they make it damned difficult to actually get a complete and accurate schedule. Sure, if you are interested in a single team, you can surf to their official site, click on a link which indicates some variant of “Downloadable Schedule”, and get a comma-separated-values file that contains your teams games in it. Unless your the Yankees. Apparently the Yankees don’t care enough to actually supply one. Or the Pirates, who supply a link, but it’s broken. Or Atlanta, who alone of all the teams chooses to make their schedule only available in the form of an Excel spreadsheet.

Sigh.

But this didn’t deter me. I snarfed, I scraped, I spidered, and in the end, I prevailed. Here’s my resulting calendar file for the 2007 season. All the times are listed in PST/PDT, rather than the more common Eastern Time, but let’s face it, it’s for me and I live on the West Coast. If you don’t care for it, you could probably write a script to fix it, or you could wait a few days and maybe I produce a nicer, more generic CSV file for your consumption.

Technorati Tags:

Addendum: Oops.  I got the home/away reversed on the list.  I’ve fixed it on the copy linked above.  It should be better now.

Calendar File for Athletics Games

I know it is incredibly gauche to still use ancient Unix utilities like calendar(1) to keep track of things, but then, I am incredibly gauche. I converted the .csv version of the Athletics schedule into a calendar file: you can download it here if you like. Just add a line to your .login script that runs calendar after adding these to your ~/calendar file, and you can keep up to date on Athletics games.

Technorati Tags: ,

Popular Works involving Mathematics

As you can tell, I’m on a bit of a mathematics bender lately. While digging around for new material, I found this rather nice bibliography of books that might be fun for the math enthusiast (there must be one or two of you out there). I have some of the books and like them, so I’m tempted to track down some of the others. In any case, enjoy:

Popular Works (Math Lite Collection)

Technorati Tags:

The Angel Problem has been Solved! (Maybe)

Over at Neighborhood of Infinity, there’s a mention that the Angels and Devil game might have been solved. Don’t know what it is? It’s a game played on an infinite checkboard. The Angel begins at the origin, and can move to any square that can be reached in k moves of a chess king. The Devil can then destroy a square anywhere. The Angel wins if he can evade the Devil. The Devil wins if he can box in the Angel. The game was proposed by Conway, and has up until now remained unknown as to whether there was a reasonable strategy for the Angel.

I haven’t read them over in any detail, but it’s the kind of neat recreational math stuff I like.

A Neighborhood of Infinity: The Angel Problem has been Solved! (Maybe)

Technorati Tags: ,

2, 23, 2357, …

If you take the sequence of primes, and concatenate the first n of them together, how many of these are prime? It’s not hard to see that 2, 23, and even 2357 is prime. The next term has 355 digits:

235711131719232931374143475359616771737983899710110\
310710911312713113713914915115716316717317918119119\
319719921122322722923323924125125726326927127728128\
329330731131331733133734734935335936737337938338939\
740140941942143143343944344945746146346747948749149\
950350952152354154755756356957157758759359960160761\
3617619631641643647653659661673677683691701709719

The concatenation of primes up until 1033 also appears to be prime.

The On-Line Encyclopedia of Integer Sequences has this sequence as well.

Technorati Tags: ,

357686312646216567629137 is a prime number

Big deal you say? Strike the initial 3 off. The remaining number is also prime. Continue striking them off, one at a time. All the remaining numbers are also prime. The number above is the largest of the “left-truncatable primes”, of which there are precisely 4260. How do I know? I wrote a program to find them (took only about 10 minutes in Python) and you can verify them on this webpage. This sequence is also A024785 in the Online Encyclopedia of Integer Sequences. You can also generate the list of right-truncatable primes (where each prefix is prime). There are only 83 of those, with the largest number being 73939133.

Technorati Tags: , ,

Pet Food Recall

Apparently a pretty serious pet food recall is underway. I caught this on the news, and since I’m such a softie for the well being of pets, I thought I’d give some more information here (it was difficult to find on my local tv news channel news website). Apparently wet and pouch style cat and dog food manufactured by menufoods.com can cause kidney failure. Menufoods is a supplier to many other pet food suppliers, even fairly upscale ones like Iams, so if you have any questions, you should check out the Menufoods website to see if you could have any food which might be affected.

Luckily, I’ve always fed Scrappy dry cat food.

Menu Foods Income Fund – Annual General Meeting

Technorati Tags: ,

Thinking about sex…agesimal numbers

Ever wonder why our clocks divide hours into sixty minutes of sixty seconds? What’s up with the sixty? I mean, factors of five and ten make some sense, but why sixty? Well, as it turns out, these things have some nifty properties because sixty has so many small factors. 60 = 2 * 3 * 2 * 5. Let’s look at the set of numbers which only have prime factors which are in the set {2, 3, 5}. What do they look like? Well… The first 30 are

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18,
20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50,
54, 60, 64, 72, 75, 80

You could get more terms from the Encyclopedia of Integer Sequences if you are too lazy to compute them yourself.

Let’s say that we have a number which we want to divide by a number in this list, say 75. 75 is 3*5*5. Let’s search (it isn’t hard) for a number 60k where 60k is divisible by 75. Well, that’s simple enough, 602 is 48 * 75. How does this relate back to division? Let’s say we want to divide 189 by 75. If we did the math normally, we’d get 2.52. But the Babylonians expressed fractions in sexagesimal notation: meaning that instead of having decimal digits, they had units, 1/60ths, 1/3600ths, and so on. We will write such numbers beginning with the units digits, and colons separating the remainders. A few seconds (minutes if you are rusty) of work on converting the number to radix 60 would tell you that the answer is 2:31:12. But let’s use what we learned above. instead of dividing by 75, let’s multiply by 48 instead. 48 * 189 = 9072. Let’s write this out as powers of 60. 9072 = 2 * 3600 + 31 * 60 + 12. Interesting! By multiplying by 48 and then shifting two sexegesimal digits, we can effect division: in short, we’ve discovered reciprocals. Because all these “regular” numbers have short reciprocals in base sixty, it’s actually rather convenient to use them to multiply and divide. Neat. The Babylonians apparently had good tables of these numbers.

It’s not hard to figure out that if a number x is regular, then its “reciprocal” must also be regular. (If a number is regular, it consists entirely of factors 2, 3, and 5 to some power. The sequence of powers 600, 601, 602… obviously generates arbitrarilly large numbers of these factors, and by dividing out, we are obviously left with 2, 3, and 5 being the only possible prime factors.) So we could just have easily divided by 48 by multiplying by 75 and then shifting by two sexagesimal digits.

It’s an interesting programming problem to find a short program to generate the list of all the numbers which are “regular”, which have only factors of 2, 3, and 5. If you have a lazy functional language which supports proper tail recursion, you can use streams to write a simple but interesting program to do it. I didn’t have either handy, but I did have Python handy. The analogous version didn’t work out too well at generating large numbers of terms, mainly because Python simply doesn’t do proper tail recursion, but in 20 minutes of tinkering with Python managed to hit on a method that worked pretty well using heaps. It took my AMD64 about 15 seconds to generate the first million terms, the millionth of which is 84 digits long.

Regular number – Wikipedia, the free encyclopedia

Addendum: Here’s the python code to generate these regular numbers (I retimed it, and it actually takes 18 seconds on my machine):

#!/usr/bin/env python

from sets import Set
from heapq import heappush, heappop

heap = []
heapset = Set([])

heappush(heap, 1)
heapset.add(1)

for x in range(1000000):
        val = heappop(heap)
        heapset.remove(val)
        print val
        if 2*val not in heapset:
                heappush(heap, 2*val)
                heapset.add(2*val)
        if 3*val not in heapset:
                heappush(heap, 3*val)
                heapset.add(3*val)
        if 5*val not in heapset:
                heappush(heap, 5*val)
                heapset.add(5*val)

Addendum2: A slightly modified version of this code can be used to verify that there 35,084 4-smooth numbers less than 10100, which is the first part of problem 1.68 in Crandall and Pomerance’s Prime Numbers: A Computational Perspective.

Technorati Tags: , ,

Hypermiling: Extreme Fuel Conservation by Unorthodox Driving

We’d all like to get better gas mileage from our cars. Well, me especially. My Ford Expedition isn’t exactly the cheapest car to put on the road. But so-called “hypermilers” take this to the extreme by adopting a number of techniques to reduce fuel consumption: such as drafting trucks with the engine off, or taking slow curves at high speed to retain momentum. I’m simultaneously horrified and amazed. Check out the cool article on Mother Jones.

This Guy Can Get 59 MPG in a Plain Old Accord. Beat That, Punk