Workshop Chess and Mathematics
Home * Conferences * Workshop Chess and Mathematics
- Fakultät Mathematik und Naturwissenschaften Institut für Numerische Mathematik
Contents
- 1 Chess Olympiad 2008
- 2 Programme Committee
- 3 Public Lecture
- 4 Invited and Contributed Lectures
- 4.1 Multi-Cut
- 4.2 General Game Playing
- 4.3 Optimal Line-Ups
- 4.4 Combinatorics
- 4.5 Spielstärkeprognosen
- 4.6 Solving Chess
- 4.7 Information of Chess Positions
- 4.8 Bitoptimiertes Speichern
- 4.9 Endgame Databases
- 4.10 Sliding Pieces Attacks
- 4.11 Valuation Equilibrium
- 4.12 Problem Chess and Mathematics
- 4.13 Databases for Chess Problems
- 4.14 Die Schachwelt im Internet
- 5 References
Chess Olympiad 2008
The Workshop Chess and Mathematics was side event of the Chess Olympiad, Dresden 2008, the Public Lecture took place at the Congress Center, the Invited and Contributed Lectures on Saturday at the TU Dresden.
Programme Committee
- Prof. J. Nievergelt (Zürich)
- Dr. U. Lorenz (Darmstadt)
- Jun.-Prof. T. Linß (Dresden)
- Prof. Hans-G. Roos (Dresden)
Public Lecture
Schach und Mathematik
Christian Hesse, Stuttgart [3] [4]
SCHACH UND MATHEMATIK
Fr., 16:00, Congress Center (German)
German Abtract
Schach und Mathematik gehören zum geistigen Weltkulturerbe. Aufgrund ihrer inneren Logik bestehen viele Parallelen zwischen ihnen. Beide sind ein Resonanzboden für Kreativität, Leidenschaft, Ästhetik und Harmonie. Der Vortrag ist populäarwissenschaftlich angelegt und zeigt einige Highlights der Anwendung mathematischer Ideen auf Probleme des Schachs. Allgemeinverständlichkeit wird angestrebt.
English Abtract
Chess and mathematics belong to the mental world cultural heritage. Due to their internal logic many parallels between them exist. Both are a resonance ground for creativity, passion, aesthetics and harmony. The popular science lecture shows some highlights of the application of mathematical ideas to problems of chess. Generally comprehensibleness is aimed at.
Invited and Contributed Lectures
Multi-Cut
Yngvi Björnsson, Reykjavik
MULTI-CUT: A SPECULATIVE PRUNING MECHANISM FOR CHESSPLAYING PROGRAMS [5]
Sa., 09:00, TU Dresden, WIL C207
The alpha-beta algorithm is the most popular method for searching game-trees in adversary board games such as chess. It is much more efficient than a plain brute-force minimax search because it allows a large portion of the game-tree to be pruned, while still backing up the correct game-tree value. However, the number of nodes visited by the algorithm still increases exponentially with increasing search depth. This obviously limits the scope of the search, since game-playing programs must meet external time constraints: often having only a few minutes to make a decision. To somewhat alleviate this problem so-called speculative-pruning methods are used to cut off less interesting lines of play prematurely, while allowing interesting lines to be explored more deeply.
Here we discuss one such speculative-pruning method called multi-cut, which makes pruning decisions based not only on the risk of pruning off relevant lines of play, but also on the likelihood of such an erroneous pruning decision affecting the move decision at the root of the search tree. The method has been successfully employed by several of the world’s strongest commercial chess program for a number of years.
General Game Playing
Michael Thielscher, Dresden
ARTIFICIAL INTELLIGENCE AND GENERAL GAME PLAYING [6]
Sa., 09:45, TU Dresden, WIL C207
Chess computers play at the same level as the best human players these days, but their general intelligence is severely limited. Most chess programs cannot even play slight variations of the game–like Bughouse Chess–let alone completely different games such as Tic-Tac-Toe, which every child easily learns to play well.
A general game player is a computer that understands a description of the rules of arbitrary games and learns to play these games well without human intervention. In this talk we introduce General Game Playing from the perspective of Artificial Intelligence research and provide some insight into our system FLUXPLAYER, which has been crowned the world champion at the Second General Game Playing Competition in 2006 in Boston.
Optimal Line-Ups
Stefan Schwarz, Jena
OPTIMAL LINE-UPS IN TEAM COMPETITIONS WITH (NON-)LINEAR OBJECTIVE FUNCTIONS
Sa., 10:50, TU Dresden, WIL C207
We consider a team competition (as in chess) where every member of team
A = {a1, . . . , an}
plays against exactly one member of team
B = {b1, . . . , bn},
where ai > 0 and bi > 0 denote the playing strength of the i-th player of team A and B, respectively. We assume that a player with strength bj playing against a player with strength ai gets in average
points. Further we assume that the sequence of team A is fixed whereas team B can order its players in an arbitrary permutation ¶. If the aim of team B is to maximize the expected sum of points
we get the well known assignment problem with a linear objective function. But in many applications team B do not want to maximize the expected number of points, but e. g. the probability of having more points than A. This results in an assignment problem with a non-linear objective function. We show for a broad class of such non-linear assignment problems that the set of potentially optimal permutations is exactly the same as in the linear case. That means for every permutation ¶ which is an unique optimal solution of a non-linear assignment problem, there is already a linear assignment problem such that ¶ is the unique optimum.
Combinatorics
Bernd Steinbach, Freiberg (with Christian Posthoff, St. Augustine)
COMBINATORICS ON THE CHESS BOARD – SOLUTIONS USING LOGIC EQUATIONS
Sa., 11:25, TU Dresden, WIL C207
The satisfiability problem (SAT) for Logic Equations has been well explored [7], many algorithms are available, mostly search-oriented. Based on a new data structure (ternary vectors) [8], very efficient parallel algorithms for its solution have been designed and implemented. It will be shown that many combinatorial problems can be transformed into satisfiability problems and solved using these developed algorithms. The approach is constructive and very general, no research procedures are involved, results are always complete. It can be concluded that the solution algorithms for SAT can be used (in the sense of NP-completeness) for many other combinatorial problems in a very general way. Among the problems that have been solved are questions of the type
- How many queens (rooks, bishops, knights, fairy chess pieces, ?) can be placed on the chess board without threatening each other?
- Are there Hamiltonian cycles or paths on the chess board, and how many of them, again for different pieces?
- The n+k-problem: Is it possible to place n+k queens on a board of size n × n if k pawns are placed on the board.
- All these problems can also be considered not only on an 8 × 8 chess board, but also on boards of size n ×m, n,m > 0.
Spielstärkeprognosen
Robert Offinger, Magdeburg
SPIELSTÄRKEPROGNOSEN AUFGRUND DER BISHERIGEN ENTWICKLUNG DER ELO-ZAHL
MIT HILFE VON STATISTISCHEN METHODEN
Sa., 11:35, TU Dresden, WIL C207
Primäres Ziel unserer Untersuchung, die vom Deutschen Schachbund angeregt wurde, ist es, das Entwicklungspotential eines jungen, bis ca. 25 Jahre alten Spielers einzuschätzen und statistische Hilfsmittel bei der Aufstellung der Kader zur Verfügung zu stellen.
Zu Beginn unseres Vortrages werfen wir einen kurzen Blick auf bisherige rudimentäre Ansätze, die in diese Richtung unternommen wurden. Wir betrachten anschließend verschiedene neue Modelle für den Verlauf der mittleren Spielstärke gemessen in Ratingpunkten. Mit Hilfe dieser Modelle versuchen wir sowohl die mittlere Spielstärke eines Spielers in einem zukünftigen Zeitraum allein aufgrund der bisher erreichten Elo-Zahlen zu schätzen, als auch die konkrete Elo-Zahl zu einem Zeitpunkt mitsamt einem Unsicherheitsbereich vorherzusagen. Nachdem wir die Güte der Modelle für den angestrebten Personenkreis beurteilt haben, diskutieren wir abschließend, ob unser Modell auch für Clubspieler brauchbare Ergebnisse liefert und wo noch Schwachstellen und Verbesserungsmöglichkeiten der statistischen Modelle liegen.
Solving Chess
Jaap van den Herik, Tilburg
CONDITIONS AND PREDICTIONS FOR SOLVING THE GAME OF CHESS
Sa., 13:30, TU Dresden, WIL C207 [9]
Chess is an attractive pastime and scientifically interesting by its complexity, its tactics, and its strategies. After fifty years of computer-chess research we have reached the situation (already since 1997) that computer programs outperform the best human beings. The next prevailing question therefore is: can a computer program solve the game of chess? The number of different reachable positions is 10^46 (Chinchalkar, 1996).
However arranging the list of positions in such a way that they can be visited or cut off by a clever computer program requires
- (1) a new intelligent approach,
- (2) a considerable speed-up of computer power, and
- (3) a considerable enlargement of storage capabilities.
Stimulating developments in this respect are
- (a) Solving Checkers by Schaeffer et al. (2007), and
- (b) defeating Kim Myungwan on Go (in a 9-stone handicap match, 2008).
New techniques potentially usable in chess are:
- (i) Monte-Carlo Tree Search,
- (ii) UCT (Upper Confidence bounds applied to Trees),
- (iii) Supercomputers, such as IBMp6 (with 3328 processors), and
- (iv) Grid Technology.
Conditions on and predictions for these techniques will be discussed in the lecture as well as their impact. An optimistic date for solving chess is 2035 and a pessimistic one (assuming that we can solve the game) is 2065. The solving time in 2035 (optimistic prediction) will be between 37 days and 4 months.
- Chinchalkar, S. (1996). An Upper Bound for the Number of Reachable Positions. ICCA Journal, Vol. 19, No. 3, pp. 181-183.
- Schaeffer, J. et al. (2007). Checkers is Solved. Science, Vol. 317, No. 5844, pp. 1518-1522.
Information of Chess Positions
J. Nievergelt, Zürich
THE INFORMATION CONTENT OF CHESS POSITIONS AND ITS IMPLICATIONS
Sa., 14:15, TU Dresden, WIL C207
Experiments in cognitive psychology involving the visual processing of chess positions (A. de Groot, H.A. Simon, et al.) have revealed stark contrasts as well as similarities between chess masters and novices. In essence, and not surprisingly, experts perform much better than novices when facing realistic chess positions, but not on board positions where pieces are placed at random. The superior performance on realistic positions is explained by the expert’s ability to encode the position into perceptual chunks, each consisting of a familiar subconfiguration of pieces”. This encoding fails for random positions, where the expert’s chess specific knowledge does not help. This insight raises the question of investigating the fuzzy but intuitively meaningful concept “realistic chess position”. We describe a technique based on guessing an unknown position by asking questions. Experiments indicate that on average, 70 to 80 bits of information suffice to identify a randomly chosen realistic position. It follows that realistic positions are a tiny fraction of all legal positions.
Bitoptimiertes Speichern
Eduard Humburg, Wolfratshausen
BITOPTIMIERTES SPEICHERN EINER SCHACHSTELLUNG
Sa., 14:35, TU Dresden, WIL C207 (German)
Es wird eine Notation vorgeschlagen, die es ermöglicht, jede mögliche Schachstellung in optimierter Form binär zu codieren. Ein Programm, das sowohl die Codierung (Stellung wird eingegeben und daraus der Code erzeugt) als auch die Decodierung (aus einem codierten Datensatz wird die Stellung wieder erzeugt) wurde entwickelt. Dabei werden außer der Darstellung der Figuren auch die Zusatzinformationen für Zugrecht, en-passant, Rochaderechte, 50-Züge-Regel und Gesamtzugzahl berücksichtigt. Ebenso sind auch alle Umwandlungen erfasst. Als interessantes Resultat ergibt sich eine obere Schranke für die Anzahl aller möglichen Stellungen.
Endgame Databases
Eiko Bleicher, Berlin
ENDGAME DATABASES FOR THE GAME OF CHESS
Sa., 15:15, TU Dresden, WIL C207
Chess endgame analysis has been a topic of interest for many decades. Databases started on paper and evolved with the available hardware. Space and time have always defined bounds to the complexity of the endgames examined. The best-known products of the recent years are Ken Thompson's databases, the Nalimov tablebases and the ShredderBases. Whereas those database solve endgames in their entirety, the program Freezer makes analysis of more advanced endgames accessible by relying on imperfect information in the database generation process. This presentation will give an outline of the database build process in general and in Freezer.
Sliding Pieces Attacks
Gerd Isenberg, Hattingen
EFFICIENT GENERATION OF MOVES AND CONTROLS FOR SLIDING PIECES
Sa., 16:00, TU Dresden, WIL C207
Attack-Sets as Base for Bitboard Move-generation: Opposed to “None-sliding” pieces, Knight, King and Pawn, whose attacks are determined by its origin square only, sliding piece attacks like Rook-, Bishop- and Queen-attacks are dependend on other pieces as well, which may block the attacking ray in one particular ray-direction. In Quiescence Search the performance of generating (winning) capture moves is crucial. Opposed to classical square-centric board-representations , which require loops over squares, bitboards permit more efficient algorithms in generating sliding attacks.
Valuation Equilibrium
Christian Seel, Bonn
VALUATION EQUILIBRIUM
Sa., 16:20, TU Dresden, WIL C207
We study a boundedly rational approach to extensive form games by valuations (Jehiel 2007). Differing from standard microeconomics, players are unable to foresee the whole game tree, but group “similar” actions together (for example the same move in similar positions of a chess game) and attach a valuation to each of these groups. Our aim is to analyze how the partitioning into groups emerges and which equilibria satisfy a certain robustness criterion.
Problem Chess and Mathematics
Hans-Peter Rehm, Karlsruhe
PROBLEM CHESS AND MATHEMATICS
Sa., 17:00, TU Dresden, WIL C207
The role of symmetries of different kinds of the Chess Space and the set of thematical moves for the aesthetical value of chess compositions.
- Symmetry and asymmetry in position and thematical contents.
- Themes concerning the action of the symmetrical group on the set of played moves in a composition.
Generalized Chess in chess problem composition.
- Other chess spaces (e.g. the three dimensional STEREO CHESS)
- Other kinds of pieces and rules.
Databases for Chess Problems
Torsten Linß, Limerick
DATABASES FOR THE COMPOSITION OF CHESS PROBLEMS
Sa., 17:45, TU Dresden, WIL C207
Databases (or endgame table bases) have been used in the analysis of the game of chess. Some of these EGTB by Herik, Thompson and Nalimov are available online and are used in some chess engines. In chess composition they have been used since the early 1970s (Mertens, with some earlier examples from the 1940s and 1950s by Halumbirek who used paper as main memory and his brain as processor).
The focus in chess composition is quite different from over-the-board competetive chess: it is the artistic value of the compositions (chess problems and studies) one is interested in. Apparently, databases can be used to verify the soundness of a composition, i.e. that there is only the solution intended by the authors, but they can also be searched for interesting problems. The latter often means to find the needle in a stack of hey of some millions of formally sound chess problems - with no clear/programmable definition at hand what constitutes an interesting problem.
In the talk the author will elaborate on these issues and present some (very) preliminary results.
Die Schachwelt im Internet
Rolf Beran, Altlandsberg
DIE SCHACHWELT IM INTERNET
Sa., 18:05, TU Dresden, WIL C207 (German)
Das Internet als Quelle für:
- Spieleplattformen (zum online-Schachspielen)
- Partiedatenbanken (zur gegnerspezifischen Vorbereitung, zur Auswahl von Theorievarianten, zur Analyse von Beispielpartien)
- Turnier- und Ergebnisdatenbanken (für statistische und historische Informationen)
- Einkauf (zur Beschaffung aktueller und antiquarischer Literatur, Spielmaterial)
- Schach-Linksammlungen (zur Orientierung und Suche nach weiterführenden Informationen)
- Personenbezogene Seiten (für biografische Informationen)
- Thematische Seiten (zur Vertiefung spezieller Eröffnungen)
- Aktuelle Berichterstattung und live-Übertragungen
- Audiovisuelle Medien (Schachvideos bei youtube, Kurzanleitung zur Herstellung eigener Schachvideos zu Lehrzwecken)
- Hintergrundwissen/Sonstiges (z.B. was sind pgn-Dateien?, wie wird die Elo-Zahl berechnet?)
References
- ↑ CHESS AND MATHEMATICS - Workshop Dresden, 21st - 23rd November 2008
- ↑ Workshop Chess and Mathematics (pdf) agenda and abstracts
- ↑ Prof. Dr. Christian Hesse from Universität Stuttgart
- ↑ Schach: Flow und mathematisches Modell, Interview mit Professor Christian Hesse, ChessBase News, November 15, 2008 (German)
- ↑ Yngvi Björnsson, Tony Marsland (2001). Multi-cut Alpha-Beta Pruning in Game Tree Search. Theoretical Computer Science, Vol. 252, pp. 177-196. pdf
- ↑ AAAI'08 Tutorial General Game Playing, Michael Thielscher, Dresden (pdf)
- ↑ Bernd Steinbach, Christian Posthoff (2007). Set-Based SAT-Solving. pdf
- ↑ Bernd Steinbach, Christina Dorotska (2000). Orthogonal Block Building Using Ordered Lists of Ternary Vectors. Freiberg University of Mining and Technology, pdf
- ↑ Jaap van den Herik « Glarean Magazin | Ist im Jahr 2035 Schluss mit Schach? by Eric van Reem, January 2009 (German)