Advances in Computer Chess 1

From Chessprogramming wiki
Revision as of 16:33, 8 October 2018 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

Home * Conferences * Advances in Computer Chess 1

Next >

The Advances in Computer Chess 1 conference was held in March 1975 at Balliol College, Oxford, England, and was organized by the Atlas Computer Laboratory and the Society for the Study of Artificial Intelligence and Simulation of Behaviour (SSAISB). Proceedings were published in 1977, edited by Mike Clarke. It was already the second conference on computer chess, after a conference meeting on chess playing by computer in May 1973 at Atlas Computer Laboratory [2].

Proceedings

  • Advances in Computer Chess 1
M.R.B. Clarke, Editor, 1977
Edinburgh University Press, Edinburgh.
ISBN 0-852-24292-1, amazom

Papers

  1. Georgy Adelson-Velsky, Vladimir Arlazarov, Mikhail Donskoy (1977). On the Structure of an Important Class of Exhaustive Problems and Methods of Search Reduction for them.
  2. Hans Berliner (1977). A Representation and Some Mechanisms for a Problem-Solving Chess Program.
  3. Ron Atkin (1977). Positional Play in Chess by Computer. [3]
  4. Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board.
  5. Soei T. Tan (1977). Describing Pawn Structures.
  6. John Birmingham, Peter Kent (1977). Tree-searching and tree-pruning techniques.
  7. Mike Clarke (1977). A quantitative study of KPK.

Reviews

The Forerunner

The first conference meeting on computer chess took place at the Atlas Computer Laboratory May 1973. It was the forerunner of the later Advances in Computer Chess conferences. Alex Bell about the arisen of the conference [4] :

In 1972 I was back in England again and met John Scott, who was doing a PhD, and his tutor Dr. Alan Bond. Naturally we talked about chess programs and the recent happenings in the American ACM tournaments. As we talked it became fairly obvious that in the intervening 4 years a number of new ideas had appeared on the scene. One idea was called refutation, a technique which (like alpha-beta) could vastly speed up the tree searching without any loss of information (see Chapter 9 - Machine Technique).
Even more mysterious was a paper Multi Dimensional Structure in the Game of Chess by Ron Atkin [5] , a maths lecturer at Essex University. Up to this point all chess programs had evaluation functions which were decidedly ad hoc, the programmers had a feeling in their water that certain features, material, mobility, control of the centre, king safety, pawn structure, etc., were the most important and accordingly stuck them in the program with very little idea of their precise effect. Now here was a mathematician who, with lots of squiggly things, appeared to have a precise mathematical evaluation function. Unfortunately neither John nor I could understand the paper - so why not get Atkin to talk about it. There were a few other new ideas I did not understand - a new, knowledge approach to solving end games and some psychological theories about how chess players think - so why not have a conference? If nothing else I might get some idea of what was going on.
The first Computer Chess Conference took place at the Atlas Computer Laboratory in May 1973. Apart from inviting the speakers it was also obvious that the conference would have to demonstrate a chess program in some form and it is at this point in time that MASTER really got started.
--
From then on the operators played more carefully and revealed that the program, because it still only had a shallow search, still suffered badly from horizon effect. Nevertheless it did win a few more games and it was decided to use it as the demonstration program at the conference.
Well it didn't win a game, hardly surprising since it was up against much stronger players. Nevertheless several people noticed that the program was usually achieving its main aim of controlling the centre squares; in other words, it was quite successful in doing what little it had been told to do but, from then on, it had no further direction other than a vague idea of advancing its own pawns and blocking its opponent's. Peter improved its sense of purpose by making the program, as the game progressed, put less emphasis on controlling the fixed centre squares and more and more emphasis on controlling the squares around the enemy king, wherever he may be. Because of mini-max this also caused the program to protect the squares around its own king far more effectively.

ACC1

The conference on computer chess took place at Balliol College, Oxford in March 1975. It was organized by Atlas Computer Laboratory and the Society for the Study of Artificial Intelligence and Simulation of Behaviour (SSAISB), and was later declared as Advances in Computer Chess 1 conference. Proceedings were published by Mike Clarke from Queen Mary College. Some excerpt from co-organizer, Alex Bell's report in Computer Weekly, April 10, 1975, Techniques for playing the end game [6] :

AFICIONADOS of the arts of chess and computing gathered at Balliol College, Oxford, last month for the second conference on computer chess organised by the Atlas Computer Laboratory and the Artificial Intelligence and Simulation of Behaviour study group.
A number of experts were invited to give papers. on their work, including Dr Mikhail Donskoy of the USSR, one of the authors of the world champion program, KAISSA. Unfortunately Donskoy was unable to attend, a disappointment only mitigated by the presence from the US of Dr Hans Berliner, of Carnegie-Mellon. Berliner is the world correspondence chess champion and has also spent the last eight or nine years programming computers to play the game. To most people in the practical, model building side of the subject, ie making a program play the computer game, Berliner is THE expert. Although full of good, implementable ideas he has no illusions as to the limitations of such chess programs.
--
The conference itself lasted one and a half days and the papers (depending on the listener) ranged from the profound to the puerile. I have no desire to repeat my own personal views, indeed as one of the organisers I helped to provide a platform for speakers whose views I found astonishing. What did seem evident to me was that the majority of the audience fell into one of three categories. One group is the artificial intelligentsia. They fully understand the difficulties of the problem and are still thinking about how to solve it. The second group are the let's get on and program something crunchers, the model makers, the people who can make big computers float round the room whistling God save the Queen. These people absolutely refuse to put anything remotely resembling knowledge, chess or otherwise, into their programs if they can avoid it, believing that if the result plays good chess then it can be more easily adapted to attempt other, more useful, decision making problems. The third group is the most important, these are the people who are new to the subject, the people who say, It sounds like a fascinating problem and I'd like to know what's going on.
Hans Berliner fits into two of these categories, his talk covered the AI approach and the crunchers, but he is hardly a newcomer. He was the first speaker and the domain of his talk was chess tactics with emphasis on recognising situations and dealing with them explicitly. He is full of good ideas and techniques which are relevant to the problem of selecting the right move in a game of chess and, more important, showed clearly how each idea and technique could be implemented in a computer.
The next paper by Ron Atkin, of Essex University, was more profound. Atkin has developed a mathematically valid approach to positional play in chess and also described a method of simulating the hierarchical method used by the chess master. His ideas have an intuitive appeal; one feels he must be right but the problem of implementing the ideas in a computer, are enormous and, as yet, unsolved. Another problem was that not a single person in the audience was sufficiently competent to stand up and say, "This is all very well but your approach will not handle this situation in a chess game, a tactic which often shoots down the simple minded crunch programs".
The final talk on the first day was given by Professor Donald Michie of the Machine Intelligence Research Unit, Edinburgh, who dealt with mechanisation of the King, Rook versus King end game. The first machine to play this end game was built by Torres y Quevado c. 1900. Hardly anything was published about it and Michie made an interesting reconstruction of the machine, and I have to admit that Michie had got most of it right.
The next day the speakers included Dr Soei Tan, also of Edinburgh, who dealt with pawn structures; John Birmingham and Peter Kent partially described how MASTER operates; and Mike Clarke, of Queen Mary College, talked about the King, Pawn versus King ending. Clarke's approach is much more scientific than the crunch programs; he has enumerated all possible positions of the K, P v K end game (there are 906,545,760 of them) and discovered which are wins and which are draws. He has done a similar enumeration for the King, Rook v King ending and should, with a little more effort. be able to scientifically work backwards to the 16 pawns, 16 pieces end game.
As can be seen a great deal of time was spent on this King, Rook v King ending. This is interesting because if this ending can cause such difficulty then it is intuitively obvious that the full game must be at least an order of magnitude more difficult. This is intuitively obvious but difficult to prove, nevertheless it appears to be true in the real world. I certainly have great difficulty obtaining a draw with the lone King. Finally, Max Bramer has offered to demonstrate his K,R v K and K,P v K programs to anyone who is interested. He can be contacted at the Open University.

Forum Posts

External Links

References

  1. Oxford - Balliol College, One of my favourite views, across the appropriately-named Broad Street, May 30 2009, Photographer Peter Trimming, source geograph.org.uk
  2. Alex Bell (ed.) (1973). Computer Chess. Proceedings May 1973 Meeting on chess playing by computer. Science Research Council, Atlas Computer Laboratory
  3. Re: Whatever happened to Neural Network Chess programs? by Andy Walker, rgcc, March 28, 2000
  4. Alex Bell (1978). MASTER at IFIPS. Excerpt from: The Machine Plays Chess? Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)
  5. Ron Atkin (1972). Multi-Dimensional Structure in the Game of Chess. In International Journal of Man-Machine Studies, 4 pp. 341-362
  6. Alex Bell (1975).Techniques for playing the end game. Atlas Computer Laboratory, hosted by Rutherford Appleton Laboratory (RAL)

Up one Level