The site itself recommends squirt guns, but I disagree that they "upgrade well". They are useful in the early stages of the game in their weak forms, but they don't do well against dark creeps, since these are immune to weak attacks, and the squirt gun is the weakest. However, their final two upgrades significantly improve them, and make them formidable.

Anti-air are also important, since air creeps ignore your tower and just fly through, and the anti-air towers hit four at once. Their last upgrade is very expensive (over 300 gold), so I usually think it is better to have multiple less than fully upgraded anti-air towers than one fully upgraded one.

Finally, you can find inspiration from YouTube videos (just search for "desktop tower defense"), and having a look at other player's maps.

After days of brute forcing (I used one of the slow computers), I found that the 11x11 version of the Cat Noir game is doable if no squares are marked at the beginning.

Since I don't have the source code that the actual Chat Noir game uses, I had to guess. However, the solution should be equivalent to some strategy in the actual game. (For instance, my cat will always move to the upper-left, then upper-right, etc., if given a choice.)

Edited with fancy JavaScript. Here is what goes on. Click on the display to iterate through.

Basically, it involves cutting off the cat at just the right times, and buying extra time.

I am still pretty sure that the board with one or more blocks already marked may not be winnable. For example, consider:

X . . . . . . . . . .
 X . . . . . . . . . .
X . . . . . . . . . .
 X . . . . . . . . . .
X . . . . . . . . . .
 X . . . . C . . . . .
X X X X X X X X X . .
 X X X X X X X X X . .
X X X X X X X X X . .
 X X X X X X X X . . .
X X X X X X X X . . .

This one is still solvable, I believe, but this just goes to show that the blocks being there can work against you just as well as for you.

There has been a lot of hubbub about shuffling algorithms the past few weeks. This post on Coding Horror is one of my favorites. He does not list my own naïve sorting mechanism, which does not use any swapping (written in Ruby):

src = [1,2,3,4,5]
dest = []
while src.length > 0 do
	dest += [src.delete_at(rand(src.length))]
end

Swapping just irritates me. Regardless, this seems to have nearly identical randomness as the Knuth/Fisher-Yates, Shuffle (in that it generates exactly as many permutations as there can be), shown here:

src = [1,2,3,4,5]
(src.length-1).downto(0) { |i|
	n = rand(i+1)
	src[i],src[n] = src[n],src[i]
}

Some quick test runs have verified to my liking that both my algorithm and KFY produce about the same levels of randomness of shuffles. KFY just modifies the array in place, while mine does so in a copy. I don't immediately see that KFY works (though it does), while my algorithm makes a little more intuitive sense to me.

In general, computer shuffles are notoriously difficult to get correct. One major problem stems from the fact that, for a deck of 52 cards, you have 52! = 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000 different ways of arranging the cards. That's a big number. A standard random number generator has only about 32-bits of precision, for a maximum of 4,294,967,296 different shuffles it can produce.

There's a huge difference in those two numbers. According to my back-of-the-envelope calculations, you need at least a 226-bit random number generator to hit all of the 52! permutations of a deck. But then you run into a problem, as illustrated in the article cited above: unless you hit is *just* right, you may be favoritizing some shuffles more than others.

It's also really hard to notice that you are doing it, too. Once you have a deck of 13 cards, the number of permutations exceeds 6 billion, meaning merely storing counts becomes nearly impossible, let alone the computation time to generate these counts to a statistically meaningful amount.

The best thing you can do is to use a very large, very good random number generator, preferably with real random numbers. Barring that, follow guidance set for by Knuth (and other brilliant folks, too) when designing your hardcore shuffling algorithms.

Thanks to my friend Marissa, I have been mucking around with a game called Chat Noir for the past few days.

A quick run-down. We have an 11x11 grid, and the cat starts in the middle. You move first by blacking out one of the hexes, and the cat goes second (and so on). The cat cannot move onto black squares. Some squares start as black already. The goal is to prevent the cat from "escaping" the grid or, equivalently, getting to an edge hex. The cat always moves towards the closest piece of edge.

Is it always possible to capture the cat? My initial guess was "no", and then it turned into a "maybe". I am still not 100% sure.

I have two methods I am going to try now: I am going to try to solve the empty case (with no black squares at the beginning) and try to capture the cat. Either by finding the optimal strategy, or by having a computer prove it is possible. The beauty of this is that the cat's strategy is always known, so it makes the problem simpler.

However, in the general case, it is not necessarily true that a solution in the empty case will extend to the general case.

I am in the middle of coding up some simple strategies and enumerations of the game, and will report on my results in a few days. In that, it may take several days for some of them to run.

There is an option in Twilight Imperium 3rd Edition: you can take fighters, which are throwaway units, and have them do a "trench run" on a "war sun" (à la Star Wars). At first glance, this might be a good idea, as fighters are dirt cheap and not very powerful, while war suns are the most expensive and destructive ships. So, how good or bad of an idea is it really?

The rules state that you roll a 10-sided die for each of the fighters making the run: on a 9 or 10, they live through the first barrage. The fighters that live must then roll the die again, getting a perfect 10. This math is easy to do: you have a 2%, or 1/50, chance of killing it. Therefore you must have 50 fighters to get guaranteed destruction, right?

Nope. And with dice, there's no such thing as "guaranteed" anything. The best we can hope for is to be more than likely able to defeat that War Sun.

To start this calculation, we think about how likely it is that the war sun survives a single attack? We know from above that this is 49/50, or 0.98. Well, how likely is it to survive after two attacks? Take 0.98 × 0.98 = 0.9604. After three attacks? 0.98³ = 0.941192.

We want to know when we will have a better than half chance, i.e., 0.50. So we solve the following equation:

Using some elementary algebra and logarithms, the answer will be log(0.50) / log(0.98) = 34.309, or about 35 fighters.

While 35 is better than 50, that's still an awful lot of fighters. Fighters, by default, hit on 9's and 10's, so a fleet of 35 of them would do about 7 damage, which is no number to sneeze at: it would take down many moderate sized enemy fleets on the first barrage, and it would be unlikely that the enemy could do 35 damage every turn, so the fighters would just keep nailing the other player.

Unless you have just a handful of fighters and not a lot else anywhere, a trench run ain't such a good idea. And if someone wants to attack your War Sun with less than 35 fighters, let them. Even with a more normal and strong-sized fleet of 10 fighters, a War Sun has an 81.7% chance of survival, and will be guaranteed to kill 80% of the attacking fighters.

Scrabble is a simple, popular game of word construction, played on a 15x15 board. A question I have always had is, what is the best word that can be played?

According to my dictionary, "objectivization" is the most valuable word, for 38 points (all 15 letters across or down). It is only playable in no less than three turns: "ion", "object", and then "ivizat". Or if several of the letters are already set up, and someone plays across them.

If we limit this to eight-letter words (which are the kind found in the The Official Scrabble Players Dictionary), then we have "highjack" for 28 points, beating the famous "quixotic", which has a raw score of only 26. However, "quixotic" has several very high-point letters, which might be used on various doubling and tripling squares. If we take these squares into account, what do we get?

The most valuable squares are, of course, playing along the sides of the board, with triple word and double letter scores. If we optimize the placement of the letters, we can get the following scores for up to fifteen-letter words:

Well, the first couple of words are probably not playable (since they might be proper nouns). But there are definitely some 1000-point words. And all of them are theoretically playable for that score, assuming that the row or column has a lot of the letters filled in, and someone plays across them.

If we limit this to words that eight letters long, we get the following:

The top two are, in fact, in the Scrabble Player's dictionary. The long-standing favorite, "quixotic", is sadly several entries down.

Stay tuned for more on Scrabble.