Chess, Thinking, Seeing, Jaggies and Chess... Again
I'd like to pay homage to James Burke and his inspiring PBS show Connections by taking you on my own short journey of connected ideas.
The timeless game of chess has long been a grand challenge for artificial intelligence, with the number of possible games being much greater than the number of atoms in the universe. Baron Wolfgang von Kempelen captured imaginations in 1769 with his famous chess-playing automaton hoax, The Turk, which actually hid a human chess master inside the wooden box.1 Much more recently IBM's Deep Blue bested human intelligence with AI and immense computational power.
Seeking to peer inside the box of modern day chess automatons, Martin Wattenberg, PhD , at IBM and his artist/architect collaborator Marek Walczak created Thinking Machine 4, 2 which "explores the invisible, elusive nature of thought" with online interactive visualizations that allow the user to play chess against the computer and see a representation of the computer's evolving "thought process". Seeing the chess board through the computer's eyes evokes recent work on seeing objects through a computational model of human eyes.
In a recent paper,3 Michael Deering shows examples of images as perceived by a computer model of a retina. The model itself consists of a hexagonal lattice of retinal cones with irregularities in the pattern. Deering refers back to some classic but non-intuitive work in computer graphics by Robert Cook4 at Pixar demonstrating the advantages of irregular patterns of sampling over regular patterns.
Cook showed how to use "jittered" sampling to sneak around the famous Nyquist theorem that says that signals need to be sampled at twice the highest frequency component in the signal to avoid aliasing artifacts, referred to as "jaggies" in computer graphics. Samples from ray tracing are randomly "jittered" away from a regular grid allowing one to trade off visually distracting aliasing for more acceptable noise.
This brings to mind a related form of sampling that is often used for efficient multidimensional sampling,5 called Latin hypercube sampling, which is also used to avoid the "clumpiness" of uniform random sampling. To efficiently distribute N samples in a multidimensional space, each coordinate dimension is subdivided into N segments and each segment contains only one sample. Put more succinctly, it is the multidimensional version of the N-rooks problem in chess where one must place N rooks on an NxN chessboard so that none can attack another vertically or horizontally.
And that, as they say, brings us full circle, back to that classic game of kings, chess.
1 Mueller, T Your Move: How computer chess programs are changing the game, The New Yorker Dec. 12, 2005 p. 62,
3 Deering, MF A Photon Accurate Model of the Human Eye, ACM Transactions on Graphics 24(3):649-58.
4 Cook, R Stochastic Sampling in Computer Graphics, ACM Transactions on Graphics 5(1):51-72.