CHESMAYNE
Computer
think-twi
stranger in paradise
Designing a machine to play chess
In the early history of many disciplines, there has appeared an individual, who so far
outshone h/her peers, as to be remembered as the father of the discipline in
question. Hippocrates, for example, is
often referred to as the father of medicine, Thomas Aquinas as the father of philosophy or, Robert Boyle as that of chemistry.
But one figure towers above them all - the depth and breath of
Aristotle’s contribution to so many fields of thought. Aristotle was born in Macedonia in 384 BC
and was a pupil of Plato, before becoming tutor to the future Alexander the
Great. Daft as some of his ideas may
seem today, for centuries it was enough to settle any scientific argument to
announce that ‘Aristotle says.......’
“Aristotle Contemplating the Bust of Homer”, Rembrandt
C3PO - R2-D2
audio: “super sounds of the ‘70s”
It was only with the Renaissance and
the advent of new scientific instruments that fresh ideas gained currency. But then, as Aristotle said ‘no excellent
soul is without some touch of eccentricity’.
Charles Babbage, the deviser of the first general-purpose computing
machine ‘the analytical engine’, in the mid-19th century, foresaw
that machines would one day be able to play games like chess. His device
was purely mechanical, and driven by steam.
In 1890 the Spanish scientist Torres y Quevedo created the first genuine chess-playing machine. The first attempts at designing
chess-playing machines had more to do with the realm of magic and illusion than with pure science.
It is not beyond the bounds of belief that the basic techniques for
constructing a humanoid robot capable of thinking for itself, like HAL-9000 in the
film 2001, C3PO and R2-D2 in the Star Wars films or, machines on
board the U.S.S. Enterprise (NCC-1701-D), could arise from intensive work in
programming machines to master the logical processes needed for playing
chess.
Torres y Quevedo
audio: “somebody kill me”
A more honest attempt to design a
chess playing machine was made in 1914 by Torres y Quevedo, who constructed a
device which played an endgame of KI and RO versus KI.
This machine played the side with the KI and RO and could force ++CM in a few moves however a human opponent played. Since an explicit set of rules can be given for making satisfactory moves in such an endgame, the
problem is relatively simple, but the idea was quite advanced for this
period. A chess playing ‘automan’ was made by Baron Wolfgang
von Kempelen and operated
by a hidden player (reputedly Allgaier, Vienna’s
strongest player of the day) who was ingeniously concealed in the machine. Several other chess automata were made in the
19th century.
Automaton
A mechanical device that plays
chess and operated by a human being.
These have included the Turk, Ajeeb, Mephisto and Ajedrecista.
In the 1950s computers were designed to play chess. The first and most famous is the Turk, first
unveiled in 1769. The exhibitor of
this device could open the cabinet to convince an onlooker that nobody was
hidden inside the apparatus.
Ajedrecista is presently on display at the Polytechnic Museum, Madrid. Its inventor, Torres y Quevedo, 1852-1936,
was subsidized by the Spanish government to demonstrate the possibility of inventing a machine that could play a game of chess.
Maelzel chess automaton
A device invented by von Kempelen and widely exhibited as a chess playing machine. Edgar Allan Poe wrote a paper entitled
‘Maelzel’s Chess Player’ purporting to explain its operation. Various writers concluded that the machine
was operated by a concealed human GM. A complete account of the
history and method of operation of the Automaton is to be found in a series of articles by Harkness and Battell in
‘Chess Review’, 1947.
Ajeeb
Chess automaton made by Charles
Alfred Hooper (1825-1900). This
consisted of a life sized dark-skinned Indian figure with a mobile head, trunk
and right arm, who sat on a cushion mounted on a large box. It had an elaborate clockwork mechanism
that was conspicuously wound by a large key.
A strong
chess player was concealed
inside the machine and among these were: Charles Moehle, Albert Beauregard Hodges,
Constant Ferdinand Burille and Harry Nelson Philsbury.
The inventor of the computer
There is a science fiction
fascination about computer chess, which goes back to the very first machines
which played the game. If you are at
all interested in the history of the computer you cannot help but debate the
question of who actually invented the first machine. Of course, it is not a particularly
meaningful question because reality usually cannot be summarized by a neat list
of who invented what. There is
no doubt that Babbage conceived the idea of a computing machine long before the
technology was right. After this there
are many people who claim to have built the first computer. When developments in technology started to
make creating a working computer possible it seems that a number of people
reinvented Babbage’s idea. But the real
problem with naming the actual inventor is that it is difficult to know what to
accept as the first stored program computer.
However, if you really must have an easy, clear-cut answer, why not just
accept the rule of law!
John V Atanasoff
John V Atanasoff is the inventor
of the computer, and that is a legal ruling.
He went as far as court to prove he invented the computer. Like many scientists of his time Atanasoff
had big problems with calculations. He
organized his graduate students into teams working with mechanical calculators,
but solving equations was still too slow a task. He thought of using mechanical analogue
computers of the sort that were becoming important due to the work of Vanevar
Bush but, these could only solve ordinary differential equations and Astanasoff
wanted to solve systems of partial differential equations. In short, he needed a powerful digital
computer. He realized that it would be
possible to store a bit as a high or low charge on a capacitor. A simple idea, but the problem is that the
charge leaks away. Atanasoff solved the
problem using a regeneration process he called ‘jogging’. This was the forerunner of the dynamic memory that all our present day machines rely on. He spent more than a year trying to
perfect the jogging circuit and the binary logic elements his computer would
need, and then he hired a graduate student, Clifford Berry. They worked together on the prototype
machine, which they completed in 1939.
It was an amazing machine.
ABC: Valves, drums, capacitors and
punch cards
The logic used 300 valves and the
memory was built using drums 8 inches in diameter and 11 inches long. Each drum had capacitors mounted on it in
rows, and the charge on each was read and/or refreshed as the drum
rotated. The storage capacity was thirty
50-bit numbers per drum, roughly 1.5K. Input was via punch cards, five 15-digit
numbers per card coded in decimal. This
ABC machine never really worked as a completed computer, but worked long enough
to prove the principles but, not for long enough to solve any real
equations. They won a grant from Iowa University
who considered taking out a patent on the machine. After the 2nd World War Atanasoff
did not return to computers. He felt
that he had built a working computer and had spent enough time and energy on
the subject.
Eckert and Mauchly - ENIAC
Years later he regretted not
continuing his work. He had
misunderstood the revolutionary nature of the computer that he had built and
the impact it might have on the world.
Eckert and Mauchly got the praise for building the first electronic
computer, the ENIAC, without any mention of his pioneering efforts and the
ABC. The case finally came to court in
1970 and Atanasoff demonstrated a reconstruction of the machine to the
judge. It clearly made a big enough
impression for the decision to be made in his favor. The judgment described Atanasoff as the inventor
of the electronic computer and maintained that Eckert and Mauchly had built a
machine that derived from the ABC. The
patent was also overturned because ENIAC had been used on the H-bomb
calculations at least a year before the patent was filed. What might have been a big story went
virtually unreported due to some sleaze going on in the White House in October
1973 [‘tricky-dicky’]. Atanasoff
remained bitter that he did not get the credit he deserved. Bulgaria gave him the ‘Order of
Cyril and Methodius’, its highest scientific award. But the rest of the scientific community
has never been quite so sure. The key
question is whether or not ENIAC was derived from the ABC, as the legal ruling
states.
A chess game-tree
The idea of a machine which can
out-think, (out-compute) a human being seems to touch a mystical chord in most people. But
computers are, in practical terms, limited because chess (Chesmayne) is an infinite game. In theory
there is a limit to the number of possible moves that can be made in any position. However, the number of possible Chesmayne
games in a particular ‘chess
game-tree’ (:gt) is vast. To illustrate how
big this number is, consider that less than 1018 seconds have
elapsed since the earth was formed some 4.6 billion years ago. Even if one considers a reasonable
statistic, such as all games last 40 moves, then assuming an average choice of
30 moves per position on a D-Array (:L01), the number of games in one single :gt (game tree)
is 10120, which is more than the number of atoms in ‘our’
universe.
Digital computers
In Arthur C.
Clarke’s film ‘2001, A Space Odyssey’, there is a scene in which
one of the astronauts (cosmonauts, argonauts) plays :L01 of Chesmayne against the spaceships murderous onboard computer which ‘became
operational at the HAL plant in Urbana,
Illinois, on January 12th
1983’ and is soundly thrashed.......
Poole: Umm. Anyway, QU takes PA.
HAL: BS takes PA.
Poole: Lovely move, er... RO to $D01.
HAL: I’m sorry, Frank, I think you missed it. QU1 to Bishop-6. BS takes QU. KT takes
BS. ++CM.
Poole: Ah, yeah.
Looks like you’re right. I ++RS.
HAL: Thank you for an enjoyable game.
Poole: Yeah. Thank you.
[This was the end of an actual game played in Hamburg in 1913].
The school of
thought that computers will one day be the worlds strongest players of
occidental chess predated the technology which enabled the concept to be
realized by almost two hundred years, if you count the Turk, which was an
automaton chess-player, first invented and exhibited by Baron Wolfgang von
Kemplen in 1769.
The 1950s
Machine chess-playing prehistory
gives way to history in the 1950s, about one decade after the invention of the
first electronic digital computer. Digital
computers are so called because they compute, or process information, although
that idea is somewhat misleading. They
can handle logic just as well as arithmetic and the end-product of their
calculating processes need not be a number ie, it may be words on a laser
printer or words displayed on a monitor screen - a graphic visual display or even the move of a chess MP/mp.
Information processing systems
The development of digital
computers has produced powerful tools for the study of mental processes. Because computers
are information processing systems they can manipulate information and make
decisions. Knowledge of information processing is essential if we are to understand the
tools of our thought mechanisms, and while your mind is not a digital computer when it comes to the
abstract scientific principle of information processing, there are general
rules that apply to both your mind and the computer. This information processing metaphor may be
applied to the problems confronting a chess player during play, and these would include perception, memory, thinking, decision making
and problem solving etc.
Multimedia computers
Multimedia has become the common
term for the next generation of personal computers which will transform the way
we live, work, learn, play and relate to our fellow human beings. As digital streams of sound, images and text
flow around our globe, almost every aspect of life is expected to change beyond all recognition in the near future. These machines come fitted with DVD Rom
drives which use discs similar in appearance to the music CDs you may have
in your home. The present generation
of computer DVDs, however, can each hold a huge amount of information (700mb on
a typical CD and 4+ Gigabytes on a DVD), which is equivalent to about 600
floppy disks or 4,000+ on a DVD. This
makes them ideal for storing encyclopedias, telephone directories, interactive
games, chess and astronomy databases etc. By using a
multimedia PC it is now possible to literally browse through the material
presented at the touch of a button - just like this text! For education, business or entertainment
they supply the complete answer in one neat package. The latest versions of these machines use
Pentium chips which run at blistering speeds and come complete with DVD Rom,
Hard Disk, Soundcard and speakers and may be connected to printers, VCRs (in
order to cut and paste video images), modems, fax and other devices. Word processors, spreadsheets and other
important software is pre-loaded on these computers - so all you have to do is
switch it on and away you go.
Deep Thought
This program
has defeated Tony Miles, Robert Byrne, David Levy and Bent
Larsen. It failed in its attempt to defeat Garry
Kasparov. Deep Thought Mk-1 could see 750,000 nodes of look-ahead per second, while Deep
Thought Mk-2 with IBMs assistance has increased this to 10,000,000. To beat Kasparov the objective is to create
a machine capable of seeing 1-Billion positions per second. Deep Thoughts games show that even the very
best that modern technology has to offer can not as yet dominate the world of
serious well-prepared mature chess players (GMs). In October 1989 Gary
Kasparov (world champion) played against the ‘Deep Thought’ programme.
Kasparov played from the New York Academy of Arts in Greenwich Village, while Deep Thought played in Pittsburgh via an electronic link. It was expected that Kasparov would win, but the programmers must have been disturbed by the way he did in fact
eventually win. Note: in 1994 Garry
Kasparov (Harry Weinstein) was finally beaten on :L01 of Chesmayne (traditional chess), but in 1995 he won against Fritz-4. Please see ‘Deep Thought/Blue’ for an update.
Against a human player a GM can feed off human psychology and the
opponents fear but a computer does not have any psychology.
Arithmetic operations
Chess is not just engaging, but
also one of the most sophisticated of human mental activities. Chess is so old that we cannot say when or where it was
originally invented. Billions of
games on :L01 of Chesmayne have been played and thousands of books have been written, yet the game is still fresh and new, and
particularly so, on the new
levels described in
this text. Basic arithmetic gives us
the answer why this is so. One reason
is that a machine is built to carry out arithmetic operations - the moves on the
board are arranged into a series of such operations before the program can
adequately deal with them.
A calculating robot
If you survey a board with a B-KI and B-PA at one end and an A-KI and A-PA at the other, the intervening cells being empty, you will know immediately that neither KI is in +CH. A computer is in the position
of a robot who has to carry out an arithmetic calculation to
find which cell to examine next and, having arrived there, finds instead of a MP or mp, a sheet of paper telling it which operation the
MP/mp is allowed to perform in order to reach other cells on the board. It transpires that several hundred
calculations may be needed to determine whether or not the KI is in +CH, and
even at electronic speeds the whole process can take an appreciable fraction of
a second.
A Chesmayne D-Array
On average,
each move on :L01 of Chesmayne offers a choice of about 30 possibilities and the
average total for a complete game is about 40 moves.
This means that there are about 10120 possible games on
:L01. To put this in perspective, imagine that you had a super fast computer processor which could play a million
games per second, then it would take the program about 10108 years
just to play all the games on :L01.
From this mind-boggling number we can conclude that no program could
play a perfect game of chess, but this is what makes the problem of programming
a computer so intriguing for programmers.
Your machine must play the game in human terms, that is, it must detect
the strategy and anticipate your judgments. Not having the omniscience that would allow
it to beat you no matter what occurred, it must try to out-compute and out-wit you in actual play. If you can
explain in plain language with the aid of symbols how a
calculation is to be done, then it is feasible to programme a computer to carry
out a particular calculation. A computer
when provided with the programme can make chess moves and find the solution of
a problem within these defined limits.
It is built to carry out arithmetic operations and the moves on the
board have to be broken down into a series of such operations before the
machine can deal with them.
Master players
Mature players are wo/men of
considerable intellectual ability. They have
in addition an extra latent ability. GMs who begin playing :L01 of Chesmayne early show unusual excellence at a tender age. The specific ability begins to manifest
itself around the age of nine or ten (in some cases). There are few GMs who cannot play blindfold, and play many games on :L01 at once, achievements
which are entirely beyond the powers of the ordinary mortal. The order of intellectual activity which
we are required to reduce to simple terms is therefore of a high order. This level of playing ability is called ‘genius’ [by some].
Chessmasters
GMs, to a
certain extent, talk in their own language.
This language has a vocabulary rich in content, which if understood by a
computer could make the task of programming the game easier. There are no instant experts in this game
and there appears not to be anyone on record who achieved a 2500+ rating with less than about ten years of intense preoccupation with the
game. It has been estimated that a GM
will spend 10,000 to 50,000 hours at a traditional chess board. These hours have been
compared to the time a highly literate person will spend in reading by the time
they have reached adulthood and who have vocabularies of 50,000 words at their
command. A GM will have a similar traditional western chess vocabulary.
Intelligence Quotient
Vocabulary is commonly regarded as
the best single test of IQ and tests were invented in France by Alfred Binet,
1857-1911. His tests are based on a
person’s intellectual aptitude ie: judgment, reasoning and comprehension. He produced a list of questions that could be solved regardless of belief-system, previous school
record or social class. A normal IQ is
considered to be 100. IQ is calculated
by the ratio of mental age over the chronological age. What this means is that a five-year old child may have a mental age of seven.
Many wo/men with high IQs (genius) are often failures in their academic,
personal and professional life. Shakespeare used a vocabulary of 25,000 words in his writing. Vocabulary and the ability to envisage
relationships between different words is a major factor in measuring IQ.
Goethe - Mozart - Mensa
Failure or defeat should not be
part of your chess vocabulary. Goethe
had a vocabulary of 50,000 words and he has been described as ‘The Prince of
the mind’. He is best remembered for his masterpiece ‘Faust’. In his play
‘Gotz von Berlichingen’ he described chess as the mind game ‘par excellence’, and the ‘touchstone of the intellect’. It has been
demonstrated by Dr Gordon Shaw of the Physics Department of the University of California that listening to the music
of Mozart can stimulate your mind and increase your IQ. He conducted tests on chess players and
found that their brainwaves appeared to be making music - the natural patterns of their brains were similar to musical patterns, indicating that we
need to be trained into classical music at a young age. In Britain you can join the high-IQ
society. The Los Angeles chapter of Mensa accepts as
members, only people with IQ scores of 148 and above.
The core of the human
intellectual endeavor
Chess is the intellectual game
par-excellence. Not having a chance device to muddle the contest, it pits two minds against each other in a
battle situation so complex that neither player can hope to
comprehend it entirely, but sufficiently open to analysis that each can expect to out-think h/er opponent during practical
play. Traditional chess was sufficiently deep and subtle in its implications
to have supported the rise of professional players and to have allowed a
deepening understanding through centuries of study without becoming exhausted
or barren. Such attributes mark the
game as a natural subject for attempts at mechanization. If a machine could be invented that could
play and beat a human Chesmayne player, then it seems, we would have penetrated
to the core of the human intellectual endeavor.
David Levy
David
Levy is an author and
computer chess player. He is a
Scottish IM and is one of the world’s leading authorities on
computer chess and President of the International
Computer Chess Association. His ‘computer-hostile’
playing methods made him the scourge of chess computer programmers during the
1970s and 1980s. He is the author of
‘Chess & Computers’, ‘More Chess’, ‘Computers & the Chess Computer
Handbook’ and ‘Computer Chess Compendium'.
He competed in a game in Hamburg
in 1979, in which he sat in a soundproof booth in front of a giant industrial robotic arm. This arm was connected
via a satellite, to the latest version of the Northwestern
University program Chess 4.8, running
on a CDC Cyber computer in Minneapolis. He was under orders to play interesting
chess (on :L01), and so opened with a very risky variation of the KIs
gambit. The advantage swayed back and forth, and just when he had victory in his grasp he got careless and allowed the program to ‘swindle’ him and get away with a draw. The game
lasted for about ten hours, without a break except for a few communications
failures of fairly short duration.
A programme
The complete list of instructions
or orders needed for any particular problem is referred to as a
‘programme’. Subsequences of
instructions in a programme are called ‘routines’. A chess problem, as every player knows, is
the problem of finding a move, the ‘key
move’, which will ++CM your opponent, irrespective of h/er replies, in a given number of
further moves. When a computer is
provided with a programme it can make moves and find the answer to the problem
within the limits stated above.
Artificial intelligence
:L01 of Chesmayne has been used as a test case scenario for artificial intelligence
research for over three decades.
Programming the endgame has proved to be difficult, even programming exact
play has turned out to be problematic, if ‘correct’ play is taken to mean ++CM your opponent using the rules of traditional chess. The contest can be divided
into three main sections:
:L01 programs survive the opening problems by referring to a library of openings containing the usual
book variations. During the middle
game they can also
play quite well. In the endgame phase accidents can mar their play unless a material advantage has been realized before this stage has been
reached. In the endgame the issue is
not computing ability, but trying to handle and reach a favorable
position. The objective of the
computer and a human player is to achieve ++CM, but before reaching this stage many intermediate sub
goals have to be attained. Endgames
have traditional canonical names of which the ‘Lucena Position’ and ‘Philidors Legacy’ are examples. After
programming a computer to play a game which is indiscernible from that played
by a human being, programmers have raised their sights for a new aim of being
able to beat a human GM.
A Chesmayne position
In practice you will find that you
will not follow all continuations but, only some of them and will not follow
them to the end of a game but only for a move or so. Often you will arrive at a position that is
not worth further consideration and at other times you will not hesitate in
playing a move. The further
a position is from the position in actual play the less likely it is to occur,
and you will therefore devote less time to its consideration. No two positions will have the same value and from this you can form an evaluation of the material on your particular level of play.
A position is
considered dead if there are no moves from that position and no captures or recaptures or ++CM positions discernible. Positions consist of a collection of rules of thumb and are of various types ie…….
|
01
|
What to do next
|
|
02
|
What principles to follow
|
|
03
|
What measurements to take
|
|
04
|
How to interpret these rules of thumb
and so forth
|
They form the qualifications that
enable you to make a decision. A
programmers problem is combining all these facts into a cohesive unit that will
enable the programme to play a decent game at the level chosen. The number of rules of thumb, their
complexity and the necessity for adding new rules and modifying old ones, will need a comprehensive
computer language to implement.
Defined programming
On :L01 , there
are about 30 legal moves from each position.
Two moves ahead increases this to 304. This is 810,000 continuations which are
brought into the picture. Since your
computer has no way to eliminate unlikely moves, it is forced to investigate
every possible move, until a solution is found. Even for a two-mover, the total number may
run into several thousand on average.
Since every move has to followed by a test for legality, it may consume
a few seconds, and the total move may then take longer than this. By the use of refined programming and a
faster processor, say 3 Ghz on a home computer, or both, a superlative game can be realized.
Width of the search tree
It is already known that superior
performance relies on limiting the width of the search, but what about superior
computer performance? Computer
programs, such as ‘Deep Thought’ or, ‘Chess’, written by Slate and Atkin, or
‘Belle’, written by Thompson and Condon of Bell Labs, have used a modification
of the brute force approach. These
programs can defeat all human traditional chess players including the GMs. Such programs have little ‘knowledge’ of chess per se.
Speed of computation
Like most brute force solutions
these programs emphasize speed of computation.
Such an approach has beaten GMs, but their success involves the creation
of hardware that can carry out computations further into the state-action tree
in a reasonable period of time, and hence the use of high speed
processors. Attempts have been made to
produce ‘knowledge based’ programs that limit the width of the search and ‘Paradise’ is one of these.
The Paradise
program
This program does
not play an entire game. It plays
from selected positions in the middle game.
The middle
game is the phase
in the middle of most contests where MPs/mps on the board are reduced through exchanges. Paradise
operates by examining a database of about two hundred rules. A rule is a two-part statement. The 1st part of the rule refers to
a set of conditions that may be observed on the board. The 2nd part of the rule describes
an action that may be undertaken if those conditions are met. Rules resemble the ‘if-then’ statements of
a programming language. The two hundred
rules in Paradise are organized by
higher-level actions that occur on :L01 (traditional chess). Players normally view their MPs/mps to see if
any are in immediate threat of attack and look at the cells to see if they are
safe to move into and sometimes attempt to gain access to a cell by using a
decoy to lure an opponent’s MP/mp away.
Deeper into the state-action tree
These rules are
applied to the configurations of MPs/mps on the board until a plan is formulated that has a good chance of capturing a MP or mp. If the plan does
not work or have a good chance of winning material, it is abandoned. The end
result of this decision making process is that Paradise
explores only a narrow :sat (state-action tree).
Paradise has another thing in common
with expert players. All programs have
an artificial limit to their depth of search.
Paradise searches until its objectives
have been reached.
On arriving at this stage the program considers other nodes to determine if it is worth searching still
deeper. Because the rules limit the
number of possibilities that are explored from a selected node, this program
searches into the state-action tree deeper than other programs. It trades off width of search for
depth. The ability of Paradise is
restricted by the information that can be input into the two hundred rules, and
because of this modular nature, rules can be changed without affecting other sections of the
program. Improving the Paradise
program is accomplished by editing individual rules. Therefore, future versions of Paradise will
have the ability to measure the success of special rules and to change them
where necessary.
Binary code
The nucleus of your computer is a binary code. The actual
form of storage is not important. Each
instruction contains the number of a cell, MP or, mp or other chunk of data. The computer will obey a fixed set of instructions
for manipulating these chunks of data, one by one, and will sometimes jump to
some other instruction on the programme store. By making these ‘control transfer
instructions’ dependent on certain arithmetic conditions it is possible to
leave a ‘loop’ after a specified number of times, or when a specified result
has been obtained. What this means in
practice is that a computer can read a table or directory just as you can find
a number in a telephone index ie, (in England 17+ million numbers are listed
and 22+ million copies are produced annually - each book is reissued/updated
every 18 months and is now available on CD).
Expressed mathematically, the machine can find and operate on any of the
values it finds and this is exactly the function that a
computer is good at – just in the same way that you [could] find the telephone
number of your local MP/TD Prime
Minister, the QU,
your BS/VC or, the President to explain any personal problem you may have.
Lists of tables
By
allocating different letters to the Chesmayne MPs/mps ie, KI-A, QU-B, RO-C, BS-D, KT-E, PA-F, GU-G, FS-H, AD-I, GE-J and so forth, the computer can be made to enter a
sequence dealing with MP moves when a particular stored line triggers the appropriate
monogram, and in a similar fashion to trigger mp moves when it comes across their letters. It will
now be possible to describe the essential features of the programme by means of
lists of tables consisting of chunks of information contained in successive
stored lists. The computer will go
through these lists in alphabetical or, other type of order and increase the value found
from say B to B1, then B2 at appropriate stages in the programme.
The first list
The MPs will comprise the first list numbered
consecutively ie, MP1, MP2, MP3 etc and mp1, mp2 and mp3 etc, for the mps. Therefore, each MP/mp, cell, move, rule or any other relevant chunk of data will have a
letter or combination of letter and number associated with it. It follows that each MP/mp will have a cell
number on which it is to be found. If
the MP/mp is missing (captured), another number will indicate its absence.
The second list
A
second table will contain or describe
the position in a different way ie, the number of a particular cell on the
board and the MP/mp or lack of same occupying the cell and a number indicating
whether it is :A or :B. A move from one cell to another cell is made by adding a
certain number to the original cell number, and a way of telling the computer that
the edge
of the board has been reached
will be done in the same fashion.
A table for each MP/mp
Since D25 is the number of a cell at the edge of a D-array (8 x 8
board), the computer will be
informed that the limits of the board has been reached.
For each MP/mp a separate table is used ie, the occidental
KT table will be composed
of moves 2 x 1 and a Standard-Bearer by moves composed of 3 x 1 etc. In addition the computer will be informed if
the move being made is an :A move, or a :B move. It
follows that the :B and :A MPs/mps will each have different numbers to
distinguish them from each other. By
this process the computer will try out all the available moves from a given
position until a solution is found to the problem at hand, that is, the correct
solution. If the position is legal it then carries out the move and enters it into
another table for reference when the next move is to be played. What you then have in your computer memory is a table of tables listing all possible
moves.
A master routine
Once you have arranged the problem into a numerical
format that the computer can digest, it is not difficult to arrange a scheme
causing the computer to produce a set of suitable answers. This scheme will be executed by a master
routine.
Man versus computer robots
The man versus machine argument began, in it’s modern form, in a secret
establishment set up by the British War Office at Bletchley outside London, in
the early days of World War II. As it
happened, the team of cipher experts included the two best traditional
chess players in Britain at
that time - Harry Golombek and C.H. O’Alexander. Breaking codes is a bit like playing blindfold
chess with a hidden adversary. You have to
find out what s/he is talking about, and secondly, how s/he is saying it. The technical processes were complicated
enough - but once they understood that, it was not difficult to handle. The best mathematician at Bletchley, was
Alex G. Bell. Among his many
interests was a fascination for automata and :L01 of Chesmayne. The task assigned
to the mathematicians and engineers gathered there was nothing less than
breaking the German Enigma code. The
enemy’s radio signals were intercepted and the process of deciphering them was
done by the back-room boys on machines which were the forerunners of today’s
electronic computers. One of the first
computers, Colossus, was invented to help the crypto-analysts at Bletchley to break
the Enigma codes of their opponent - Germany.
Application of computer technology
There were spin-offs in other areas also. When the problem was cracked, and in the
final months of the war Colossus was paying off in a high rate of coded messages
being broken, the panel of brains brought together had the time to reflect on and discuss other possible
applications of the computer technology that they had helped to bring onto the
world stage. Whether by accident or by
design, there were many good traditional chess players at Bletchley. Probably it had been somebody’s inspired guess that a mind trained in chess would have a special aptitude and insight for code-breaking.
Three of the people working on the Colossus project had
a special interest in chess and in the potential of machine intelligence:
I.J.Good, D. Michie and Alan Turing. Turing and Michie had great contributions to make to the
field of computer chess after the war.
Michie has had great influence on the development of research on chess,
right up to the present day and Alan Turing is renowned as a computer scientist
from the earliest era. The curious
thing about Turing was that despite his outstanding brilliance as a mathematician,
he was quite hopeless at playing :L01 of Chesmayne. This shows
that while a high IQ may well be a necessary condition for playing GM chess, it is demonstrably not enough in itself. The first recorded game between man and
machine took place some time in 1952 and was staged in Turing’s office. His notebooks/jottings are still
classified material to this very day.
Machines to play chess
After the war Turing was given a government grant to
build a general purpose electronic computer, capable of solving a variety of problems
which led in turn to his discussing the possibility of machines being able to
play an average game of Chesmayne, :L01.
He wrote a paper that described a ‘program’ that could be played on a
computer. His paper went on to
discuss how this might be brought about and the problems involved in doing
so. In the immediate post-war years,
England and the United States of America were the main pioneers in
computing. ENIAC, the first American
computer was switched on in 1946 but worked on a decimal rather than a binary system and its purpose was chiefly weapons
development calculation.
The stored program
The second American computer, EDVAC, incorporated a
crucial innovation, suggested by John von Neumann, the ‘stored program’, kept
on coded punched paper and fed into the computer when it was required to solve
the task on a particular tape. This was
the breakthrough, together with the switch to other circuits that separated the
first general purpose computers from Colossus and ENIAC. Colossus and ENIAC were dedicated (just
like some of the dedicated chess computers of today) and could not be
programmed to do any other task.
Knowledge
Knowledge is the core of information possessed by the
chess player and can be used for an intelligent understanding of the strategic problems that can confront a player during a
contest. Knowledge in itself involves more than information ie, if you
went along to a meeting of chess strategists which discussed plans for winning manoeuvres, the knowledge you possess
would not improve your playing ability one iota.
However, if the information contained in these strategies could be
adapted by the chess player then h/er knowledge could be used to good effect
during practical playing conditions.
For example, you might review the principles of chess
which would include an opening repertoire of initial moves. As you improve with practice and experience
this knowledge will be modified and instead of counting out, say, the number of
steps an occidental KT makes on the board, you will do so
unconsciously. Some of these mental
processes will require a focused attention, while others like the castling
move (%K, %Q) on :L01 will take very little attentional effort.
Chunking - Frames
Simon and Gilmartin have speculated that the typical GM has encoded about 50,000 chunks of related MPs/mps, based on an examination and analysis of MP/mp positions.
Frames are a type of script, which are data structures full of details that
can be added to or taken out at will - just like the various sentences or
paragraphs in this text which you are presently reading. It is basically a method of organizing
information ie, in the chunking analogy just cited a frame might contain slots
of information such as, GU, PA, cell, Array, Regent, KI, ++CM and so forth.
So it seems that the mature player learns some meaningful configurations
which are easy to retain in memory and work with.
This might be demonstrated using the following anagram -
‘ssgniocPre’. Now, consider the following
letters – ‘Processing’.
Hierarchies
These letters are easy to remember and form a single
unit or word. The configurations of Chesmayne
MPs/mps on the different levels of Chesmayne are treated by mature players in the
same way as the letters cited above.
Mature chess players have their knowledge organized in a hierarachical
way. In their minds, specific details are logically chunked and these
chunks are grouped into more general topics, and these into even more general
types.
Jack in the Beanstalk - Pruning the
tree
Most advanced types of problem solving occur in knowledge rich domains, where the search processes and
solutions are most likely to be narrowed down by human expertise. A mature player differs from the amateur in
many respects, but the most important way is in h/er ability to prune part of the state-action tree. One of AIs
goals is to develop software that will ‘know’ something,
in just that sense, enabling a problem solver working in consultation with the
program to trim down the size of the state-action tree. A mature chess player accumulates knowledge
resulting from years of experience with the game. This
experience has produced knowledge that is independent of the players general
cognitive functioning ie, the mature player does not explore the branches of
the state-action tree any further than a novice. This means that a mature player does not
necessarily have a better memory than the novice.
The brute-force method
What s/he does have is superior organization of the
MPs/mps on the board which operates schematically. The mature players’ mental structure not only
organizes the MPs/mps but also indicates which lines of play should be
explored. Establishing simple sub goals
can prune the branches of the state action tree, making the problem more
manageable. This is what the mature
players’ schematic knowledge enables h/er to do. Chesmayne is played at a higher level by mature players than
it is by novices, in part because the mature player does not waste time and cognitive effort exploring unproductive
avenues. For AI researchers, this
presents a problem: what exactly does the mature player know that can be
formalized into a computer program of the game? AI research using the traditional
version of chess (:L01 of Chesmayne) has taken two distinct approaches to
the problem of knowledge. The first of
these is called the ‘power approach’, because no attempt is made to mimic the
knowledge structures of a human.
Instead, the program searches as much of the state-action tree as it
can, as quickly as it can. The
computer is just taking advantage of its computational speed to find an answer to the
problem, and for this reason is said to be ‘brute-forcing a solution’. The knowledge based approach tries to
formulate an algorithm that mimics the domain-specific knowledge of the
players.
Limiting the depth of the search
How are these two approaches be applied to chess? First, no
program searches the entire state-action tree, it is just too big. This means that all programs must limit
their search operations. These
restrictions can be written into the program in two ways. A program can restrict the number of moves
that are evaluated from any point in a game. This is known as…….
01 Limiting the
depth of the search. A program may
limit the number of plays
that
are evaluated from any node in the
state-action tree that are suggested for further exploration. This is called…….
02 Limiting the
width of the search. All programs
limit depth to a certain extent, usually for the sake of time. Increasing the depth of the search by just
a single node ie, looking four moves ahead instead of three, results in a
tremendous increase in the time required to carry out all the evaluative
computations. This is usually what
happens when you increase the level of play on one of the home computer chess
programs. The program now searches
further into the state-action tree, but if you
have such a program, you know that the amount of time required by the computer
increases dramatically with each increase in level. Not all programs limit the width of
search, however, and those that do not are referred to as ‘brute force
programs’. The programs consider every legal move available on
the board at that time and consider them all out to some, usually limited
depth. Knowledge-based chess programs
on the other hand are those that try to limit the width of search.
The human brain
Your brain is designed in such a way that only a limited number
of goals are active at any one time. The reason for this is that if you were to pay
attention to all the sensory information being received at any one moment, you
would have difficulty in making a move in the first place. The point is that you can only attend to
what can be held in short term memory. This
enables you to focus on what is important and make decisions swiftly. When you try to think ahead move by move during a chess game, you have to remember to go back and explore other
possibilities after exploring the current one. If you were to take into account all
possibilities at once your mind would be overwhelmed and this would lead you to
forget what to look at next on the board.
By conscious effort it is possible to keep the last few items in memory
and be able to respond to any type of danger or, other matter of importance
that may arise on the board in the meantime.
Automatic processes
The
matter of automatic processes has also to be understood during a chess
game. The players might be involved in
conversation at the start of the game and at the same time, setting
out the board. Placing the MPs and mps on the board can be
an automatic process and makes no demand on your working memory. On inspection you might realize that your KI is in the wrong cell. The reason
for this error is that placing the MPs/mps on the board is an
automatic process. While doing this
your attention was focused on the conversation with your opponent. Reading
this text on the moves just before a contest is unlikely to improve your ability, unless of course you want to remember low level
facts such as how many cells forward a mp can move etc.
Your ability to make predictions and think of moves that will occur is limited by the
constraints on your short term memory.
Short term memory
This paradox leaves the novice player in a peculiar
dilemma. How can the mature player win most of the time if s/he cannot see all the moves
from the opening to endgame play? You will
have a number of problems to surmount if you are to achieve success. It will
be difficult for you to compare several moves and then select the correct one. Because each course of action is complex
this will strain the capacity of your short term memory to picture a single alternative and its
ramifications, let alone carry out several moves in your mind simultaneously, in order to compare one with
another. There is no precise way to
compare alternatives because the decisions made will also have to include the
reactions of your opponent who has yet to make up h/her mind about their own
reaction yet.
Mental images
Another form of representation known as a ‘mental
image’ is used by the player to distinguish, say, a MP form a mp. It is
unlikely that you have pictures stored in memory or MPs/mps cooped up inside your brain as actual images, but you clearly recognize them, so
you must have some representation of these perceptual experiences stored in
such a manner that the pattern recognition mechanism can make use of them. It is these perceptual representations that
are used in a wide range of situations during a contest. It would seem you have the information
necessary to visualize and manipulate the MPs/mps in such a way that you can
produce a plausible next move response when required to do so. This means that you can achieve ++CM, despite the obstacles introduced by your opponent and transform the mental representation in your mind
to an endgame winning scenario.
The interpretation of what your goals are, where you are in relation to them and what kind
of actions you must perform to achieve these goals are what chess is all about.
It is a problem that must be addressed by you and you alone!
Categories
If you had attended the meeting of game strategists mentioned earlier, it is assumed that you know the rules and moves of the MPs and mps. What this means is that for you there is a
connection between one move and the next, so that, in a game of chess you seek
to confirm that the next move is in fact a legal move on that particular level of play. This
concept allows you to group MPs and mps into distinct categories. You group similar objects into categories
to recognize patterns on the board that happen in some regular way. Without this ability you would not be able to carry out the advanced
thinking necessary for playing chess.
These patterns of recognition can be seen on the board where they try to
repeat actions that are followed by desirable outcomes and avoid those that
result in undesirable one’s. Therefore,
it seems that all Chesmayne players’ have knowledge represented in their minds by assembling experiences
into categories at many levels of
abstraction, and label
these groupings and use the conceptual labels as the building blocks of their
thinking processes.
Grouping - Codifying
It is possible to convey a concept using gestures, that
is, when two deaf people sit down to play chess. Signs are used from which the players can inductively
arrive at the concepts being conveyed.
Thus the function of concept making is to increase your mental
efficiency, for without the economies of categorization your information
processing system would suffer from overload. Theoretically, there are tens of trllions
of possible moves on the various boards and if you did not reduce them to a
handful of groupings, incoming information would result in overwhelming visual
static in your brain. To resolve this
you compress and codify concepts to enable you to think and communicate
effectively. This process enables the
chess player to predict what move to make next on the board. You do this by eliminating most of the
unsuitable possibilities and concentrate on those moves that have promise by
means of your ability to categorize different moves on the board.
Hierarchies
Experts have many interconnections in their minds but
they approach problems from the top down which is the key to their expertise. Research also shows that you will remember items
more effectively if they are meaningfully organized than those you see in a
random order. Mature
players who remember large and complex bodies of material often say they do so
in a hierarchical way rather than starting at the beginning and working
straight through. The reason why the
mature player is so proficient is that it takes time and experience to arrange
and rearrange what s/he knows into a hierarchical form and this can only be
achieved through practice. Due to the
narrow limit of short term memory, you will work your way through a problem in
a serial fashion, but you will not use a trial and error search that blindly
looks at every possibility in a sequential manner. You will use a selective search - not an
exhaustive search. You process incoming
perceptions of the board, and while you have a limited computing power you can
store large amounts of knowledge and retrieve it at will. This shows that the only real way a chess player can improve
h/er game is through time and experience.
Seeing
What makes a mature player more proficient than the novice? It seems that the expert player can ‘see’ things that the novice cannot. De Groot conducted a number of studies to
clarify the role of perception in problem solving. He showed his subjects, mainly chess GMs, a tactical position taken from a tournament
game that had taken place between two GMs. The subjects were asked to determine :A’s best move. Coming up
with a good move involved a lengthy analysis of the board.
De Groot compared the responses of the GMs with the players who are one
rank lower and found that the lower ranked players could analyze the board
almost as well as the GMs. However, in
a real game situation the GM would win hands down.
De Groot examined this phenomena and found that the GMs explored fewer
moves than players with less ability. De Groot
concluded that the GM players were able to see certain moves better than the
lower ranked players because their interpretation and organization of the board
was more likely to be precisely accurate.
De Groot
De Groot also asked GMs to reproduce tournament
positions from memory. He found
that they could reproduce a position of greater than twenty MPs/mps after only five seconds. They did not place the MPs/mps on the board
one at a time but in groups of four or five MPs/mps in several chunks, where
each chunk consisted of a group of MPs/mps that were somehow related to one
another. It was found that the GMs
were not using a geographical code to place the MPs/mps on the board. They were using a more abstract code which
was dependent on their extensive knowledge of MP/mp configurations. From this it can be concluded that there are
stages in skill learning.
01 The first stage
called the ‘interpretive’ stage is used to ascertain what the task of the game
involves. Performance at this level is
error prone because the
knowledge is incomplete and can overload your working memory.
02 The second
stage of skill acquisition is called the ‘compiled stage’ during which parts of
your skill are chunked or compiled into a procedure that is specific to chess
playing. Demands on working memory are
much lower because the specific knowledge ie, allowable moves, which cell to move to etc,
fall into particular areas which can be interpreted by a general
procedure.
Able to see
A program should be able to ‘see’ the same things a
human sees when it looks at a chess board. It is a well known fact onlookers see more
of the game than the players! Thus the
program requires an internal representation of the cells and the MPs and mps on
a board and the relations amongst them, and a set of processes that can pick
off and make use of these relations as needed. The former requirement is called ‘setting
up the chess board’ and the latter ‘move making and matrix making
capabilities’. The game of chess
provides an inhomogeneous collection of information out of which moves must be
forged. Thus there must be enough
variety in the representation to discriminate all the different kinds of
moves. Given that, the information
should be stored in such a way that little space is allotted to moves that
seldom occur, such as mp
promotion (#), castling (%) and so forth.
Parallel processing
Another phenomena we must consider is also perceptual,
but of a more recent discovery.
Explanations in terms of heuristic search postulate that problem solving, and cognition
generally, is a serial, one-thing-at-a-time process. Many psychologists have found this postulate implausible and have
sought for evidence that the human organism engages in extensive parallel
processing. The intuitive feeling that much information can be ‘acquired at a glance’
argues for a parallel processor. Of
course, the correctness of the intuition depends both on the amount of
information that can actually be acquired and upon what is meant by a ‘glance’. If a glance means a single eye fixation,
lasting anywhere from a fifth of a second to a half-second or longer, then we
know that there are high-speed serial processes ie, short-term memory search
and visual scanning that operate with this time range. Thus, it is certainly interesting and
relevant to find out how the human eye extracts information from a complex
visual display like a chess position and to see whether this extraction process
is compatible with the assumptions of the heuristic search theories. Experiments have confirmed the existence of
an initial ‘perceptual phase’, earlier hypothesized by De Groot, during which
the players first learn the structural patterns of the MPs/mps before they begin to look for a good
move in the ‘search phase’ of the problem solving process.
Lists
A chessboard is made up of cells, which lodge MPs/mps,
which make moves from one cell to another.
Objects in Chesmayne, like the new boards and the palettes of MPs/mps, can be represented as names of
description lists with certain prescribed associations, such as the cell from
which a MP/mp comes, the cell to which it moves, and the kind of move in
question. A Chesmayne position can be
fully described as a list of moves that originate from a standardized initial
position (ISP) and terminate in a well-defined ++CM position.
To make a move
Moves are the operators that transform one Chesmayne position into
another. What are the common properties
of chess moves? Each involves a MP/mp,
or sometimes two (as in castling), going from one cell to another. If the ‘to cell’ is already occupied, the
move is called a capture. If the
‘to cell’ is on the top rank and the mp is a PA or, other mp, it is called a promotion (#). But in
all these cases the common ‘from-to’ property holds. Four steps are required to make a move in
a game of chess…….
Configurations
The configurations of MPs/mps in chess games are treated by the mature player in the same way as you
treat the configurations of letters in sentences. In fact, many
configurations have been given names, and are quite familiar to mature players. Games follow logical sequences of moves, and
when two experts compete there are systematic patterns to the configurations. By taking advantage of these regularities, GMs appear to have superior
mental abilities in looking ahead and in planning possible moves.
But this skill is actually due to their great familiarity with the :gt (game-tree) of traditional
occidental chess, which allows
them to view configurations of MPs/mps as single psychological units.
As an example of this, ask a traditional chess player
to play :L02 of Chesmayne (using eight GUs instead of eight PAs) or, Chinese Chess and you will find that s/he will be all-at-sea
(sea-sick!). Therefore, it can be
concluded that the novice Chesmayne player will have a sporting chance [an even
playing field] of defeating an experienced traditional chess player on the new
levels of play described in this text.
Familiarity is not easy to develop.
It takes years of study, many hours each day, to reach the level of
performance of a traditional chess GM. When
skilled traditional chess players are asked to remember meaningless board
configurations, as on :L02 or :L03 of Chesmayne or, even patterns of MPs/mps taken
from the games of unskilled players, their apparent superb memory and
analytical skills deteriorate very rapidly indeed, much as your ability to
remember letters drops considerably when they no longer form meaningful words
ie,
An example of the above paragraph is
given below with all of the vowels deleted:
s n xmpl f ths, sk trdtnl chss plyr t
ply :L02 f Chsmyn r, Chns Chss nd y wll fnd tht s/h wll b ll-t-s. Thrfr, t cn be
cnclded tht th nvc Chsmyn plyr wll hv sprtng chnc f dftng trdtnl chss plyr n th
nw lvls f ply dscrbd n ths txt. Fmlrty s nt sy t dlp. t tks yrs f stdy, mny hrs
ch dy, t rch th lvl f prfrmnc f trdtnl chss GM. Whn sklld trdtnl chss plyrs r
skd t rmmbr mnnglss brd cnfgrtns, s n :L02 r :L03 f Chsmyn r, vn pttrns f
MPs/mps tkn frm th :gms f nsklld plyrs, thr pprnt sprb mmry nd nlytcl sklls
dtrrte vry rpdly ndd, mch as yr blty t rmmbr lttrs drps cnsdrbly whn thy n lngr
frm mnngfl wrds.
Decisions-Decisions - Decision making
So far, we have only examined problem-solving. Another major category of mental activity
is labeled decision making. Here, a specific
choice of alternatives is offered someone who must then select one course of
action. Decision making is a part of
problem solving, of course, just as a problem plays a role in the formal study
of decision processes, that it makes sense to examine them separately. Decisions pervade our lives (ie, whether to
vote for one party/candidate in an election or another). We are continually faced with alternative
courses of action, each of which must be evaluated for its relative merits. Sometimes, the decision depends upon the
reactions of others, often chance factors are involved and sometimes decision making is
frequently accompanied by a perplexing mixture of success and failure.
Course of action
It is a very difficult
psychological task to compare several courses of action and finally to select
one. 1st - if each course
of action has any complexity to it, it strains the limited capacity of
short-term memory
simply to picture a single alternative and its implications, let alone carry
several in mind
simultaneously in order that they might be compared with one another. 2nd - if the alternatives are
complex ones, then there is no clear way to do the comparison, even if the
several choices could all be laid out one in front of the other.
And finally, there are always a number of unknown factors (other candidates) that intrude upon the situation. Some of the results of the action are only
problematical - who knows what will really happen? Some of the results of the decision depend
upon how someone else will react to it, and often that reaction is not even
known by the other person yet. It is
no wonder that the sheer complexity of reaching a decision
often causes one to give up in despair, deferring or postponing the event for
as long as possible, sometimes making the actual final choice only when forced,
and then often without any attempt to consider all the implications of that
choice. Afterward, when all is said
and done it is too late to change the act, there is time to fret and worry over the
decision, wondering whether some other course of action would have been the
best after all - proving that time and unforeseen circumstances befall us
all.
Cognitive limitations
Human cognitive limitations interact with human
actions. Thus, in our study of human
decision making, we have to be especially concerned with realizing the distinction
between the rules people ought to follow, and those they actually do
follow. The distinction can be
difficult to make, since wo/men often describe their behavior as deliberate and
logical, even when it is not. When a
wo/man makes a decision (ie, to get married) that appears to be illogical from
the viewpoint of an outsider, usually it turns out that the decision was
sensible from the position of the decision maker, at least in terms of the
information s/he was thinking about at that time. When the apparent error is pointed out to them ie, ‘why did you move your QU there?’, ‘now I can take your BS’, they are likely to respond that they simply
‘forgot’ some important information – ‘Oh damn (or some other vernacular
expletive), I saw that earlier on, but then I forgot about it’. Which behavior do we study - the actual
erratic acts, or the systematic, purposeful ones? The answer, of course, is both.
Strategy and tactics
The word strategy is derived from the Greek strategos, a root, that originally meant ‘trick’ or
‘deception’ and was used to describe army generals, that is, a general was one who could trick the
enemy. You will notice that a trick or
ruse indicates behavior, but a trick is more than just behavior. A trick means that a mental action or plan has preceded it.
Accidental tricks are not possible (‘Jape’ means prank or trick). A Chesmayne players definition of strategy must take these aspects into account. Strategies are seen in play, but this behavior implies some type of mental
effort. A strategy can also be defined
as a move, plan, or probe designed to effect some change on the board and provides information to the
players. That is, the move is
considered informative. In Chesmayne,
strategies are of two classes…….
In computer programs, opening strategy is simulated by attaching different values to different cells on the board.
By scoring points each time a MP/mp attacks one of the four center
cells (B$A), and one point for any other cell on the board, the
programmer simulates a view of the chess board in which the edges are less important than the middle. The difficulty for the machine is to
recognize when the center of gravity of play moves from the geometrical center
of the board (B$A). A human player
knows instinctively to move h/er MPs/mps towards the sound of gunfire. The central cells of B$A may only be a
useful stopping-off point on the journey of re-deployment.
The game is divided into strategy and tactics. The best
programs are excellent tacticians. Their
calculating ability gives them an obvious superiority over most
humans. They are less adept at evaluating positions and therefore you would avoid tactics, if
possible, when playing a computer in order to defeat the programme. The strategy to adopt is to do nothing, but
to do it very carefully, because sooner or later the program will dig its own
grave. Sometimes making a bizarre
early move can confuse a program and take it out of the ‘book openings’ programmed into it.
In other words, the interactions between immediate perception and stored knowledge are themselves complex and inventive beyond anything reproducible in computers, with
their yes/no logic and essentially static memory banks. Such key concepts as advantage, sound sacrifice, and simplification by exchange, on which the choice of moves will depend, are far
too indeterminate, far too subjective and historically fluid to be rigorously
defined and formalized. The vital
parameters of psychological bluff, of time pressure, of positional feel, of tactics based on a
reading of your opponent’s personality largely elude formal notation and judgment.
They belong to the unbounded inexactitudes of art.
Four simple rules
Computers
playing to a depth of, say, 100 ply will give chess GMs a hard game and they may even get to an objectively won
game, but they will not beat a mature player because they
will not know what they are doing.
They possess too much useless information which slows down the deep tree search. Can a program ever be written which will
embody all the concepts of Chesmayne?
Mathematically, a computer can perform so many equations. If it were possible to program a computer
with everything necessary for the game of chess, it would certainly have a
chance of crushing a human being. If
you are going to play a computer, there is no reason to be scared. There are four simple rules of engagement…….
Advantage of an electronic computer
Playing chess is a problem of a much higher intellectual
order for a computer and for this reason it was possible for some early
research to be done. The main advantage
of having a computer play chess lies in its ability to perform millions of
calculations much quicker and more accurately than a human being can. It has to have the ability to look ahead to
see the ‘variations’ that can be played. Checkers was also played by machines in the 1950s for the
first time, but the main problem was that the computer found the game too
easy. It could see through a sequence
of moves and captures to the final winning or drawn
position faster than
even very strong human opponents.
However, Chesmayne has an advantage over draughts in that it has MPs of
infinite value, the KI, GE, etc which gives the game a special character for
modeling real-life processes.
Related keywords to be found in this
dictionary…….
In the early days of computer chess, at the Los Alamos Scientific
Laboratory, on the Maniac-I computer, a chess variant was implemented, to be played by the computer. The
game is described in the book ‘Computer
Chess’ by Monroe Newborn. Three
games were played, and can be found in this book, the last one against a total
novice in chess, who lost the game from the computer. If your university library does not have a
copy of this (old) book, most of what is written there about this game and
its history, can also be found in
Pritchard’s
Encyclopedia of Chess Variants.
The game is
played on a six by six board. The
opening setup is as follows…….
White:
King d1; Queen c1; Rook a1, f1; Knight b1, e1; Pawn a2, b2, c2, d2, e2, f2.
Black:
King d6; Queen c6; Rook a6, f6; Knight b6, e6; Pawn a5, b5, c5, d5, e5, f5.
Pawns cannot move two steps on their first
turn. There is no castling. Other rules are as in orthodox
chess.
Jari Huikari has
made a free PC computer program that plays Los Alamos chess. You
can download it. Another computer
program, which can play Los Alamos Chess (Also by Jari Huikari) Download
it here
You can also take a look to an
experimental applet
where the game can be against oneselves, or an
applet where the computer plays against you.
Written by Hans
Bodlaender
Heuristics
Assuming that you have read the text and have played a
couple of different levels of Chesmayne, the question now arises as to what processes are
active when doing so. Having learned
how some of the new MPs/mps move you will probably have learned heuristic
principles of which the following are
examples:
Heuristics are rules that have been developed from experience in solving
problems. If you play chess, you probably know some of its heuristics, such as keeping
your QU in the center of action, keeping the KTs away from the edge of the board, and so forth. Unlike algorithms, heuristics do not guarantee the attainment of a
solution. They make up this shortcoming
by being simple and quick to use.
Cognitive scientists have discovered that the human entity often uses
several all purpose heuristics that do not appear to be closely tied to
specific problems. The origin of much
of this knowledge was the work of Newell and Simon.
A very important heuristic device is to find analogies
between the present problem and one’s for which the solution is known. Often, this requires a bit of skill in
recognizing the similarities and a bit of subterfuge in ignoring obvious
differences. Solution by analogy is
extremely valuable, even if the analogy is far-fetched. The danger, of course, is that one can think
there are similarities where in fact there are none, causing much wasted time
and effort before the error is realized and a new approach is tried. Heuristics come into play in any complex
problem-solving situation. In fact,
much of the study of thinking and problem-solving involves a search for the
kinds of heuristics people use. The
role of heuristic strategies is best understood by considering a specific
example ie, chess does not give a prescription guaranteed to lead to success. Rather,
it contains heuristic rules ie, try to control the four center cells (B$A) - make sure your KI is safe and so forth.
Subgoals
One of the main problems when playing chess is finding the particular operators that will work
in a situation. Breaking up the
overall problem into sub goals is useful for setting the problem up. The means-end analysis is useful for evaluating whether a given operator will make some progress
toward the solution. But none of these tactics tells us which operator we should be
considering. The mathematician Polya
suggests that to solve a problem we must first understand the problem and must
clearly understand the goal, the conditions imposed upon us, and the data. Second, we must devise a plan to guide us to the solution. But the crux of the matter is to devise
the appropriate plan, the operators that will, in fact, guide us toward a
solution.
Algorithms - Heuristics
In the study of problem solving, plans or operators
are divided into two types as mentioned above 1) Algorithms and 2) Heuristics. The
distinction between the two is whether the plan is guaranteed to produce the correct result. An algorithm is a set of rules which, if
followed, will automatically generate the correct solution. The rules for multiplication constitute an
algorithm. If you use them properly, you
always get the right answer.
Heuristics are more analogous to rules of thumb. They are relatively easy to use and are
often based on their effectiveness in solving previous problems. Unlike algorithms, however, heuristic methods
do not guarantee success. For many
of the more complicated and more interesting problems, the appropriate
algorithms have not been discovered and may not even exist. In these cases, we resort to heuristics.
Efficiency
In fact, the differences among
chess players seem to lie mainly in the power and efficiency of the heuristic
schemes they employ while playing the game. A good place to examine the operation of
these rules is with the last few moves
of a game, just before a ++CM
ie, an attack on your
opponent’s KI
from which it is impossible to escape.
If you consider all the possible moves and counter moves that are available
at any given stage in a chess game, there are about a thousand combinations
that could conceivably take place. The
number of possible sequences of eight moves, then, would be 10008,
which is a million billion, billion, if you care to spell it out. Were you to try to devise an algorithm for
evaluating the best one of these possible combinations, you would have to
explore literally billions of different possibilities. The sheer effort involved would overload
even the largest high-speed computer.
Selectivity
Chess players clearly do not try to follow through all
possible combinations to their conclusions.
They selectively consider only those moves that would seem to produce
important results. How do they know
which of the millions of possible moves should be considered in detail? Several studies of experts - those who have
reached the internationally recognized level of GM in traditional
occidental chess suggest that
these GMs use a number of heuristic rules to examine and select moves. The rules are ordered in terms of
importance, and this order is used to discriminate among promising moves. A sample of some of the heuristics used by
GMs gives an indication of how their search for appropriate operators is
guided……
Efficiency of heuristic schemes
These are simple rules. When they
are applied to a number of standard chess endgame situations, they succeed in a large number of
cases. Of more importance, they
succeed without requiring too much memory capability on the part of the player - only a
certain number of possibilities need to be considered in the exploration phase
of reaching the solution, even less in the verification phase to confirm that
the combination of moves is indeed valid and sound. Since the solution of some of these
problems might take a player 10 minutes to discover, they do not seem to
require a great mental capacity at any one time. In fact, the task would appear to be
equivalent to that of spending ten minutes in memorizing a grammatical
selection of words ie, the preceding three sentences. In conclusion it can be concluded that the
different levels of ability among chess players seem to result more from the
efficiency of the selective heuristic schemes they have developed, rather than from sheer
mental capacity.
A checkmating program
In any given position, what moves should be considered
and in what order? Human
players are known to be highly selective in the moves they look at, a
selectivity based on their heuristics of search. Computers must also incorporate such
selectivity. Restricting the mobility of your opponent’s MPs/mps is a recognized principle of strategy. It is
particularly important in ++CM combinations since ++CM is defined as an unopposed attack on an
enemy KI whose mobility has been reduced to zero. Strategically this means the attacker strives
to gain control over…….
If just condition 1 obtains, the enemy KI is simply in +CH. If just
condition 2 holds, the enemy KI is ++ST, while if both 1 and 2 hold, he is ++CM. Viewed in this light, ++CM is a process of
acquiring control or restricting the enemy’s KI more and more. This principle is the cornerstone of the
++CM program.
Algorithm
An algorithm is a method that
is guaranteed to produce an answer to a chess problem and although an algorithm
will not always be efficient, they always work.
You make use of algorithms whenever you play chess. For well defined
problems, we are often defeated in our efforts to find an algorithm because the
problem is so enormous. Chess is a good
example of a problem that is too vast to permit the discovery of an
algorithm. Starting from a conventional
opening position, the estimate is that a Chesmayne D-array (8 x 8 board, :L01), has 1040
continuations of games. If you had a computer capable of evaluating
each game at the rate of three per micro mille second, examining all the
possibilities would still take the computer 1023 centuries. The moral - don’t hold your breath waiting
for computers to discover the chess algorithm.
An algorithm is written which enables the program to generate a
significant portion of a problem’s branches.
The program then compares some or all of these branches systematically,
evaluating each branch against some criteria that have been stored as part of
the program. Elsewhere in the text
several of the programs that use some variation of the strategy outlined here and
how they are used to solve the problems are discussed.
Problem solving
Decision making implies a given number of
alternatives, whereas in problem solving the alternatives must be created. Thus,
problem solving involves both choice behavior and the finding or creating of
alternatives. In every chess position,
of course, the rules of the game place an upper limit on the number of possibilities
that can be created. De Groot found
that, (on an 8 x 8 board, :L01) averaged across the course of a game, the mean
number of legal move possibilities lies somewhere between 30 to
35. How do you build a search-tree? How are
the limbs and nodes, moves and positions structured into a tree of
possibilities? The chess player can be
compared to climbing a tree as s/he builds it.
Crawling along a branch in one direction corresponds to making a move in
the current position (node), while traversing it in the opposite direction
corresponds to unmaking a move and restoring the previous position (node). As the player builds and climbs s/he also
accrues and retains information. The
information garnered en route and the use to which it is put are in large part
what can be called ‘the development of the problem’.
Tree searching
The following paragraphs describe the results of
applying the formal heuristic search algorithm to the game of traditional
chess, and the impact of this
work on the theory of heuristic search.
It is not that the application of the heuristic search can by itself
solve the problems at the heart of computer chess, but that representing these
problems with the formalism of the heuristic is proposed that does offer a
common solution to the problem of quiesence, sacrifices, and plan-oriented play.
Zobrist and Berliner
Computer chess has been dominated by programs using the alpha-beta
minimax search and more recently by programs using an exhaustive search. The trend of successful programs has thus
been to a more brute-force approach rather than developing more formal
solutions to the difficult problems that arise. Approaches using more sophisticated
representation and utilization of knowledge such as those of Zobrist and Berliner have been
unable to perform competitively with programs using the alpha-beta
technique. The actual assessment of
new approaches is hampered by the fact that a chess program hangs by its
weakest link, and poor play may not be the fault of the new approach. It is by no means clear than in chess if
the trade-off of search effort for accuracy in evaluation can be consistently made without significant loss of
precision. Thus the speed of the heuristic search - an attempt to combine a sufficiently
powerful search mechanism with a knowledgeable heuristic. The heuristic search approach has not proven
itself competitively superior to the alpha-beta technique either, winning, drawing and losing.
Evaluative categories
Classical game theory partitions the set of legal positions into evaluative categories: ++LS, ++DR and ++CM. Yet commentators employ a much larger repertoire of evaluative terms than this, distinguishing for example, a ++DR
from a balanced position, a decisive from a slight advantage, an inaccuracy from a mistake and a mistake from a blunder. Using this, an additional quantity can in principle
be associated with each position, so that we have not only its ‘game heuristic value’ but also its expected utility. A function of these two variables can be
found which yields explanations for many evaluative terms used by
commentators. The same model can be
used as the basis of computer play.
It has shown itself to be easier to justify, and to adjust to realistic
situations, than the minimax model on which some state of the art programs are
based.
Helmut Richter
Almost every chess program ever written uses some sort
of look-ahead. Perhaps the most notable
exception is Helmut Richter’s program ‘Schach’. Since the game-tree [:gt] for chess becomes enormous within only a few ply
(half-moves) of look-ahead, a considerable amount of research effort has been
devoted to the problems of tree searching.
The contribution by Birmingham and Kent provides a concise summary of
the fundamentals of tree searching. A
paper by the authors of ‘Kaissa’ gives an account of their interesting ‘method
of analogies’ which aims to use information gained from one part of the search
tree in analogous positions.
Larry Harris in his paper described how the
intelligence of heuristic search can be applied to chess programs, and how the
method may be used to find sacrificial combinations or, to defend against them. Donal Michie’s paper breaks away from the
classical traditions of game theory and utilizes the fact that chess players
are imperfect to show that it is not necessarily best to assume that one’s
opponent will always find the correct move.
Michie’s contribution has been underestimated, and could be extended to
enable a computer program to play ‘psychologically’, making moves which were thought to be stylistically unpleasant
for a particular opponent.
Razoring
This technique works on the assumption that from any
given position your opponent will be able to find at least one move that improves
h/er position. This assumption is invalid
in the context of chess if a ‘zugzwang’ situation occurs.
In fact the program defines zugzwang precisely as a state in which every
move available to one player creates a position having a lower value to h/er (in its own evaluation terms) than h/er present position. Razoring is a new and very powerful technique
for speeding up mini-max searching.
Unlike alpha-beta it will not guarantee finding the best decision but it
will, however, find a very good move far faster than alpha-beta.
Chopper
When playing a game a program has to search a sequence
of trees, and occasionally one of the trees in a given
sequence will have a single node at ply-1.
It is well worth while to test for such an occurrence, otherwise the program
will search through more plies, only to decide that its only choice is also its
best choice. So long as the value of the tree is not required, but only the decision
about which move to select, you can chop the tree off at ply-1 and
the only move available. This situation
occurs when the KI has to move out of +CH.
The alpha-beta algorithm, sometimes misnomered heuristic, has been a standard component of every modern game
playing program. It was apparently
first used by Newell, Simon and Shaw.
In the search for a suitable next play, a move is discarded if it leads
to a value which is worse for the side to move than some already considered
move. If we look, however, at two
levels of the tree (say, moves by :A), followed by replies from :B, we notice the following: as moves by :B are being
explored, the value which is going to be returned back up to the :A
level (:B best value so far), cannot be getting worse and worse. If an :A move has already been evaluated, it is possible to check a :B move not only to see
if it is so good for :B than some alternative, but also to see if it is so good
for :B that :A would never make the move leading to that choice for :B, or in
other words: whether the move is ‘too good’ for :B. If the move is ‘too good’ it is useless to
consider any more moves for :B from that position and the :A move leading to
that position may be discarded immediately.
Thus, only one refutation is required to a proposed move and once it is
found further search may be discontinued.
Alpha Beta
cutoff
The probability of alpha-beta cutoffs is increased by
the fact that moves are investigated in order of decreasing plausibility, and a
move is refuted if it is equally good as the best so far at the previous
level. Such a consideration leads to a
tremendous speed-up of the search, especially if what turns out to be the best
move at each position is considered first.
One of three attributes of the plausible move generator is that it
usually assigns the highest plausibility score to the best move, so almost
maximal advantage is gained.
Calculation shows that the workload of the search is reduced
considerably. The name ‘alpha-beta’
is derived from the fact that in the classic implementation of the algorithm, two recursive variables are kept…….
Game tree :gt
I think that I shall never see, A poem lovely as
a tree, A tree who’s
hungry mouth is pressed, Against the earth’s sweet flowing breast, A tree that
looks at God all day, And lifts
her leafy arms to pray. A tree that may
in summer wear, A nest of robin’s in her hair, Upon who’s bosom snow has lain,
Who intimately lives with rain. Poem’s are made by fools like me, But only
God can make a tree.
The game of traditional
occidental chess contains about
1046 positions, a substantial proportion of which are terminal. The rules of the game assign a value to every terminal position according to whether the
position is ++WN, ++DR or ++LS for :A. These
values can be backed up the game tree using the minimax rule, so that in
principle every position can be given a value, including the initial position (ISP). This last
is known as the ‘value of the game’, and is conjectured to be zero for Chesmayne. If this
conjecture is correct, and if both sides play faultlessly, ie, only execute
value preserving moves, it follows from the ‘back-up’ method of assigning
values, that there is at least one such move available from every non-terminal position, then the
game must end in a ++DR. Traditional
chess has been honed into
the game we play today. The old board of
64 cells is still there, standing silently in tribute to the genius of its inventors and players.
In the last few decades the computer has been applied to address some of
the :gt (game-tree) problems that have arisen in chess and
many insights have emerged from the woodwork.
A game-tree (:gt) of Chesmayne (the Level of play ie, :L01, 02, 03 etc).
The programming structure which enables a program to play chess is
called a ‘tree’. The
program’s task is to decide on a move from a given position, and it represents that
position as the ‘root’ of the tree.
Each of the possible moves from a position is represented by a ‘branch’
of the tree and at the other end of a branch is the new position. Growing a tree to represent the myriad
possibilities on the chessboard is a straightforward task, accomplished by a
module in the program called the ‘legal move generator’. What is much more difficult for a program
is accurately evaluating the positions that arise on the tree. Without a reasonably sensible ‘evaluation
function’ a program could look a long way ahead but have little or no
understanding of what it was looking at.
Clearly some chess knowledge is needed in the evaluation function but
representing such knowledge in purely numeric terms is far from simple. With little knowledge at its disposal, an
evaluation function will provide only a crude, often erroneous distinction
between good positions and bad ones.
With a lot more chess knowledge the evaluation function becomes much
more accurate, and will sometimes be able to pick the best move in a position
without using a look-ahead. One of the
problems facing chess programmers is that evaluation functions with more
knowledge require more time to compute, reducing the depth of look-ahead than
can be achieved within the allotted time per
move. A search which thereby becomes too shallow
can lead a program to make tactical oversights, unnecessarily losing material or
succumbing to ++CM.
Evaluation function
Evaluation
functions in games playing programs are also employed to determine which moves
a program should examine, making selectivity possible. With an average of 37 moves in a chess
position, it is easy to comprehend that the problem of looking ahead to a
significant depth can be immense. After
only one move by each side there are more than 1,000 positions to evaluate. After two moves by each side the number
rises to over 1,000,000. Deep
Thought, by using some clever
programming tricks, looks at everything at least five moves ahead by each side,
and it examines the tactical
variations which it considers most interesting to a depth of
10, 15 or even more moves by each side.
In contrast to these telephone numbers a strong human player will typically
evaluate only 50-150 positions during a three minute analysis. Herein
lies the big difference in thinking between human GM and computer GM - humanoids know which moves to
select for examination. H/her
evaluation function is sufficiently knowledgeable.
Deep Blue versus Gary Kasparov
It is possible to summarize the difference in thinking
between ‘Deep Thought’ and Garry
Kasparov thus: the computer
performs the task of evaluation fairly competently but not brilliantly, though
it does so millions of times whenever called upon to decide on its move. In attempting to emulate and surpass human
GMs it performs its task of evaluation less intelligently, in the chess sense,
but it does so much more often.
Kasparov’s evaluation function is fine-tuned to the point of perfection,
but he needs to apply it less than once per second. He uses his accurate evaluative skill to
select those moves which deserve to be considered, and to prune out the
dross. This highly selective search
enables Kasparov to keep the size of his own game tree to within manageable
proportions. Kasparov played IBMs Deep
Blue program in February 1996. The
match was over six games with a prize fund of $500,000. Deep Blue had a powerful new set of chips
working in parallel which can analyze 10 million positions per second and was 100 times as
powerful as the machine then in use. Another
chess computer ‘Star Socrates’ (USA) has over 1800 processors working in
parallel but was defeated by Fritz which only has a Pentium processor!
Selective search and brute force
Because chess programmers have not yet been able to
encapsulate all human chess knowledge in numeric evaluation techniques, the art of chess programming has largely relied on ever
faster hardware. Deep
Thought uses a microchip
designed specifically and only to play :L01 and which performs the tasks of move generation and position evaluation at amazing
speeds. A debate has long raged
between two schools of chess programmers: which of ‘selective search’ and
‘brute force’ should be the more successful strategy? At the
moment the brute force school is winning, so one needs to ask the question ‘is
mere brute force alone enough to defeat Kasparov?’ There are
those, including Deep Thoughts designers, who believe that existing evaluation
techniques, together with an extra 2 moves of look-ahead for each side, will be
sufficient to create an electronic monster strong enough to challenge the
human World Champion. Others,
notably the stronger chess players within the computer chess fraternity,
believe that greater selectivity ie, more embedded chess knowledge, will be
required.
10,000 chess programs
Amongst the thinking games that have been programmed, chess has been witness to
some of the greatest successes. It is
estimated that some 10,000+ people have written chess programs. More than 20 books, dozens of university theses and hundreds of
academic papers have appeared on the subject.
This information has been available for those who have programmed other
thinking games, with the result that human champions have been vanquished in
activities other than chess, but in most cases the ‘thought processes’ of the
programs have been very different from those of human players.
List of annotator’s comments
General considerations
A chess ‘position’ may be defined to
include the following data…….
No chance element
In chess there is no chance element apart form the original choice of which
player has the first move. Each
opponent has perfect information at each move as to all previous plays. These two
facts lead to the following conclusions…….
Evaluation function
From the above we can infer an
existence theorem. No practical way is
known for estimating which of the three categories a position belongs and if
one were discovered the finale of a game between :A and :B would be exactly
determined at the outset of the contest.
In some games there is a simple evaluation
function (P) which can be applied to a position (P) and whose value
determines to which category ie, ++WN, ++LS or, ++DR the position (P)
belongs. In typical chess positions
there will be 30 or so legal moves (:L01, 8 x 8 board). Thus a move for :A and then one for :B gives
about 103 possibilities. If a
typical game lasts about 40 moves (8 x 8, :L01), before ++CM or ++RS of one side then
there are 10120 variations to be calculated from this initial
position (ISP).
Evaluation function f(P)
In chess there is no known simple and precise evaluating
function f(P) and never
will be because of the rules of the game, but it is still possible to perform an approximate
evaluation of a position. An
evaluation will be based on the structure of the position, the number and kind
of MPs and mps, formations, mobility, etc. The
more mature you are as a player the more successful will be your
evaluations. The values of the MPs and
mps and other factors when totted-up will determine which side has the largest
total and the leading position.
f(M1P)
In actual play this translates into a position where
for example the side with a MP advantage will have an easy win and if having a mp advantage will have a difficult
time trying to win. The side with the
MP advantage will have many ways to win while with the mp exact play may be
required and a single error of judgment will negate this advantage. A simple evaluation function can only be
applied to quiescent positions, that is, in an exchange of MPs ie, MP capturing MP. It would
be ridiculous to calculate the function of f(P) after the MP capture because
your opponent will immediately recover the value just lost.
More terms have to be added to f(P) to account for exchanges of MPs/mps
in progress and is in fact the method which chess players use in actual
play. You will choose the variation giving you the highest evaluation. Thus your maximum evaluation can be
expressed as f(M1P) where M1 is the selected move.
f(P)
Evaluation
Function: can be applied to a position ‘P’ and whose value determines whether a
game is ++WN, ++DR or, ++LS,
When it is the computers turn to move it calculates
f(P) and chooses that move giving the maximum value to ‘f’. A cell on the chess board can be occupied in one of many
different ways, empty - occupied by an :A MP - occupied by an :A mp - occupied by a :B MP -
occupied by a :B mp. In traditional
chess (:L01
Chesmayne) there are 13 different ways in which a cell can be
occupied: empty, by one of the 6 :A MPs/mps - by one of the 6 :B MPs/mps. On :L02 of Chesmayne there are also 13 different ways in
which a cell can be occupied. On :L03
each player has 7 types of MP/mp to start with instead of the usual 6 of :L01
or 02. If a computer always made the
same move in the same position this would always lead to the same game.
Statistical element introduced
To prevent this a statistical element is introduced into the program. When there are two moves of equal value the
machine chooses the move to be played at random. In the same position in another game it
will choose another move of equal value to be played. In this way a number of standard openings are stored in the computers memory. For the
first few moves the computer plays its moves from this memory bank which is
just the same way a chess player goes about selecting h/er moves. The computers ‘style of play’ can be changed by altering the factors involved in its evaluation
functions. The strength of play can be altered by
adjusting or changing the depth of calculation and by omitting or adding terms
to the evaluation function. However,
the main weakness of a computer program is that it does not learn by its
mistakes. Do you?
Higher level program
The only way for a computer to improve its play is by
improving the program itself. One way
is to have a higher level program change the terms involved in the evaluation
functions which in turn would depend on the results of previous games that it
has played. A chess player has knowledge of hundreds of situations that can arise on the
board stored in h/er brain and in a given position recognizes a familiar
situation which directs h/er mental calculations along lines with greater
probability of success. In a similar way
the data in the computer program is triggered to use various other programs
depending on the particular nature of the position encountered and in this way obtains
suggestions of plausible moves to investigate. A computer is strong in speed and accuracy
and weak in analytical ability and recognition.
Plausible move generator
It has three basic goals…….
Plausible move generator
The analysis done in the plausible move generator is done on a per
move basis rather than a per position basis - that is, for example, ‘this move
is bad because it blocks A-BS2’ rather than ‘the position resulting after this move
is bad because A-BS2 is blocked’. To
determine the latter fact starting just with the board position would require
considerably more processing and analysis of irrelevant details. Numerous ‘heuristics’ are available for the plausible move
generator. As is frequently the case with
heuristics, they may not be valid in particular situations, therefore a program
organization is required which allows for the interaction of the heuristics to
determine which of them most nearly applies in the current situation. Very generally speaking, two types of
heuristic interaction are used in a chess program and these are given
below.
Enumeration
One type of interaction involves enumeration of all
combinations of facts. Such an
enumeration leads to the familiar tree structure with the nodes of the tree corresponding to sub-decisions. Each node is dependent upon only one
fact. The size of this tree grows exponentially
with the number of facts involved, severely limiting the usefulness of this
technique.
Weighted sums
The second type of interaction uses weighted
sums. A value is assigned to each fact
proportional to its average importance, and each move is scored as the sum of
the weights of the attributes which apply to the move. In the simplest case, the move with the
highest score is chosen. The
complexity of this process grows linearly with the number of facts - not
exponentially. Also there is
opportunity for a large number of small factors to add up and sway the final
decision in a way hard enough to achieve with the enumerative process. While it is true that any linear weighting
process can be simulated by an appropriate enumerative process, for large
numbers of facts the size of the enumerative process becomes absolutely
unmanageable. So, for practical
purposes the techniques are distinct.
Linear weighting methods have been used before in game playing programs
- nevertheless they have a weakness in that they basically fail to take into
account the relationships that may exist between the facts. To put it another way, the importance of a
fact may vary depending on the position.
Non-linear techniques have been proposed to solve this problem, but
chess is a game where the relationships are so complicated and numerous that it
is unlikely much additional headway could be made by making the weighting
nonlinear.
Fifty identifiable heuristics
In most programs 50+ identifiable heuristics are used in computing the plausibility. Many, though, apply only in special cases
such as capture, moves with certain MPs/mps, or certain stages of
the game. Each cell is assigned an importance during each plausible move
computation, corresponding roughly to the estimated worth of having an
additional MP/mp bearing on the cell or the cost of taking away a MP/mp
presently bearing on the cell. The
principal criteria used for assigning these values include the closeness of the
cell to B$A, its proximity to the opponent’s
KI, and its occupation by one of your MPs/mps which is
‘en
prise’. Small values are given for occupation of
the cell by one of your MPs/mps and for its closeness to your opponent’s side
of the board. The current developmental value of a MP/mp is the sum of the values of all the
cells it attacks (can move to in one move) plus values accumulated for actual attacks on enemy MPs/mps.
The new developmental value is similarly computed assuming the MP/mp is
in its proposed new location. The
difference between these is used as a factor in the plausibility, encouraging
developing moves and discouraging apositional moves. Gains or losses in development resulting from
blocking or unblocking the opponent’s or, your own MPs/mps are also considered
in the development value. Of course,
putting your opponent’s MPs/mps ‘en prise’ is plausible. Furthermore, factors are added to encourage
certain types of attacks on weak spots (weak mps, pinned MPs/mps, MPs/mps defending other MPs/mps, etc). When a capture is made, the capturing move receives the
developmental value of the MP/mp captured.
Some very specialized heuristics also are employed, such as, ‘it is bad to move
MPs/mps in front of center mps on their original
cell, thereby tending to
block your own center’. Sometimes an
apositional move will receive a high value because it is an attacking
move. If this leads to gain, all is
well and good - but, if your opponent can simply move away then the move is a
pointless waste of time. So, moves are
scored separately on their positionality and if this is bad these moves are
rejected if there is some other move which leads to an equal terminal score.
Phases of a game
A game of chess can be subdivided into three distinct
phases, the &O, :MG and :EG. Different
principles of play apply in these phases.
The opening phase takes up the first dozen moves and will entail the development of your MPs and mps.
Tactics, strategy and combinations will come into play during the middle game phase and
will continue until most of the MPs and mps are exchanged, leaving you with say, A-KI and a few A-mps and one or two :B MPs. Promotion of mps, ++ST, zugzwang and so forth will comprise the endgame phase. A cell on the board can be occupied in many
ways: empty or occupied by any one of the :A or :B MPs or mps. A move is specified by giving the original
and final cell occupied by the choice of the
board you have chosen for
play.
Evaluation
function
The evaluation function f(P) is hard to define as many
features of an actual position will be on the borderline. The following is a selected sample of those
which you will have to take into account…….
All of the above factors come into play in the :MG but different principles apply during the :&O
and :EG
and the values given to each of the above statements becomes nebulous.
Position evaluation
Every program contains an evaluation
function, sometimes
called a scoring function, to assess the merit of the positions that it
encounters during its search for a move.
Many of the features employed in these evaluation functions are described
in previous paragraphs. Slater
produced a paper that was the first to attempt to quantify the significance of mobility in chess.
He studied the relative mobilities of the MPs/mps in a number of GM games, and his data provided clear evidence as to
the importance of employing mobility as a feature in position evaluation.
Turbulence
Good’s work was rather more radical. He provided logical arguments to show why
particular features might be quantified in a certain manner. He also introduced the notion of turbulence,
which has never really been employed in programming, even though it is a
significant factor in human chess thinking. A human
GM might well say to him/herself, ‘In a position as sharp as this it would be
dangerous to leave my KI in the center’, whereas a computer program does not
typically make its weightings of certain features dependent on the presence or
absence of others. Perhaps non-linear
evaluation functions will become popular at some future date, in which case
some of Good’s ideas will come to the fore.
Value of the MPs/mps and cells
A satisfactory theory of the value of the positions should include a theory for the
values of the MPs/mps as a special case. So it is worth while to look for a theory
that gives reasonable values to the MPs/mps.
Then we could try to generalize the theory. The values of the traditional
chess MPs/mps - RO, BS, KT, QU and PA have been found by experience to be approximately
proportional to 1, 3, 3, 5 and 9. A KI is worth about 4 in the endgame. These
values vary with the position and with the number of MPs/mps on the board. For example, two KTs are worth less than a
RO when the only other MPs/mps on the board are two KIs, in so far as two KTs
and a KI cannot force ++CM against a lone KI.
But the values given are applicable rather widely. For example, two KTs are about the equal of
six PAs on R$02 even when the KIs are removed. A
theoretical attempt to evaluate the MPs/mps was made by H.M. Taylor in 1876. The value of a MP/mp is taken as
proportional to the average number of cells controlled, averaged over all cellular positions of
the MP/mp on the board. This argument
leads to the relative values of KT, BS, RO and QU as 3, 5, 8 and 13
respectively.
Coxter and Taylor go on to modify the argument by asking
instead for the probability of ‘safety’ giving +CH, that is, without being en
prise to the KI, if the
MP/mp and KI are both placed on the board at random. The MP/mp values seem to be valid when
there are no KIs. Consider, for
example, a MP/mp called the ‘Galactic Emperor’, that controls all the cells on the board. When the KIs are on, he is worth at least
seven QUs, on an open board.
Therefore a theory that allows for the presence of the KIs is too
difficult to start with, and that it is more sensible to try first to obtain a
theory that arrives at the known values without reference to +CH.
Control of cells
The number of cells dominated by the QU and the fact
that the RO and BS have overlapping fields of influence needs to be taken into
account. For example, a RO on $D05 and a BS on $C06, on an open 8 x 8 board,
dominate only 24 cells instead of 27, and so lose about one ninth of their
value. This gives a partial
explanation of why the QU is worth more than a RO plus a BS. A similar argument explains why two BSs
are worth more than a BS and KT, or than two KTs. It is usually better to control two cells
than to control one cell twice, not allowing, of course, for the different
values of cells.
The initial position
The initial position (ISP) can be examined in its own right, as indeed can any
given position. But it would be too
short-sighted to say that ROs, BSs and QUs have no value in the initial
position (ISP), merely because they cannot move. It would
be more reasonable to make some guess concerning the probability that each
MP/mp will occupy the various cells after any given number of moves, and then
to use these probabilities as weights in a weighted average of the number of
cells dominated. To make the theory
more accurate we attach a value to each cell, making the central
cells more valuable than the
others. To do this we can use a similar
principle to the one used for MPs/mps, that is, we can find the average number
of cells from the cell when various MPs/mps are placed there.
New MPs/mps
Theories of evaluation of MPs/mps can be tested by using new
MPs/mps as in Chesmayne. We are not
inevitably tied to the small sample of distinct kinds of MP/mp that occur in traditional
occidental or oriental
chess. An example of this test was given above in
connection with the ‘Galactic Emperor’, although perhaps this MP is too extreme for most purposes. Positions for which there is no move
forceful or purposeful enough to be worth analyzing were independently described as ‘quiescent’ by Shannon and Good and ‘dead’ by Turing. One
objection to this term is that a ‘dead ++DR’ is a standard expression among chess players.
Also it is useful to be able to refer to ‘degrees of quiesence’, whereas
‘degrees of deadness’ sounds facetious.
A good name for the degree of quiesence is simply the ‘quiescence’ of
the position, or inversely one might refer to the ‘turbulence’. A quiescent position is one of low
turbulence, a combinative position is one of high turbulence. It is also possible to define turbulence
with respect to goals other than material balance, such as control of the center (B$A).
Endgame (:EG)
:EG literature contains erroneous evaluations by experts.
Some computer experiments have already revealed errors and omissions in
the published theory of the endgame.
However, this imperfect knowledge has not prevented GMs from achieving ELO
ratings of 2800+.
The conclusion seems inescapable: it does not take perfect play to be a GM. Although
the output of a chess machine looks like the output of a chess player, what do
we know about their respective thinking and computing processes? This is important because we want to explain,
if possible, the differences in playing strength between an average chess
player and a GM in terms of differences in concepts in which the former is
lacking. Such concepts might be
embodied in ad hoc procedures.
Barbara Hubermann
It is well known that computer programs play far less
strongly in the endgame than they do during the earlier phases. This is because the endgame requires a much
deeper understanding and far more long range planning, and these are aspects of the game which have not yet been converted into computer
programs. Some of the earliest work on
:L01 endings was written by Barbara Hubermann at Stanford
University. She did not discuss the
endgame in general, but concentrated her efforts on the problem of extracting
information from a chess book in such a way that it could be programmed. In this sense, Hubermann was one of the
early ‘knowledge engineers’ in the field of ‘Expert Systems’. Her work was to program the endings: KI and RO versus KI, KI and two BSs versus KI; KI, BS and KT versus KI.
She did this using the concept of ‘better than’, so that her program
could make simple comparisons between the merits of various positions. Kenneth Church of M.I.T., has mentioned a
particular class of PA endgames, called co-ordinate cell problems, and
generalizes from blocked PA formations to less specific KI and PA
endgames. Church’s work has planning
implicitly built-in, and it is a significant advance to have been made in
endgame programming.
Style of play
Computer programmes often blunder
in the endgame, and at other times see combinations and manoeuvres so ingenious that they would probably
not be thought of by human players as emenating from a computer programme. Computers tend to be good where the
average human player is weak and weak where the human player is good. But how does a computer play chess? Why do they play in a different style to
human beings? Actually, how a computer
is programmed affects its particular style of play and its weak and strong points. A machine obeys a programmed set of
instructions which enable the computer to store and handle data, which they do
in the form of binary information representing chess moves and positions.
Computers have the capacity to
calculate deeply and accurately.
Advantage of the computer
What is difficult for a computer is to make a really good, subtle, strategic move, because that involves long-range planning and
a kind of indefinable sixth sense for what is right in a position. This sixth sense, or instinct, is what
really sorts out the wo/men from the boys/girls on the chess board. Computers do have certain advantages over human players. The best constructed programs will never
commit simple blunders, such as leaving a MP/mp to be captured for nothing, or overlook a ++CM in one or two moves. The computer will never fall victim to
fatigue or inattention, and it will store and retrieve thousands of specific opening
variations better than a human player. Most other differences strongly favor
sentient human beings.
The differences are not so much in general processes
of learning or thinking, but in weighting or, various specific criteria for
move selection, that is, in evaluative
functions. It comes down to massive ‘tree-search’ versus focused or restrictive search. In contrast a human player considers very few
first moves, sometimes only one. The
difference between computers and humans in learning capacity is perhaps the
hardest of all for computer programmers to take into account, notably the
relatively strict depth limitations versus flexible depth analysis.
Perception operates in two main areas, generating plausible moves and
statistically evaluating terminal positions.
Not only will a plausible move be generated more quickly by the mature
player, but h/er long experience with many patterns on the board - 50,000 or more, translates into the advantage of being able to evaluate the resulting position
more readily. Programs do not of
course think (they compute), or perform a set of instructions. The principles on which they operate give
them a different and distinctive style of play, with its own strengths and
weaknesses. A chess player plays the
wo/man and not the board, which is opposite to what a computer does.
Positional programs
In recent years the effort has mostly gone into
positional programs and into the special programs of the endgame. An algorithm is defined in the dictionary as a series of
instructions or procedural steps designed to result in the solution of a
specific problem, that is, the first stage of programming which precedes
detailed programming and coding into a language that a computer
understands. A human player, deciding
on h/er opening repertoire, needs to find &Os, &Ds and &OVs of those openings and defenses, which enable h/er to
cope with the most common situations that h/er opponent is likely to force h/er
into. In Chesmayne this will call for a program to be able to offer on-line
assistance to a human player, particularly on the higher levels of Chesmayne,
that is, on the larger boards with many more combatants on each side and when
new rules affect the conditions of play.
Opening repertoire
A program has to be given some form of opening repertoire.
A computer which always plays the same opening and defense would become predictable. A player needs practice in a wider range of
openings and defenses. In Chesmayne the
sky is the limit. It will also need a
repertoire of some depth, both to avoid traps and to set it on the path to a decent middle
game and endgame
scenario. A large opening repertoire
needs a large amount of ROM. However,
sooner or later the program will run out of its book knowledge. This can occur early in a game, if the
opponent plays a move not in its ROM book. The computer will also need to be given
information on how to develop moves, castling (%), central control, which exchanges to make and how to handle MPs and mps and all the
other new Chesmayne concepts.
Positional evaluation is another problem a programmer has to contend
with. A method of choosing between possible
positions has to be incorporated. The
simplest form of evaluation is a purely material one, that is, mp = 1, QU = 9, KI = 250 and so forth. With this crude material evaluation, all
one then does is instruct the program to calculate the material for both sides at the end of each variation searched and try to obtain the maximum material win or minimum material loss. To make
it a little more subtle, a ratio system can be added to distinguish between
positions with the same material advantage.
This will enable the program to exchange when it is ahead and avoid exchanges when
behind.
Horizon
How far a computer sees ahead is also a very important feature. What is its horizon. The so called
‘horizon effect’ is a problem that is encountered by almost all computer
programs when they try to analyze opening variations.
Computer programmes search to a fixed level or number of moves ahead
(ply) and will not see captures or other threats beyond that particular depth. This is responsible for the occasional
inexplicable blunders that they often make.
Claude
Shannon back in 1948 predicted
that this problem would arise and particularly so, on the higher levels of Chesmayne. The method
to fix the ply-depth search which he proposed was to continue with analysis so long as there were still +CHs and captures and to only count material when a quiescent position was reached. Most of the powerful programs adopt this
methodology of analyzing variations, but only to a limited extent. If you analyze until four-ply in every
possible position arising from the position you have, that is, 20 possible
moves each time, this means 160,000 positions at four-ply. What is sometimes done is to examine only
non-quiescent positions. If you define
a quiescent position as one in which the player to move cannot make a capture,
or give +CH, or promote a mp, then you will keep the analysis to manageable
proportions for the programmer and the computer.
Speed control
If further classes of threats are included, that is, threat to capture, threat to ++CM, threat of promotion on the next move, then the program would start to
see forks, pins, skewers and other kinds of tactics further ahead.
For this a much faster processor will be required. Computers, despite the limitations imposed
by the horizon effect, will still calculate consistently better
than most human players. Their
sharpness in short-range tactics makes them particularly formidable at blitz play, because the reduction in the time
for thinking hurts human
players more than it does computers.
Computer manufacturers introduce ‘speed level’ and positional heuristics according to the sophistication required at each
level. Time cut-offs lead to
inefficient play by a computer program.
These factors are not in themselves enough.
Something extra is needed to help the computer play
sensible moves rather than choose at random between continuations that have the
same material evaluation x-ply ahead.
It is necessary to bring in weightings for moves that control central
cells, increase mobility, improve KI safety and further desirable goals such as the creation of passed
mps. Negative weightings are given to moves that
leave the machine with doubled
mps, backward
mps or isolated
mps, put MPs on a closed file or, KTs on the edge
of the board. Giving the right weightings to the various
strategic and positional factors will be one of the hardest
things to do in Chesmayne, as most chess players know to their cost. Computers are better tacticians than they are positional players. The trouble is to express the factors in
terms of rules without making them so rigid that the computer never
recognizes exceptions. The hallmark
of a mature player is that s/he knows when a weak
cell is significant and
when it is irrelevant to the position.
Endgame (:EG)
It is a cliche that computers play endgames appallingly badly.
Another problem in programming the endgame is what to do with the KI, who is tucked away for safety in the middle
game, but in the endgame is
needed as a fighting MP, which generally means centralizing him. The
problem of dealing with passed mps is even more difficult. It is hard to teach a beginner how to
calculate several moves ahead whether a mp can be captured with the KI or not. To attempt to analyze every possible move in a position under
consideration is not the human way.
Experienced human players restrict their analysis to just a few moves
which they immediately recognize by experience to be the most promising choices
and may also quickly check out a few other tactical possibilities to ensure
against oversights. A lot of moves
will be rejected subconsciously or instinctively by a human player. Thus a large number of retreats and moves
that retract the previous move tend to be discarded within a few seconds. This is a particular failing that a
computer sometimes manifests.
Programming ingredients
The rest of the time the human player selects a small number
of candidate moves, probably no more than three and begins by analyzing the one
that s/he wants to play. In this
way the width of the search is cut down drastically from the start and the
human player can concentrate on achieving sufficient depth in h/er analysis and
positional evaluation. This is called
‘selective search’ as opposed to the ‘full-width-search’ which considers every
legal move.
Sometimes obviously bad moves turn out to be good moves and good moves
turn out to be bad moves. A way of
reducing the number of nodes in the search of the analytical tree now
exists. The alpha-beta pruning method
works on the principle that once you find a move for your opponent that is a refutation of the move you are
considering, then you do not bother analyzing that line further. The key to this method is to select the move that is most
likely to be the best and to have all main candidates listed in descending
order of plausibility before commencing the alpha-beta tree search. Another useful trick is known as the
‘killer heuristic’ which works well in situations where there is a
strong move or manoeuvre which can obtain advantage against several of your opponents moves. The refutation heuristic is also used by
programs in solving ++CM problems.
There are many ingredients in the programmers cake, and some of these
are trade secrets.
Playing against a computer
Do not make the mistake of treating the opening as an isolated thing. Play all your games to a finish or at least until it is clear which side
is winning beyond all doubt. The most
valuable side to practicing your openings against a computer is that it helps
to give you experience with them, so that you will have a feel for the right
move by the time you get a tough game in that particular opening against a
human opponent. It is not very likely
that your computer will play against you a strong move that has not already
been found by human players of mature strength. The total number of moves are decided in
the endgame and middle game. Computers
are real idiots in the endgame. Most
of the problems that computers have in the endgame are connected with passed
mps. It is partly that the value of the passed mp can suddenly shoot up from one to
9+ and partially that occasionally under-promotion is needed. In general MP/mp values can fluctuate in
strange ways in passed mp endgames.
There are also problems to do with the KI, especially getting him to the
right place to shepherd home a mp, and in the endgame to use them actively
while still not losing themselves to capture.
New boards
The endgame is the hardest phase of the game for most
human players. It is a fact that a
computer is less likely to beat you in the endgame than it is in the middle
game. The endgame is loosely applied
to any position with say, QU and a few other MPs and/or mps. The novice player starts by playing on a 7
x 7 (see Tori-Shogi) or, 8 x 8 Chesmayne board (traditional
chess, :L01) and then will move to the introduction of the Vanguards (:L02) etc. After
this a ‘QU-sized-board’ array will take you to a 10 x 10 board. The 12 x 12 board is referred to as the
KI-sized-board. Thus the complexity
will increase by the introduction of new boards and additional MPs/mps with
original moving capabilities.
A good programme
The quality of play from a computer is not, however,
uneven in the way that a human player is uneven. A
computer plays consistently because it is following the same program each time
but its algorithms and heuristics will be more appropriate to some positions
and types of game it finds itself in, than in others. A computer has to be programmed with rigid
and unambiguous instructions to play a game where it needs to be highly
flexible. Human players know all kinds
of techniques which are comparable to the algorithms that tell the computer how
to do specific things, and rules of thumb or, heuristics to call on when these
are inappropriate. Sometimes they
conflict because they are too general and the player has to decide which fits
the present case. On the one hand BSs
are superior to KTs in the open positions with mps on both sides and on the
other QU and KT cooperate much better than QU and BS. A good programme can give the appearance of
creativity. The best software writers
are those who can make a program small and make it clever. The degree of difficulty is much the same
as that which faces a composer who wishes to adapt a violin sonata for full
orchestration. Because they examine
all legal moves from the millions available they are in with a chance of
finding a good move that human players might overlook. Until programmers get a lot better than
they are now, such cases will usually be tactical combinations rather than
strokes of positional genius.
New programs
A lot will depend on how good a player you really,
actually are, and particularly so in Chesmayne. Your chances
of beating the new programs that will become available will depend on your ability to concentrate on playing a sound positional game
and watching out for tactical tricks. The
program will make the running and probably create weaknesses that you will exploit, or else it will manoeuvre and
wait for your attack. If
tactical situations develop then the computer will stand a better chance. If you become one of the new breed of
mature players you may be able to find a critical variation in which you can see further than the machine. What you will need is a line which,
looking two or three or more moves deep, which the program will go in for -
turns out well for you later.
This is where your full thinking powers and creative
abilities will come into play. It will
become possible shortly to train yourself in new combinational continuations which are good on their own
merits. I have given some examples in
the diagrams (see :L01) and a look at these should give you a basic
understanding of what will be possible in the near future. Training for positional sense will not be
easy with a computer so programs will have to be produced that will cater for
this growing market that is bound to appear.
A new rating system will be called for to evaluate the strength
of the players who will play at the ever increasing levels of Chesmayne that
will appear and will reflect a true creative and thinking ability, as opposed to a learn by rote
approach that is common in traditional
occidental chess.
COMPUTER
01 Various models of chess computer are made by Novag, Saitek and
Mephisto. The 5 biggest computers in the
world at the present time are…….
01A Japanese Atomic Research Agency.
Used for studying earthquakes which operates at 103 Gflops (one Gigaflop
equals one billion floating point operations per second).
01B Oak Ridge National Laboratory USA.
Used to map the humane genome.
01C Sandia National Laboratories in New Mexico. Used for modeling nuclear explosions.
140 Gflops. Presently being upgraded to 9,072 Pentium
chips.
01D Fujitsu, NAL Japan. Used for
aerodynamics.
01E Hitachi. 220 Gflops. Theoretical Astrophysics Group, University of
Tokyo. Used to model the birth of the
universe. Teraflop computers are on the
drawing board (a trillion calculations per second).
02 Arthur Burks, Herman Goldstine and John von Neumann published the
ground-breaking paper 'Preliminary Discussion of the Logical Design of an
Electronic Computing Instrument'.
03 Tony Sales rebuilt Colossus (1995/6), the world’s
first electronic computer. It was originally used at Bletchley Park in
Buckinghamshire (home of England’s code-breakers during the 2nd
World War). It was
used to break the German Enigma and Lorenz machine-generated codes. Colossus was built at Dollis Hill in
northwest London by GPO engineers. It
was a parallel architecture computer that could process five different
instructions at the same time. The
Enigma machines initially had 3 and later 4 code wheels. The Lorenz
had 12 and was used for code traffic between Hitler and his top generals ie, Rommel etc.
In the beginning it took six weeks to decode one message sent by a
Lorenz machine. The Mark II Colossus
done the same job in two hours. The
Mark-I had 1,500 valves - the Mark-II, 2,500 valves. Without these machines the D-Day landings
could not have occurred for two more years.
The Americans claim that there Eniac was the first computer in the world. Bletchley Park (Milton Keynes) may be visited
every other weekend between 10 am and 5pm.
Telephone for details: 01908-640404.
One of the keys to computer hostile strategy is to avoid open positions which lead to sharp tactics at which computer programs excel. The first computer to play a ++CM in 2 was programmed in 1949 on a Ferranti digital
machine. The first computer to play a
decent game of chess was written by Alex Bernstein in 1959. In 1967 a computer played in the
Massachusetts Amateur Championship for the first time. The first all computer program chess tournament was held in New York in 1970. The first world computer championship took
place in Stockholm in 1974 and was won by the Soviet program, Kaissa. Cray Blitz
won the first state (USA) championship in 1981. The first time a master was defeated by a computer occurred in 1983. 1983 was also the year in which a computer
gained a master’s rating.
Man versus Machine - My personal viewpoint
ace942@gate.net
There has been a lot of talk lately in the news about
chess ever since last year when Gary Kasparov was challenged by the IBM chess programming team to
a series of chess matches against their creation, Deep
Blue. Many people feel that the human brain is one of the most complex and a sign of the ultimate achievement by God. To play a
dumb machine and have it possibly beat the best current player in the world (and some would argue perhaps the best player of all
time) would be the worst thing that could ever happen to us.
I have been
working with computers ever since my senior year in high school way back in
1980. I have always seen computers as
tools that people can use to make everyday life much easier to manage. No longer do we have to use old fashioned
typewriters to type out our letters or have to worry about making typing
mistakes due to the fact that most modern word processors are getting more and
more sophisticated with new features that making the creative process of
writing easier. We no longer have to
worry about using too much white out which would distract the reader from
whatever it is that we wish for them to review. Computers removed the need for book ledgers
as well since we can now use Excel or Lotus to accomplish the very same
task. If we need to send a letter to a
loved one, we no longer
have to wait for the postal service to deliver it. Now with electronic mail, you can get a
message to someone within a few minutes or in a worse case scenario, perhaps a
few hours.
With all the wonderful things that
computers have given us, it really bothers me that we are now using computers
for what I consider to be an evil thing.
To prove that machines are better than man. Personally, I don’t like it at all. Machines are supposed to be helping us, not
challenging us. I know that to Deep Blue, it is nothing
more than a series of numbers to be crunched.
It doesn’t know what it is truly doing. It is a very sophisticated
program that allows it to accomplish a task that for a long time no one thought
would ever be possible. Sure,
computers can beat lower ranked players.
Mine beats me all the time with no problem (although I am learning more
and more as I play it and thus it gets harder for it to beat me as I play with
it more and more. I even beat it once
at its highest setting but it took me about one hour of playing time to it’s 5
minutes). But beating our very best? That I could never tolerate.
Even worse in my opinion is some of
the attitudes of some of the IBM programmers involved in the Deep Blue
project. They are talking about how
computers will be used to solve problems that man himself can not solve. They must be both arrogant and out of their
minds. Like the 4th Doctor Who (my
favorite) said,
“The problems with computers of
course is that they are nothing more than very sophisticated idiots”.
Computers are nothing more than very
efficient processors of information.
They take information into themselves through various means and process
that information according to a certain algorithm that we call a
computer program. Since computers can
not think for themselves
yet (and I hope they never do or else the stuff that happened in the Terminator
movies might come true),
they are not capable of solving any problem that we ourselves can not. They need to be programmed in order to
accomplish any task given to them. If
we can program in a solution into the machine, then there is no problem that
can not be solved by a human being given enough time, is there? This is why I can’t stand the IBM
team. They need to be reminded that
computers are nothing more than high speed calculators.
Well, you have now
by personal thoughts on the matter. I
hope that everyone is enjoying the matches between Kasparov and DB (Deep Blue)
so far. I know I have enjoyed them and
all the wonderful comments from everyone starting from the GM’s and all the way
down to players at my level. It is a
learning experience to see how players of all different chess abilities view the same
board in different ways. I hope that
Kasparov can prevail against Deep Blue just like he did last year. I felt that the machine had an unfair advantage over Kasparov
last year since the machine was able to study games that Kasparov had
previously played in but Kasparov was not permitted to study games played by
Deep Blue because IBM was worried that Kasparov would be able to find a weakness in the machine.
If I had been in the very same
situation as Gary was, I would have insisted on being allowed to view previous
practice games played by Deep Blue and strongly demanded to view such games or
I would have refused to play it at all.
By the way, this is not a admission of defeat to machines. Today, chess masters use database
programs like Chessbase
to study their opponents and get an idea
from the games that they have played to get an understanding of their
style of play. Emmanual Lasker, one of the great
chess players of all time used to make inferior moves on the chess board
because he knew that particular opponent had problems with particular
situations that would arise in chess.
He was using a technique in chess called “playing the man, and not the board”.
It really helps Chess Masters in
their preparation for their upcoming matches to be able to view games
that have been played by their opponents.
Given the paranoid attitude of the IBM team, they must really be worried
that they have still not found all the bugs in the software for Deep Blue. It would be a real embarrassment to the
IBM chess team since supposedly they have taken Deep Blue to chess school for a
year and a half to try to remove all of the bugs from the earlier version that
Kasparov beat 4-2 last year. They even
had a Grandmaster (Joel Benjamin)
working with the programmers this time to see how Deep Blue evaluates positions
and tried to strengthen it’s style of play.
Certainly, I give them credit for improving the program and we might all
very well benefit from that type of computing power sometime in the near future
but until DB beats either Kasparov or whoever might be the next human champion,
humans at the highest level of chess will always be superior.
Your thoughts and comments would be
most appreciated. Email your comments to
me at the following Internet email address…….
ace942@gate.net
Sources: http://www.tim-mann.org/chess.html
The history of Winboard
All goes back to 1991 when Dan Sears and Chris Sears
start programming this piece of software.
Later (from 1992 till now) Tim Mann made some enhancements. Since then
Tim Mann has taken the “development in his hands”! He is really a great programmer , with
interesting ideas and of course with handy implementations.
Xboard’s alternative piece bitmaps (bitmaps.xchess)
are derived from the bitmaps in the XChess program, which was written and is
copyrighted by Wayne Christopher.
What is this software?
XBoard is a graphical chessboard for X systems while
Winboard is a graphical chessboard for Windows systems. With Winboard you can do any of the
following…..
Where can I get a copy of Winboard/Xboard
The best place to get the latest versions of XBoard
and WinBoard is Tim Mann’s web site. So
go directly to: http://www.tim-mann.org/chess.html. Another place
that you can find XBoard and WinBoard or other free chess software is by
anonymous FTP from ftp://ftp.gnu.org/pub/gnu/ and its many mirror sites.
Play against a chess engine
Choose your favorite chess engine (which is Winboard
compatible of course) and start playing chess!
Match two engines
Starts a game between two chess engines. You can also set the number of games and the
time controls, so that to create a complete tourney! Another useful feature is that you can set a
default PGN file where all games of your tourney are saved automatically!
Winboard and the Internet
You can easily connect with an Internet Chess Server
to play chess against its other users, observe games they are playing, or
review games that have recently finished.
When you run WinBoard in ICS mode, it starts up a console window in
which you can type commands and receive text responses from the chess
server. I find it really very handy
tool when choosing this mode!
View or edit mode.
If you start up Winboard in the view mode, you can
easily load a PGN file and view its games using Winboard as an interface. If no game file is loaded (this means that
you are in edit mode) you can simply create a game file by just playing moves
on the Winboard interface. After
finishing entering moves you can alter the tags data and finally save the game
in a PGN (Portable Game Notation ) file.
Yes life is so easy!
