Solving Chess

[hgm]

What is your database? Mysql, or is there a common type used in chess progams? Do you use a hash to look up the correct board position?

I guess he is building a regular tablebase, where positions map into numbers according to a given formula (the so called indexing scheme), and the tablebase is simply a binary file of 8-bit numbers, representing the distance to mate.

[Kirill Kryukov]

What is your database? Mysql, or is there a common type used in chess progams? Do you use a hash to look up the correct board position?

Hi Dustin,

Usually people implement custom databases to maximize performance, so no, SQL is not used in my or any other chess endgame databases that I know of. For looking up the positions, commonly people create some arcane index functions. For example you can read about Nalimov's indexing here (click on "PDF"). My index is different (I did not discuss it in detail yet), but the big idea in all these databases is very similar and goes back to Ken Thompson's 1986 study (perhaps even earlier).

Why don't you introduce your idea?

[bob]

What is your database? Mysql, or is there a common type used in chess progams? Do you use a hash to look up the correct board position?

No, you commonly compute what is called the "Godel" (wrong character for e but I am not going to figure out how to enter it correctly) number and use that as an index into a file, as is done in egtb accesses today.

[Edmund]

What is your database? Mysql, or is there a common type used in chess progams? Do you use a hash to look up the correct board position?

No, you commonly compute what is called the "Godel" (wrong character for e but I am not going to figure out how to enter it correctly) number and use that as an index into a file, as is done in egtb accesses today.

ö

Feel free to copy.

[hgm]

Do you make any assumption on the maximum number of pieces, for considering a mini-variant as 'solved'? I took a look at your web pages, and it seems you allow the entire board to be crammed with pieces. That seems a little bit unnatural. We generally would consider FIDE Chess solved if we had a 32-men tablebase. A 64-men tablebase would not be required.

In analogy with 5x5 shogi, wouldn't this be a logical starting position for 4x4 Chess:

[d]8/8/8/8/kbnr4/p7/3P4/RNBK4 w

[Kirill Kryukov]

Do you make any assumption on the maximum number of pieces, for considering a mini-variant as 'solved'? I took a look at your web pages, and it seems you allow the entire board to be crammed with pieces. That seems a little bit unnatural. We generally would consider FIDE Chess solved if we had a 32-men tablebase. A 64-men tablebase would not be required.

In analogy with 5x5 shogi, wouldn't this be a logical starting position for 4x4 Chess:

8/8/8/8/kbnr4/p7/3P4/RNBK4 w

For an already existing small board game it can make sense to just solve the subset reachable from the starting position. However there is no any established 4x4 chess game, so I am simply solving it as a puzzle. Here the logic is the opposite. First comes the solution, then we will know which starting positions can be interesting. No limit on number or composition of the pieces. Although it won't be easy or quick.

With shogi a meaningful and deep game is possible even on a tiny board. Dobutsu Shogi is one example (3x4 board), and I also know at least one interesting 3x3 shogi variant. In small board chess however, any single starting position would be relatively trivial. After figuring it out once you won't play it over and over again. So analyzing the whole multitude of possible positions makes more sense to me. On 3x3 and 3x4 boards it was trivial of course, and 4x4 chess is suddenly more challenging. Perhaps I'll just do up to 9 or 10 pieces, not sure yet.

[hgm]

Well, your last remark was my point, actually. Even if you want to select the starting position afterwards, would it make sense to select it from all 16-men tablebases (on 4x4) or can you already limit it in advance to the sub-set of 10-men positions? That would make a huge difference.

[DustinYoder]

Well indexing will not work to solve chess as there would be required far to many unique indexes. My solution requires no index and would only need room for winning moves, others would be deleted as they found to be moves not leading to a win. This is the first important method in my theory.
So maybe from your tests you could estimate how many of your board positions could safely be removed as positions without forced wins? Half? Quarter?

[Kirill Kryukov]

Well, your last remark was my point, actually. Even if you want to select the starting position afterwards, would it make sense to select it from all 16-men tablebases (on 4x4) or can you already limit it in advance to the sub-set of 10-men positions? That would make a huge difference.

Without a pre-existing 4x4 chess game, setting a limit on number or pieces would be arbitrary. Other than practical limitations there is no reason to limit to 10 pieces. So I'll just solve as much as I can, and not try to find any good-sounding excuse. If I can't solve 11 pieces, than that and only that will be my reason for 10-piece limit.

[hgm]

So maybe from your tests you could estimate how many of your board positions could safely be removed as positions without forced wins? Half? Quarter?

I would be inclined to say: less than 0.01%?

Of all positions, balanced positions are really very much the exception. Even if you just look at material composition, there are many ways to assign material in an unbalanced way than in an unbalanced way. Even if you only look at Pawn endings, there are 9 possible numbers of Pawns for white, (0-8), 9 for black, so 81 possible Pawn endings. Only 9 of them (0-0, 1-1, ... 8-8) have equal material. That is just 11%. Including orther pieces in the equation drives that down even further.

And even with equal material, most positions will not be draw. In KQKQ, for instance, the side to move almost always wins, by capturing the opponent's unprotected Queen.

Drawn positions form a very narrow ridge between the abysses of white and black wins.