I'm teaching a group of kids about chess (they're pretty computer literate) and one of the things I'm showing them is how to use programs like Chessbase or others to analyze their games. In doing this, I thought that giving them a lecture about tablebases would be kindof interesting. Would anyone know of any simplistic (for smart 10 year olds) explanations of how they're made, especially with pictures (showing how symmetry reduces the size of things and speeds things up).
Also looking for a simple example of how a tablebase is made (unless I get a better idea, I'll just start out with a simple KQK mate and then show them how to work backwards from that).
The computer I'm lecturing from has ChessBase 9 and Rybka 2.2 with the 5 piece (with pawns) tablebases installed and working. Would anyone have any good positions that would be interesing (not only 5 piece but even some with a lot more pieces that reduce to 5 pieces quick enough to make the tablebases useful.)
Tablebase lecture
-
Kirill Kryukov
- Site Admin
- Posts: 7399
- Joined: Sun Dec 18, 2005 9:58 am
- Sign-up code: 0
- Location: Mishima, Japan
- Contact:
Re: Tablebase lecture
This thread has some good positions for showing the usefulness of tablebases.
KCEC | EGTB Online | 3x3 Chess | 3x4 Chess | 4x4 Chess | Longest Checkmates | EGTB Test Suite | Opening Sampler | EGTB Bounty | NULP
-
guyhaw
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Re: Tablebase lecture
viewtopic.php?f=6&t=3083 ... KK's thread on an 'EGTB Test Suite' is perhaps what KK had in mind.
KK, even though obviously everything is a draw, focuses on topics like:
- the number of physically different positions: what is a 'biggest figure' (wtm/btm ...2*64*63), can we reduce this upper limit?
- how we might number the squares of the board and associate a two-number [vector] with each positions
- the number of 'dimensions' of the 'space of KK positions' - two
- how we might turn this 'two number' into one number so that each two-number goes to a different number [1-1 mapping]
- physical position and logical position: turns of the board change the physical position but not the logical position
- [the 'group' of rotations of the board may be one for last-year school-children really into mathematics]
- the consequent reduction in the number of positions we need to consider
- the a1-h8 flip of the board being a transformation of the board that is not in the set of rotations of the board
- [the group of transformations of the board is now size 8: the group of rotations is size 4]
- the consequent reduction in the number of positions we need to consider
- one final symmetry: since both sides have the same men (a K), we need only keep a White-to-move version of the table
- again, we have reduced the number of positions to consider by a factor of 2
- a puzzle is how many 'legal' (and logically different) positions there actually are
- the idea of illegal positions - 'checks' by the stm, in this case, the Kings being right next to each other
- Nalimov's clever idea for reducing the number of physical positions to be indexed: avoid unblockable 'checks' by the stm
- the need for a rule in chess ... namely that if mate cannot be forced in any way, the game-result is defined to be a draw
KBK and KNK, even though there are still no wins, focus on:
- the number of 'dimensions' of the 'space of KBK positions' - three
- a three-number [vector] rather than a two-number: how doe we turn each of these into a unique number?
- despite all our tricks for reducing the number of positions the computer has to remember, the number has gone up by a factor of about 62
- the idea of 'illegal positions' where the
- the 'defined draw' rule is required for these endings
KNKN
- this is a fun one: White can only mate Black if Black has been very unlucky or very silly (or is trying to catch a bus)
- so there are a few wins in this endgame
- so, the 'defined draw' rule does not apply here ... see the WWCC2008 video from Nalchik of the tournament arbiter not understanding this!
- how many dimensions (4), upper limit on number of positions
- there's a neat point here: when one side only has Ns, all the illegal positions with this side to move can be avoided by the Nalimov idea
- this is because checks by the N cannot be blocked
KQK now brings in the idea of finding wins by a 'backwards progression', the concept of 'depth of win' and maximum depth (which must 'exist')
- lots of physical positions have to be indexed, and they are not avoided by Nalimov's idea [but they could have been - how]
The R is less mobile than the Q, and so - no surprise - maxDTM for KRK is greater than KQK. Still just 3 dimensions.
KPK brings in several new ideas:
- the number of transformations of the board is now reduced to one, namely 'a becomes h'
- there are draws as well as wins,
- the concept of positions being 'next' to each other can be defined in two ways: one man has moved one square [or next in the indexing of positions]
- with the first concept of 'next', there will be a drawn position and a won position right 'next' to each other.
- this has to be true for all endgames featuring both wins and draws.
- KPK can only be computed after KBK, KNK, KQK, KRK have been computed (and they were done after KK was computed)
- this idea of some endgames 'being after' others is what makes the computation of EGTs possible in the first place
- is there a position where conversion of the Pawn to a Queen is a bad idea - yes - 8/k1P5/8/1K6/8/8/8/8 w.
- different definitions of depth: 'Depth to Conversion' rather than 'Depth to Mate'
- ... and even 'Depth to move-count Zeroing move' (P-push and/or capture) as these moves are irreversible too and move the game into its 'next phase'.
What other games than chess allow EGTs to be computed:
- Checkers, Nim, Noughts and Crosses [maybe the simplest to illustrate], Awari [solved with a giant EGT]
KBBK brings in the idea of 'sets of like men' and the consequent reduction in the number of positions. An ambitious concept is how to number these arrangements of the 2 Bishops. See 'The Unique Triangle' thread on this board. Take a look at maxdepth.
A spreadsheet of stats (which I maintain) about EGT'd endgames in on the International Computer Games Assoc (ICGA) website under 'Game-specific information ... Western Chess ... Endgames'. There are illustrative max-depth positions there. www.icga.org
KQKR brings in the idea of an endgame which can frustrate really good chess players. maxDTC = 31 and, with only 50 moves to get to capture the Rook, this is perhaps an endgame best avoided!
There are 7-man endgames with EGTs, none publicly available, that show that maxDTC can be as high as 517 moves.
Really, there is a lot of good material in the chess endgame if one is teaching discrete mathematics to children (without telling them that this is what it is).
There are also published papers going into the details of EGT generation, and showing what ideas people had and what mistakes they made.
g
KK, even though obviously everything is a draw, focuses on topics like:
- the number of physically different positions: what is a 'biggest figure' (wtm/btm ...2*64*63), can we reduce this upper limit?
- how we might number the squares of the board and associate a two-number [vector] with each positions
- the number of 'dimensions' of the 'space of KK positions' - two
- how we might turn this 'two number' into one number so that each two-number goes to a different number [1-1 mapping]
- physical position and logical position: turns of the board change the physical position but not the logical position
- [the 'group' of rotations of the board may be one for last-year school-children really into mathematics]
- the consequent reduction in the number of positions we need to consider
- the a1-h8 flip of the board being a transformation of the board that is not in the set of rotations of the board
- [the group of transformations of the board is now size 8: the group of rotations is size 4]
- the consequent reduction in the number of positions we need to consider
- one final symmetry: since both sides have the same men (a K), we need only keep a White-to-move version of the table
- again, we have reduced the number of positions to consider by a factor of 2
- a puzzle is how many 'legal' (and logically different) positions there actually are
- the idea of illegal positions - 'checks' by the stm, in this case, the Kings being right next to each other
- Nalimov's clever idea for reducing the number of physical positions to be indexed: avoid unblockable 'checks' by the stm
- the need for a rule in chess ... namely that if mate cannot be forced in any way, the game-result is defined to be a draw
KBK and KNK, even though there are still no wins, focus on:
- the number of 'dimensions' of the 'space of KBK positions' - three
- a three-number [vector] rather than a two-number: how doe we turn each of these into a unique number?
- despite all our tricks for reducing the number of positions the computer has to remember, the number has gone up by a factor of about 62
- the idea of 'illegal positions' where the
- the 'defined draw' rule is required for these endings
KNKN
- this is a fun one: White can only mate Black if Black has been very unlucky or very silly (or is trying to catch a bus)
- so there are a few wins in this endgame
- so, the 'defined draw' rule does not apply here ... see the WWCC2008 video from Nalchik of the tournament arbiter not understanding this!
- how many dimensions (4), upper limit on number of positions
- there's a neat point here: when one side only has Ns, all the illegal positions with this side to move can be avoided by the Nalimov idea
- this is because checks by the N cannot be blocked
KQK now brings in the idea of finding wins by a 'backwards progression', the concept of 'depth of win' and maximum depth (which must 'exist')
- lots of physical positions have to be indexed, and they are not avoided by Nalimov's idea [but they could have been - how]
The R is less mobile than the Q, and so - no surprise - maxDTM for KRK is greater than KQK. Still just 3 dimensions.
KPK brings in several new ideas:
- the number of transformations of the board is now reduced to one, namely 'a becomes h'
- there are draws as well as wins,
- the concept of positions being 'next' to each other can be defined in two ways: one man has moved one square [or next in the indexing of positions]
- with the first concept of 'next', there will be a drawn position and a won position right 'next' to each other.
- this has to be true for all endgames featuring both wins and draws.
- KPK can only be computed after KBK, KNK, KQK, KRK have been computed (and they were done after KK was computed)
- this idea of some endgames 'being after' others is what makes the computation of EGTs possible in the first place
- is there a position where conversion of the Pawn to a Queen is a bad idea - yes - 8/k1P5/8/1K6/8/8/8/8 w.
- different definitions of depth: 'Depth to Conversion' rather than 'Depth to Mate'
- ... and even 'Depth to move-count Zeroing move' (P-push and/or capture) as these moves are irreversible too and move the game into its 'next phase'.
What other games than chess allow EGTs to be computed:
- Checkers, Nim, Noughts and Crosses [maybe the simplest to illustrate], Awari [solved with a giant EGT]
KBBK brings in the idea of 'sets of like men' and the consequent reduction in the number of positions. An ambitious concept is how to number these arrangements of the 2 Bishops. See 'The Unique Triangle' thread on this board. Take a look at maxdepth.
A spreadsheet of stats (which I maintain) about EGT'd endgames in on the International Computer Games Assoc (ICGA) website under 'Game-specific information ... Western Chess ... Endgames'. There are illustrative max-depth positions there. www.icga.org
KQKR brings in the idea of an endgame which can frustrate really good chess players. maxDTC = 31 and, with only 50 moves to get to capture the Rook, this is perhaps an endgame best avoided!
There are 7-man endgames with EGTs, none publicly available, that show that maxDTC can be as high as 517 moves.
Really, there is a lot of good material in the chess endgame if one is teaching discrete mathematics to children (without telling them that this is what it is).
There are also published papers going into the details of EGT generation, and showing what ideas people had and what mistakes they made.
g
-
guyhaw
- Posts: 489
- Joined: Sat Jan 21, 2006 10:43 am
- Sign-up code: 10159
- Location: Reading, UK
- Contact:
Footnotes to the above
This board was started by Kirill Kryukov, 'KK'. Quite good initials for the Chess Endgame, I think 
.
The EGTs produced so far have not considered castling rights. Indeed, no game has retained any castling rights as far as the 49th move, but there have been castlings on the 48th. So the motivation to include castling rights is not high. However, a question is 'How many sets of positions are there within an endgame, differentiated by castling rights?'. The answer is of course 16, '----', '---q', '--k-', '--kq' etc ( you can see a binary numbering going on here).
A position where castling rights matter: 8/8/8/8/3k4/8/1r6/R3K3 w Q - 0 1. 1.O-O-O uniquely wins.
The concept of depth brings in questions like 'what is the metric?'. Nalimov uses winner's-moves-to-goal rather than plies-to-goal, and this involves 'information loss'. There are positions where the loser is forced to capture: these affect the DTC and DTZ metrics - depth is '0' in moves and '1' in plies, and this can affect the set of maximal positions in 'extreme' endgames like KQQQK. Christoph Wirth adopted code that assumed that the attacker always did the capture, as a result of which his DTC results were slightly wrong.
Different metrics mean that the set of moves which optimally reduce depth by 1 can be different, even in endgames like KRRK.
6R1/8/8/8/8/8/2R5/K2k4 b - - 0 1: DTC = DTZ = 1 but DTM = 11 - 1...Kxc2 is DTM-optimal but 1...Ke1 is DTC/Z optimal.
I think there are positions where the DTC-, DTM- and DTZ-optimal moves are all different but one does not come to mind immediately.
Certainly, if the 50-move rule is considered in a 'DTZ50' EGT, there are positions where the DTC/M/Z-optimal move only draws!
EGTs have been produced on a WDL, value-only, basis: see SHREDDER's Shredderbases. These are 'Bitbases', requiring only 2 bits per position. They are obviously more compact, can fit into RAM for 5-man endgames and are useful in helping decide whether it is even necessary to go to the disc to find out the depth of a position. Certainly, my observations are that SHREDDER is quicker when armed with its Bitbases but SM-K has not produced a paper on the quantitative difference yet.
EGTs have been constructed for different m*n shapes of boards, with and without 'fairy pieces', e.g. more exotic Knight-like (a, b) Leapers. Chess without Fairy Pieces on 3*3 ... 6*6 boards is interesting, and historically - the first Man-Machine (actually Woman-Machine) match was on a 6*6 board.
'Mathematics Chess' in Amazon reveals:
http://www.amazon.co.uk/Mathematics-Che ... 253&sr=8-1
I don't know this book - looks expensive for an 11-year-old paperback: maybe it's amazingly good.
http://www.amazon.co.uk/Across-Board-Ma ... 253&sr=8-2
I had this book and donated it to a colleague's (mathematically et al) clever son. Must get another copy. A lot of stuff for older children, like me.
Google on Mathematics and Chess turns up Wolfram Mathworld and other interesting stuff which is well grounded.
http://www.k4it.de/index.php?topic=egtb&lang=en is Eiko Bleicher's EGT site - DTM only but all available DTM EGTs.
http://chess.jaet.org/cgi-bin/dtx is John Tamplin's site which he created when working with me on EGTs some years ago.
Plenty of arguments as to the didactic benefits of Chess (esp. re Maths), but including unqualified ones (not considering 'cost') from those in 'The Chess Business' with a living to earn and an agenda to follow. I believe chess helped me learn to think, and I'm glad I didn't get obsessed about it as a child. It doesn't teach the value of co-operation or teamwork as its 'I win, you lose' goals are opposite to that.
Little has been done to 'mine' higher-level nuggets of knowledge from the mass of perfect but basic and raw data. Attempts to write computer-systems to infer what the higher-level rules might be have proved to be most frustrating - even for endgames like KRK. An algorithm of high-level decision-rules tends to have to ferret away into smaller and smaller corner of the KRK-space. Chess-engines tend to play less than well in endgames, and it would be intereseting to compare how they get on without EGTs.
Something I am working now is the question 'How important is this position 'p', or this set of positions 'P'? What if they were not all wins for White: how would that change things?
g
.The EGTs produced so far have not considered castling rights. Indeed, no game has retained any castling rights as far as the 49th move, but there have been castlings on the 48th. So the motivation to include castling rights is not high. However, a question is 'How many sets of positions are there within an endgame, differentiated by castling rights?'. The answer is of course 16, '----', '---q', '--k-', '--kq' etc ( you can see a binary numbering going on here).
A position where castling rights matter: 8/8/8/8/3k4/8/1r6/R3K3 w Q - 0 1. 1.O-O-O uniquely wins.
The concept of depth brings in questions like 'what is the metric?'. Nalimov uses winner's-moves-to-goal rather than plies-to-goal, and this involves 'information loss'. There are positions where the loser is forced to capture: these affect the DTC and DTZ metrics - depth is '0' in moves and '1' in plies, and this can affect the set of maximal positions in 'extreme' endgames like KQQQK. Christoph Wirth adopted code that assumed that the attacker always did the capture, as a result of which his DTC results were slightly wrong.
Different metrics mean that the set of moves which optimally reduce depth by 1 can be different, even in endgames like KRRK.
6R1/8/8/8/8/8/2R5/K2k4 b - - 0 1: DTC = DTZ = 1 but DTM = 11 - 1...Kxc2 is DTM-optimal but 1...Ke1 is DTC/Z optimal.
I think there are positions where the DTC-, DTM- and DTZ-optimal moves are all different but one does not come to mind immediately.
Certainly, if the 50-move rule is considered in a 'DTZ50' EGT, there are positions where the DTC/M/Z-optimal move only draws!
EGTs have been produced on a WDL, value-only, basis: see SHREDDER's Shredderbases. These are 'Bitbases', requiring only 2 bits per position. They are obviously more compact, can fit into RAM for 5-man endgames and are useful in helping decide whether it is even necessary to go to the disc to find out the depth of a position. Certainly, my observations are that SHREDDER is quicker when armed with its Bitbases but SM-K has not produced a paper on the quantitative difference yet.
EGTs have been constructed for different m*n shapes of boards, with and without 'fairy pieces', e.g. more exotic Knight-like (a, b) Leapers. Chess without Fairy Pieces on 3*3 ... 6*6 boards is interesting, and historically - the first Man-Machine (actually Woman-Machine) match was on a 6*6 board.
'Mathematics Chess' in Amazon reveals:
http://www.amazon.co.uk/Mathematics-Che ... 253&sr=8-1
I don't know this book - looks expensive for an 11-year-old paperback: maybe it's amazingly good.
http://www.amazon.co.uk/Across-Board-Ma ... 253&sr=8-2
I had this book and donated it to a colleague's (mathematically et al) clever son. Must get another copy. A lot of stuff for older children, like me.
Google on Mathematics and Chess turns up Wolfram Mathworld and other interesting stuff which is well grounded.
http://www.k4it.de/index.php?topic=egtb&lang=en is Eiko Bleicher's EGT site - DTM only but all available DTM EGTs.
http://chess.jaet.org/cgi-bin/dtx is John Tamplin's site which he created when working with me on EGTs some years ago.
Plenty of arguments as to the didactic benefits of Chess (esp. re Maths), but including unqualified ones (not considering 'cost') from those in 'The Chess Business' with a living to earn and an agenda to follow. I believe chess helped me learn to think, and I'm glad I didn't get obsessed about it as a child. It doesn't teach the value of co-operation or teamwork as its 'I win, you lose' goals are opposite to that.
Little has been done to 'mine' higher-level nuggets of knowledge from the mass of perfect but basic and raw data. Attempts to write computer-systems to infer what the higher-level rules might be have proved to be most frustrating - even for endgames like KRK. An algorithm of high-level decision-rules tends to have to ferret away into smaller and smaller corner of the KRK-space. Chess-engines tend to play less than well in endgames, and it would be intereseting to compare how they get on without EGTs.
Something I am working now is the question 'How important is this position 'p', or this set of positions 'P'? What if they were not all wins for White: how would that change things?
g
Re: Tablebase lecture
Before diving in too deeply, it is probably good to first explain the basic concept. A tablebase doesn't store a list of (all) positions with for each position the best move, but it assigns to each position an index value 0 ... N-1 and stores an array of N values (one value of each index value 0 ... N-1). The value stored for a position corresponds to the outcome of this position. For example a value of 0 stands for a draw, a value of +1 stands for a win in 1 move (i.e. mate in 1), a value of -1 stands for a loss in 1 move, etc. Now the big trick is that you can find the best move (or "a best move") for a position by trying out each move and comparing the results. (I left out that you'll need separate arrays or tables for white-to-move and black-to-move.)
I think this is not at all trivial even for smart 20 year olds (unless they've thought about this type of thing before). It will probably help a lot if they already know a bit about programming.
I think this is not at all trivial even for smart 20 year olds (unless they've thought about this type of thing before). It will probably help a lot if they already know a bit about programming.