Robotics Reference
In-Depth Information
The black King
is in the same
zone as the rook
is not in the same zone as the rook and the vertical
distance between the black king and the rook is
more than
one square
one square, with the vertical distance
between the two kings being
more than
two squares
Two squares, with the number of squares representing
their horizontal distance apart being
odd
The rook
moves one
square
horizontally
even
The white king
moves one
square
towards the
black king
zero
The rook
moves
down one
square
The rook moves
away
horizontally
The rook
moves
down one
square
The king
moves down
one square
1
2
3
4
5
6
Figure 5.
The six possible operations of Torres y Quevedo's Chess endgame machine
(originally printed in the author's topic
Chess and Computers
(Computer Science Pr,
Rockville, MD, 1976))
The Nimotron
In 1938 the first machine was built that could play a complete game
of skill. The machine was designed and patented by Edward Condon,
Gerald Towney and Willard Derr and it played the game of Nim. Their
machine was called the Nimotron and was exhibited by their employer,
Westinghouse, at the 1939 World's Fair in New York.
Nim is a two-player game that starts with a number of piles of objects,
such as matches, and with a number of objects in each pile. Typically
there might be four piles, as in the Nimotron, but any number of piles
canbechosenandanynumberofmatchesineachpile.(Fourpileswith
1, 3, 5 and 7 matches makes for an entertaining game.) The players
take turns to move. In making a move a player must choose one of the
piles and remove at least one match from that pile. (S)he can remove
more than one, up to the whole pile—any number that (s)he wishes.
The player who removes the last match of all loses the game. (There is
another version of Nim in which the player who removes the last match
of all wins the game.)
There is a method of selecting the best move in Nim from any posi-
tion. Anyone who follows this method will always win the game provided
that at some point (s)he has a winnable position. Such a method is called
an
algorithm
, which means a method that will find a correct solution to a
problem if such a solution exists. In Nim the winning algorithm is based
on the use of binary numbers (made up of 1s and 0s). The first step in
the algorithm is to convert the number of matches remaining in each pile
after your next move into binary. So if you make a move that creates the
