Posts Tagged ‘chess’

image-jpg-crop-promo-large2

By Ella Morton

The 1770s.

At the dawn of that decade, an inventor by the name of Wolfgang von Kempelen debuted his latest creation in Vienna: A chess-playingautomaton made for Habsburg Archduchess Maria Theresa. Known initially as the Automaton Chess Player and later as the Mechanical Turk—or just the Turk—the machine consisted of a mechanical man dressed in robes and a turban who sat at a wooden cabinet that was overlaid with a chessboard. The Turk was designed to play chess against any opponent game enough to challenge him.

At the Viennese court in 1770, Von Kempelen began his demonstration of The Turk’s workings by opening the doors and drawers of the cabinet and shining a candle inside each section. Inside were cogs, gears, and other clockwork. After closing the cabinet, von Kempelen invited a volunteer to serve as the Turk’s opponent.

Gameplay began with the Turk moving his head from side to side to survey the board before appearing to decide on the first move. His left arm then jerked forward, the fingers splayed, and he picked up a chess piece, moving it to another square before setting it down.

So far, this was relatively standard stuff—at the time, automata in the form of mechanical animals and expressive humanoids had delighted many a royal and commoner. One of the most prominent automata makers, Jacques de Vaucanson, had not only created the Digesting Duck—which wiggled its beak, quacked, and pooped out pellets it had been fed—but also the Flute Player, an automaton that could, in the words of Tom Standage in The Turk, “mimic almost all of the subtleties of a human flute player’s breathing and musical expression.”

Compared to these masterful simulacra, the Turk, with his expressionless face made of carved wood and jerky arm movements, initially seemed an inferior product. But then came the rest of the chess game. The Turk was good. Really good. And it wasn’t just adept at executing a repetitive task. The Turk responded skillfully to the unpredictable behavior of humans. This machine seemed to be operating autonomously, guided by its own sense of rationality and reason. If the human opponent attempted to cheat, as Napoleon did when facing off against the machine in 1809, the Turk would move the chess piece back to its previous position, and, after repeated cheating attempts, would swipe his arm across the board, scattering pieces to the ground.

Of course, there had to be a trick to all of this. But the nature of the deception was, for many decades, elusive. Following the 1770 demonstration, which astonished Maria Theresa and her attendants, von Kempelen, an engineer rather than an entertainer, was content to let the Turk rest. The automaton sat in a neglected state until after Maria Theresa’s death, when her son and royal successor, Joseph II, remembered the Turk and asked von Kempelen to revive it. In 1783, von Kempelen took the Turk on tour to Paris, where he once again astonished onlookers—including a certain chess-loving American by the name of Benjamin Franklin.

Tours of England and Germany followed over the next year. During this time, people began to publish their speculative accounts of the Turk’s workings. Some, such as British author Philip Thicknesse, were indignant at the notion that the Turk was a purely mechanical creation whose gameplay was free from human influence. “That an AUTOMATON can be made to move the Chessmen properly, as a pugnacious player, in consequence of the preceding move of a stranger, who undertakes to play against it, is UTTERLY IMPOSSIBLE,” wrote Thicknesse in a critical pamphlet he passion-published in 1784. (The immoderate word capitalization is all his.)

Thicknesse did not believe, as others did, that von Kempelen was directing the Turk’s gameplay from several feet away using strong magnets, stealthy strings, or remote control. His opinion took the Occam’s Razor approach, with a child-labor twist: He wrote in his pamphlet that the cabinet must be concealing “a child of ten, twelve, or fourteen years of age”—presumably one whose chess talents were prodigious.

The notion that someone was hiding in the cabinet was espousedfrequently over the decades, with variations on the size of the hypothetical person as well as their positioning. The cabinet measured four feet long, two-and-a-half feet deep, and three feet high—dimensions that encouraged people to speculate that short-statured people and children were the most likely candidates for the role of hidden Turk operator. Some believed that the concealed person stayed in the cabinet the whole time, using strings, pulleys, and magnets to execute the chess moves, while others thought the operator crawled up into the body of the Turk in order to control him.

Then there was the complication of the pre-demonstration routine in which von Kempelen would open the cabinet doors and drawers and shine a candle inside, seemingly precluding the presence of a human. But this, too, was cited as a mere trick—in 1789, Freiherr zu Racknitz proposed that the concealed operator hid in the back of the cabinet’s bottom drawer during the pre-game display, then moved to the main portion.

The most outlandish tale of a hidden operator comes from Jean Eugène Robert-Houdin, a French magician who encountered the Turk in 1844—long after its heyday. In his 1859 memoirs, Robert-Houdin passed on the Turk’s origin story—a clearly apocryphal tale that he nonethelessdescribed in great detail. According to Robert-Houdin, von Kempelen was in Russia during the 1790s when he met a doctor named Osloff. The doctor was sheltering a fugitive Polish soldier, Worousky, whose legs had been blasted away by a cannonball. This soldier happened to be a gifted chess player. So von Kempelen did what anyone would do in the situation: spent three months building a fradulent humanoid automaton chess player machine equipped with a cabinet large enough to house Worousky, thereby smuggling him out of Russia to safety by touring the automaton through major cities. A foolproof plan if ever there was one.

Such outlandish stories, while entertaining, added unnecessary complications. The truth was simpler: the Turk did operate via a concealed operator, who controlled each movement from inside the cabinet by candlelight, pulling levers to operate the Turk’s arm and keeping track of the moves on their own board. Von Kempelen, and his Turk-touring successor, Johann Maelzel, picked up new chess players on their travels, gave them a quick how-to orientation, then bundled them into the cabinet.

Though the machine ultimately relied on human behavior and a bit of old-fashioned magic, its convincingly mechanical nature was cause for both wonder and concern. Arriving smack-bang in the middle of the industrial revolution, the Turk raised unsettling questions about the nature of automation and the possibility of creating machines that could think. The fact that the Turk appeared to operate on clockwork mechanisms, complete with whirring sounds, contradicted the idea that chess was, in the words of Robert Willis in 1821, “the province of intellect alone.” If a machine could play a human game at the mercy of the human whims of its opponent, what else could it do?

This was one of the big questions rattling around the young mind of Charles Babbage when he first saw the Turk play when it toured England under Maelzel in 1819. Three years later, Babbage began working on the Difference Engine, a machine designed to calculate and tabulate mathematical functions automatically. It was an early step on the path toward artificial intelligence.

“Unlike the new machines of the industrial revolution, which replaced human physical activity, this fragment of the Difference Engine, like the Turk, raised the possibility that machines might eventually be capable of replacing mental activity too,” writes Tom Standage in The Turk.

In the 1820s and ’30s, Maelzel took the machine for one last hurrah around the northeast United States, during which Edgar Allan Poe developed a fondness for it and wrote his own treatise on the human-assisted operations he assumed were in place during gameplay (http://www.eapoe.org/works/essays/maelzel.htm). But the thrill of the Turk was fading. By the 1850s, with Maelzel having perished during a Turk tour of Cuba, the machine sat forgotten in the Chinese Museum in Philadelphia. It was there that, in 1854, it succumbed to a fire.

Though the Turk could be called a fraud, to regard the machine as a mere trick or swindle is to dismiss the profound and disruptive questions it introduced. The Turk may not have been intelligent, but it pointed toward an all-too-easily imaginable future of machines that can think for themselves—an ethical conundrum with which even the world’s AI experts are still struggling.

http://www.slate.com/blogs/atlas_obscura/2015/08/20/the_turk_an_supposed_chess_playing_robot_was_a_hoax_that_started_an_early.html

Advertisements

In the steppes of southwestern Russia, there lies the largest Buddhist city in all of Europe, a town called Elista. In addition to giant monasteries and Buddhist sculptures, Elista is also home to kings and queens—but not in the royal sense.

Lying on the east side of Elista is Chess City, a culturally and architecturally distinct enclave in which, as the New York Times put it, “chess is king and the people are pawns.”

Chess City was built in 1998 by chess fanatic Kirsan Ilyumzhinov, the megalomaniac leader of Russia’s Kalmykia province and president of the International Chess Federation, who claims to have been abducted by aliens with the wild, utopian mission of bringing chess to Elista.

Following the aliens’ suggestion, Ilyumzhinov built Chess City just in time to host the 33rd Chess Olympiad in grand fashion. Featuring a swimming pool, a chess museum, a large open-air chess board, and a museum of Buddhist art, Chess City hosted hundreds of elite grandmasters in 1998 and was home to several smaller chess championships in later years. Also found in Chess City is a statue of Ostap Bender, a fictional literary con man obsessed with chess.

But while Chess City brought temporary international attention to Elista, it was also highly controversial. In the impoverished steppes of Elista, cutting food subsidies to fund a giant, $50 million complex for the short-term use of foreigners wasn’t a popular idea with much of the region. Once the Chess Olympiad was over, Chess City became sparsely used and largely vacated, a symbol to the people of Elista of the local government’s misguided priorities.

http://www.slate.com/blogs/atlas_obscura/2017/01/30/the_alien_inspired_chess_city_in_europe_is_a_haven_for_chess_lovers.html

Thanks to Kebmodee for bringing this to the It’s Interesting community.

t’s been almost 20 years since IBM’s Deep Blue supercomputer beat the reigning world chess champion, Gary Kasparov, for the first time under standard tournament rules. Since then, chess-playing computers have become significantly stronger, leaving the best humans little chance even against a modern chess engine running on a smartphone.

But while computers have become faster, the way chess engines work has not changed. Their power relies on brute force, the process of searching through all possible future moves to find the best next one.

Of course, no human can match that or come anywhere close. While Deep Blue was searching some 200 million positions per second, Kasparov was probably searching no more than five a second. And yet he played at essentially the same level. Clearly, humans have a trick up their sleeve that computers have yet to master.

This trick is in evaluating chess positions and narrowing down the most profitable avenues of search. That dramatically simplifies the computational task because it prunes the tree of all possible moves to just a few branches.

Computers have never been good at this, but today that changes thanks to the work of Matthew Lai at Imperial College London. Lai has created an artificial intelligence machine called Giraffe that has taught itself to play chess by evaluating positions much more like humans and in an entirely different way to conventional chess engines.

Straight out of the box, the new machine plays at the same level as the best conventional chess engines, many of which have been fine-tuned over many years. On a human level, it is equivalent to FIDE International Master status, placing it within the top 2.2 percent of tournament chess players.

The technology behind Lai’s new machine is a neural network. This is a way of processing information inspired by the human brain. It consists of several layers of nodes that are connected in a way that change as the system is trained. This training process uses lots of examples to fine-tune the connections so that the network produces a specific output given a certain input, to recognize the presence of face in a picture, for example.

In the last few years, neural networks have become hugely powerful thanks to two advances. The first is a better understanding of how to fine-tune these networks as they learn, thanks in part to much faster computers. The second is the availability of massive annotated datasets to train the networks.

That has allowed computer scientists to train much bigger networks organized into many layers. These so-called deep neural networks have become hugely powerful and now routinely outperform humans in pattern recognition tasks such as face recognition and handwriting recognition.

So it’s no surprise that deep neural networks ought to be able to spot patterns in chess and that’s exactly the approach Lai has taken. His network consists of four layers that together examine each position on the board in three different ways.

The first looks at the global state of the game, such as the number and type of pieces on each side, which side is to move, castling rights and so on. The second looks at piece-centric features such as the location of each piece on each side, while the final aspect is to map the squares that each piece attacks and defends.

Lai trains his network with a carefully generated set of data taken from real chess games. This data set must have the correct distribution of positions. “For example, it doesn’t make sense to train the system on positions with three queens per side, because those positions virtually never come up in actual games,” he says.

It must also have plenty of variety of unequal positions beyond those that usually occur in top level chess games. That’s because although unequal positions rarely arise in real chess games, they crop up all the time in the searches that the computer performs internally.

And this data set must be huge. The massive number of connections inside a neural network have to be fine-tuned during training and this can only be done with a vast dataset. Use a dataset that is too small and the network can settle into a state that fails to recognize the wide variety of patterns that occur in the real world.

Lai generated his dataset by randomly choosing five million positions from a database of computer chess games. He then created greater variety by adding a random legal move to each position before using it for training. In total he generated 175 million positions in this way.

The usual way of training these machines is to manually evaluate every position and use this information to teach the machine to recognize those that are strong and those that are weak.

But this is a huge task for 175 million positions. It could be done by another chess engine but Lai’s goal was more ambitious. He wanted the machine to learn itself.

Instead, he used a bootstrapping technique in which Giraffe played against itself with the goal of improving its prediction of its own evaluation of a future position. That works because there are fixed reference points that ultimately determine the value of a position—whether the game is later won, lost or drawn.

In this way, the computer learns which positions are strong and which are weak.

Having trained Giraffe, the final step is to test it and here the results make for interesting reading. Lai tested his machine on a standard database called the Strategic Test Suite, which consists of 1,500 positions that are chosen to test an engine’s ability to recognize different strategic ideas. “For example, one theme tests the understanding of control of open files, another tests the understanding of how bishop and knight’s values change relative to each other in different situations, and yet another tests the understanding of center control,” he says.

The results of this test are scored out of 15,000.

Lai uses this to test the machine at various stages during its training. As the bootstrapping process begins, Giraffe quickly reaches a score of 6,000 and eventually peaks at 9,700 after only 72 hours. Lai says that matches the best chess engines in the world.

“[That] is remarkable because their evaluation functions are all carefully hand-designed behemoths with hundreds of parameters that have been tuned both manually and automatically over several years, and many of them have been worked on by human grandmasters,” he adds.

Lai goes on to use the same kind of machine learning approach to determine the probability that a given move is likely to be worth pursuing. That’s important because it prevents unnecessary searches down unprofitable branches of the tree and dramatically improves computational efficiency.

Lai says this probabilistic approach predicts the best move 46 percent of the time and places the best move in its top three ranking, 70 percent of the time. So the computer doesn’t have to bother with the other moves.

That’s interesting work that represents a major change in the way chess engines work. It is not perfect, of course. One disadvantage of Giraffe is that neural networks are much slower than other types of data processing. Lai says Giraffe takes about 10 times longer than a conventional chess engine to search the same number of positions.

But even with this disadvantage, it is competitive. “Giraffe is able to play at the level of an FIDE International Master on a modern mainstream PC,” says Lai. By comparison, the top engines play at super-Grandmaster level.

That’s still impressive. “Unlike most chess engines in existence today, Giraffe derives its playing strength not from being able to see very far ahead, but from being able to evaluate tricky positions accurately, and understanding complicated positional concepts that are intuitive to humans, but have been elusive to chess engines for a long time,” says Lai. “This is especially important in the opening and end game phases, where it plays exceptionally well.”

And this is only the start. Lai says it should be straightforward to apply the same approach to other games. One that stands out is the traditional Chinese game of Go, where humans still hold an impressive advantage over their silicon competitors. Perhaps Lai could have a crack at that next.

http://www.technologyreview.com/view/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/

Thanks to Kebmodee for bringing this to the It’s Interesting community.