A Game of Logic

I've been thinking about a game which I haven't named yet. The rules are simple. The playing board is a logical expression built from the binary connectives 'and' and 'or', the logical constants 'true' and 'false', and atoms 'A', 'B', 'C', ... For example (A and B) or C. To make things easier I'll use abuttal for 'and' and + for 'or'. The previous example is just AB+C.

There are two players, False and True, who take turns. A legal move for False consists of replacing all occurences of one atom with 'false' and you can guess what True's moves are. True wins if the expression evaluates to 'true' with the obvious interpretation of the symbols I've given and False wins if the expression evaluates to false. There is no possibility of a tie.

For example consider the game (A+B)(C+D)(E+F). This is a win for True whoever plays next. Any time False sets an atom to 'false' True merely has to set the other atom in the same factor to 'true' making the factor 'true'. Eventually all of the factors will have the value 'true'.

So here are some questions:

1. Has this game already been studied? If so, what's it called?
   
2. Is there a nice way to evaluate any position in the game? A partial answer is given by some papers by Anshelevich on the subject of Hex. All Hex positions are positions in this game and many interesting Hex positions and subproblems can be approximated well by simple positions in this game. (Note that a good strategy for this game might not be a good strategy for Hex because a Hex game corresponds to a very large expression.)
   
3. Can you assign Conway numbers to positions in this game? What is the value of 'true'?
   
4. What happens if you allow the unary operator 'not' and allow the two players to replace an atom with either 'true' or 'false'.
   
5. What other games, besides Hex, are special cases of this game? (All combinatorial games I guess.) What games are special cases in an interesting way?
   

Opinion: A Farewell to Angles

This story was on Slashdot recently. While the guy might be seen as a bit of a crackpot I'm coming round to his point of view. As a worker in the field of computer graphics I'm frequently faced with software that performs operations like finding the angle, theta, between two normalised vectors, by computing the inverse cosine of the dot product. And yet later down in the code the angle is used only as the argument to further trig functions. Trig functions are expensive to compute. If you know the cosine and the quadrant of an angle then you immediately also know the value of all of the angle's other trig functions by some elementary computations involving the four elementary operations and square roots. These are far cheaper to compute than trig functions. And yet programmers frequently insist on working with the angles themselves because they are familiar with them.

As an extreme example: I recently optimised a block of someone else's code in which a point (x,y) was rotated through an angle π around (0,0) by converting it to polar coordinates, adding π to the angle and then converting back to rectangular coordinates! (Incidentally, this block of code was hard-coded for this one particular rotation, and there were similar blocks of code for π/2 and -π/2 rotations.)

It seems to me that people learning computer graphics need to learn that there are many operations that can be performed without using angles. There needn't be a reflex action to convert any dot product to an angle. Converting to an angle this way may also have unfortunate numerical inaccuracies, especially when the angles are converted back to trig functions again later in the code. Maybe I'll put together a document with a list of things you can compute given the sines, cosines and tangents of angles without having to evaluate a single trig function.

The issue is that the word 'angle' has two meanings. One sense of the word 'angle' is a set of equivalence classes of intersections between two lines. The pair of intersecting lines (A,B) and the pair (C,D) are said to be equivalent if there is a rigid motion of space that transforms A to C and B to D. There are a number of easily computed invariants we can associate with these classes, but the most popular one is called 'the angle' and is often horrible to compute as it typically requires the use of transcendental functions. Unfortunately, as soon as people think 'angle' they also think 'the angle' and are led to use these functions unnecessarily. (It's worse than this, 'the angle' properly lives on S¹ but people work with the cover of S¹, R, leading to troublesome ambiguities.) It seems to me that other invariants besides 'the angle' ought also to be taught. And that is what this book seeks to do, despite its crackpot trappings.

Quadratic Residues and Acoustics

Here are some articles on quadratic residue diffusors to improve sound quality in your home. And an old classic: golden section stranding.

I hear that numerology can also be used to tell your fortune.