Programming a computer to play chess in the 1950s

Jacqueline Wagner

University of Heidelberg
jacqueline.wagner@stud.uni-heidelberg.de

April 18 2019

Jacqueline Wagner University of Heidelberg April 18 2019 1 / 38

Overview

1 Introduction
2 The easy way out
Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider
3 Considering a more complex approach
Coming up with a better strategy
More problems to consider
4 Conclusion
5 References

Jacqueline Wagner University of Heidelberg April 18 2019 2 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 3 / 38

Theories highlighted in this presentation

Programming a Computer for

Playing Chess by Claude
Shannon, 1949
Digital Computers applied to
Games by Alan Turing, 1953

Figure: Claude E. Shannon

Image: [11]
Jacqueline Wagner University of Heidelberg April 18 2019 4 / 38
Events that shaped the decade

Image 1: [8], Image 2: [14], Image 3: [19], Image 4: [6], Image 5: [10]
Jacqueline Wagner University of Heidelberg April 18 2019 5 / 38
Advancements made in the 1940s

Image 1: [17], Image 2: [5], Image 3: [20], Image 4: [7]

Jacqueline Wagner University of Heidelberg April 18 2019 6 / 38
What you might be thinking right now...

Why are we looking at theories created in the

1940s and early 1950s?
Is this even relevant information for me?
Are we wasting our time?
Why chess?

Image: [2]
Jacqueline Wagner University of Heidelberg April 18 2019 7 / 38
Chess 101

a game of chess can be divided into three phases

the longest tournament lasted for 269 moves [4]
the shortest chess tournament lasted for 4 moves [4]

Image: [16]
Jacqueline Wagner University of Heidelberg April 18 2019 8 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 9 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 10 / 38

Playing a perfect game of chess

consider all possible moves in a given position

until an outcome has been reached
possible since game ends after a finite number
of moves
318,979,564,000 different ways of playing the
first four moves
10120 game variations to consider

Image: [9]
Jacqueline Wagner University of Heidelberg April 18 2019 11 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 12 / 38

Playing a skillful game of chess

evaluate a position on the basis of

general layout of the position
number and kind of black and white
pieces on the board
pawn formation
each players mobility
possible legal moves
use chess principles with statistic validity

Image: [0]
Jacqueline Wagner University of Heidelberg April 18 2019 13 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 14 / 38

Coming up with a first strategy

calculate all possible variations out to

two moves deep for each side
apply evaluation function f (P) after
every move
assume that the opponent will minimize
f(P)
choose the variation which will
maximize f(P) given this constraint

Image: [21]
Jacqueline Wagner University of Heidelberg April 18 2019 15 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 16 / 38

Necessary Hardware

Image: [21]
Jacqueline Wagner University of Heidelberg April 18 2019 17 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 18 / 38

Defining building blocks

T0: Make move (a, b, c) in position P to obtain resulting position

T1: Make list of all possible moves for pawn pieces at square (x, y ) in
position P
T2-T6: Perform the above evaluation on all other types of pieces
T7: Make list of all possible moves for all pieces in given position P
T8: Calculate the evaluating function f (P) for position P
T9: Perform maximizing and minimizing to determine the overall best
move

Jacqueline Wagner University of Heidelberg April 18 2019 19 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 20 / 38

Some fundamental problems to consider

> 16 minutes to perform a move

variations are only considered three
moves deep
strategy is the same in calm positions

Image: [12]
Jacqueline Wagner University of Heidelberg April 18 2019 21 / 38
Ideas for improvement

examine forceful variations out as far as

possible
perform evaluation once a stable
position has been reached
only evaluate worthwhile variations

Image: [3]
Jacqueline Wagner University of Heidelberg April 18 2019 22 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 23 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 24 / 38

Shannons idea

evaluate whether stability exists using a function g (P)

explore for 2 to 10 moves until g (P) = 0
evaluate whether a move M in position P is worth exploring using a
function h(P, M)
forceful moves → high h(P, M)
defensive moves → medium h(P, M)
all other moves → low h(P, M)
with increasing depth fewer sub-variations are examined

Jacqueline Wagner University of Heidelberg April 18 2019 25 / 38

Turings idea

evaluate game for at least two moves

dead position = no captures, recaptures
or checks are possible in the next move
all other positions are considerable
positions
estimate value at the end of a sequence
based on criteria, such as material,
mobility, safety or threat of checkmate
choose move which leads to the greatest
value and the greatest positional value

Image: [3]
Jacqueline Wagner University of Heidelberg April 18 2019 26 / 38
1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 27 / 38

More problems to consider

machine always makes the same move in the same position →

opponent can use weak decisions to win
program is quite complicated in opening stage where masters focus on
set number of variations until one player deviates

Jacqueline Wagner University of Heidelberg April 18 2019 28 / 38

More ideas for improvement

use statistical element to avoid repeating the same strategy over and
over again
store few hundred standard opening strategies in slow-speed memory
change style of play by modifying selected coefficients and numerical
factors
increase strength of the player by adjusting depth of the calculation or
evaluation function

Jacqueline Wagner University of Heidelberg April 18 2019 29 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 30 / 38

Conclusion

machine will not learn from its mistakes

strategy relies on brute force calculation rather than logical analysis

Image: [1]
Jacqueline Wagner University of Heidelberg April 18 2019 31 / 38
Conclusion

“It plays something like a beginner at chess who has been told some of the
principles and is possessed of tremendous energy and accuracy for calculation
but has no experience with the game.”
Shannon, 1949
Programming a Computer for Playing Chess, page 273

Jacqueline Wagner University of Heidelberg April 18 2019 32 / 38

Conclusion

“The computer is strong in speed and accuracy and weak in analytical ability and
recognition. Hence, it should make more use of brutal calculations than humans.”
Shannon, 1949
Programming a Computer for Playing Chess, page 274

Jacqueline Wagner University of Heidelberg April 18 2019 33 / 38

Conclusion

“If I were to sum up the weakness of the above system in a few words I would
describe it as a caricature of myself.”
Turing, 1953
Digital Computers applied to Games, page 9

Jacqueline Wagner University of Heidelberg April 18 2019 34 / 38

1 Introduction

2 The easy way out

Playing a perfect game of chess
Playing a skillful game of chess
Coming up with a first strategy
Necessary hardware
Constructing a program
Some fundamental problems to consider

3 Considering a more complex approach

Coming up with a better strategy
More problems to consider

4 Conclusion

5 References

Jacqueline Wagner University of Heidelberg April 18 2019 35 / 38

References I

Dec. 15, 2013. URL: https://www.trivalleylifechurch.org/2013/12/15/no-brain/.

Nov. 25, 2016. URL: http://hdimages.org/question-mark-image-hd/.

Aug. 7, 2017. URL:

https://tmhome.com/wp-content/uploads/2014/01/meditation-higher-intelligence-research-w2.jpg.

Apr. 16, 2019. URL: https://ohfact.com/interesting-facts-about-chess/.

Apr. 17, 2019. URL: http://worldartsme.com/abacus-clipart.html#.

Evan Ackerman. Sept. 30, 2016. URL:

https://spectrum.ieee.org/tech-history/space-age/a-brief-history-of-the-microwave-oven.

Jodi Beggs. Dec. 9, 2017. URL: https://www.thoughtco.com/the-meeting-game-definition-1147465.

Detlef Borchers. Feb. 16, 2016. URL: https://www.heise.de/newsticker/meldung/Vor-70-Jahren-Amerika-

lernt-den-ersten-elektronischen-Universalrechner-ENIAC-kennen-3102001.html.

Gregor Delvaux de Fenffe. July 29, 2016. URL:

https://www.planet-wissen.de/geschichte/diktatoren/mao_zedong_gnadenloser_machtmensch/index.html.

Stephanie Pappas. Sept. 24, 2018. URL: https://www.livescience.com/63655-why-earth-wobbles.html.

Jacqueline Wagner University of Heidelberg April 18 2019 36 / 38

References II

Scott Michael Rank. Apr. 16, 2019. URL: https://www.historyonthenet.com/when-did-america-enter-ww2.

Siobhan Roberts. Apr. 30, 2015. URL: https://www.newyorker.com/tech/annals-of-technology/claude-

shannon-the-father-of-the-information-age-turns-1100100.

Ronan. July 12, 2017. URL: https://huddle.eurostarsoftwaretesting.com/when-you-have-minimum-time-

for-testing-what-do-you-do/time-running-out-clock/.

Andrew Schell. Sept. 1, 2014. URL:

https://www.maximumyield.com/amino-acids-the-lego-blocks-of-plant-proteins/2/2596.

Johnny Simon. Aug. 6, 2018. URL:

https://qz.com/1349319/pictures-of-hiroshima-and-nagasakis-atomic-bomb-destruction/.

Jimmy Soni. Aug. 16, 2017. URL:

https://www.chess.com/article/view/the-man-who-built-the-chess-machine.

Jimmy Stamp. Apr. 3, 2013. URL:

https://www.smithsonianmag.com/arts-culture/how-the-chess-set-got-its-look-and-feel-14299092/.

Steemit. Apr. 16, 2019. URL:

https://steemit.com/history/@steemizen/today-in-history-the-first-frisbee.

Jacqueline Wagner University of Heidelberg April 18 2019 37 / 38

References III

Martin Stezano. Aug. 29, 2017. URL: https://www.history.com/news/in-1950-alan-turing-created-a-

chess-computer-program-that-prefigured-a-i.

Shashi Tharoor. Dec. 9, 2010. URL: https://www.welt.de/debatte/die-welt-in-

worten/article11502690/Gandhis-Methoden-halfen-die-Welt-zu-veraendern.html.

Pamela Wiggins. June 9, 2018. URL:

https://www.thesprucecrafts.com/guide-to-vintage-tupperware-4158189.

Claude E. Shannon. “XXII. Programming a computer for playing chess”. In: The London, Edinburgh, and
Dublin Philosophical Magazine and Journal of Science 41.314 (1950), pp. 256–275. eprint:
https://doi.org/10.1080/14786445008521796. URL: https://doi.org/10.1080/14786445008521796.

Jacqueline Wagner University of Heidelberg April 18 2019 38 / 38