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