All checkmate positions possible

[DustinYoder]

I'm wondering if it would be possible to find all legal (not necc. legally reachable) checkmate position involving the standard 48 chess pieces (no pawn conversions) or less where white is the winner only.

Would it be possible to write a program that could create a list of all these checkmate positions without having to brute force through every board combination?

[Sven]

I'm wondering if it would be possible to find all legal (not necc. legally reachable) checkmate position involving the standard 48 chess pieces (no pawn conversions) or less where white is the winner only.

Would it be possible to write a program that could create a list of all these checkmate positions without having to brute force through every board combination?

About which game are you talking? Standard chess is played with 16 white and 16 black pieces, that makes 32, not 48

Regarding your questions: yes, it is possible in theory but the memory requirements to achieve this in practice prevent you, me and all of our next descendants from ever being able to see the result. Either there is not enough memory for the calculation itselt, or the calculation takes too long to terminate in time for us.

Whether it is possible "without brute force" is not known today, the usual techniques are based on enumerating "all" positions within a given context.

Currently all endgames with up to 6 pieces and some with 7 pieces are solved. The solution consists of a bitbase, tablebase or something like this, and implicitly contains the list of won positions for a given piece configuration. Here is one link if you are interested to know more about endgame tablebases.

Sven

[DustinYoder]

Right 32. ithats what I meant. So what percentage of games end up in an endgmae that exists in a tablebase?

[wgarvin]

Whether it is possible "without brute force" is not known today, the usual techniques are based on enumerating "all" positions within a given context.

And if the context is "32 or fewer pieces on the board" you'd probably have to enumerate about 10^47 positions (give or take a few orders of magnitude). The state space of chess is really really large.

For comparison, the universe is estimated to be less than 10^18 seconds old, and a "petaflop" is 10^15 floating-point operations per second. So if you took the best supercomputer that exists today, and added a magic circuit allowing it to construct an entire chess position and test it for checkmate just as fast as it could do the simple operation of multiplying two numbers together, and you then took it back in a time machine until the moment after the Big Bang, and set it to enumerate all positions and count all of the checkmates, and then let it run for over 13 billion years until one day our solar system has been created and Earth has a biosphere and humans have evolved sentience and discovered somehow that the machine is out there... it would still have explored only a tiny fraction of 1% of all of the possible positions.

[FlavusSnow]

Can't we just sell the time machine?

I can think of better things to do with a time machine...

[zamar]

And if the context is "32 or fewer pieces on the board" you'd probably have to enumerate about 10^47 positions (give or take a few orders of magnitude). The state space of chess is really really large.

Oh come on, don't be so pessimistic!! I'm sure we can develop some rules to skip large number of positions, so in the end we may need to examine only something around 10^40 - 10^43 positions.

[kbhearn]

Given that what you want isn't path-to-mate, but rather just what could mates look like, it should be rather more manageable than iterating through all positions. You have 32 relevant positions for the black king(left-right mirroring, can't use any other symmetries because of pawns), find the various combinations of white pieces that can create unique checkmates. Add in black blockers adjacent to own king for smothering effects square by square, and find which additional checkmates this allows, determine rules on which blockers must not be of a certain type or be pinned. Then with all these positions, get a list of squares particular black pieces cannot be on lest they be able to intervene. And finally the set of squares white pieces cannot be on lest they be in the way of your own pieces. These last couple steps would increase the number of positions exponentially (we're headed back to a task that takes as long as the age of the universe again) if you actually tried to enumerate them so you'd want to just store them as 'rules' and not break them out into all the different ways the pieces could be arranged. Now what value finding this 'list' would have, i have no clue ;)

[Don]

I'm wondering if it would be possible to find all legal (not necc. legally reachable) checkmate position involving the standard 48 chess pieces (no pawn conversions) or less where white is the winner only.

Would it be possible to write a program that could create a list of all these checkmate positions without having to brute force through every board combination?

There are massive shortcuts possible, but essentially you would be enumerating all positions and the number of possible positions is greater than the number of grains of sand on the beach as they say.

By reasoning about the position you could take many shortcuts, but I'm sure this is intractable. There is probably not enough space to store all the mate positions on all the hard drives in the world.

A more interesting version of this is to find all checkmates with no unnecessary pieces on the board. For example the "standard" back rank mate with a king on g8 and rook only require the rook giving the mate, the black king and the 3 black pawns blocking the escape squares.

Image however that some of these pawns could be replaced with other pieces - the h pawn could be any piece except a knight for example.

So YOU could try to enumerate all possible mates ignoring non-essential pieces to get many many orders of magnitude less data but even with this is it still intractable.

A final try is to classify all possible mates by theme. You would have to create your own classification system, but you could get substantial savings by not obsessing over the exact square that a piece delivers mate on, for example. A back rank mate works whether the rook is on a8, b8, c8, d8 or e8 (assuming the king is on g8.) Of course this changes if an enemy can interpose a piece but you ignoring those positions.

I think the bottom line here is that you cannot hope to do this unless you generalize to the extreme.






A little outline of how this might be done is to consider first the king location and ignore all equivalent symetries. There are only 10 canonical king locations. THEN consider the piece giving a mate - you could cycle through all combinations of pieces giving a mate. Then you have to consider all the escape square of the king

[wgarvin]

A little outline of how this might be done is to consider first the king location and ignore all equivalent symetries. There are only 10 canonical king locations. ...

A quibble... that's only true if there are no pawns left. If either side still has pawns, you only have 2-fold symmetry and 32 canonical king locations.

[Don]

A little outline of how this might be done is to consider first the king location and ignore all equivalent symetries. There are only 10 canonical king locations. ...

A quibble... that's only true if there are no pawns left. If either side still has pawns, you only have 2-fold symmetry and 32 canonical king locations.

I did not even intend to include that paragraph, but you are right. My idea was to start with the king location, but iterate by the number of white and black pieces. So you could at least start with the simplest of positions (for ALL fully legal positions.) So you would have nested loops where you considered 1 black piece (the king) and 1 while piece (the checkmating king) and then 1 black piece and 2 while pieces, then 2 black pieces and 1 white piece, etc.

Of course there are no mates with only 1 white piece (the king) on the board against black, but it would make sense to progress in clearly defined stages like this. You could do it with total piece count started at 3 also.

So like endgame database you could work your way towards more complicated positions. I think the loop should first consider every possible piece that could give check near the top. So for each king location consider each white pawn, knight, bishop, rook or queen that could give check - then start placing pieces around that.

The problem might be almost doable with the use of "wild cards", if you could identify squares where it does not matter what kind of pieces are sitting there. Nahhh I think it's still way too much.