maximum niumber of legal moves

[Fabien Letouzey]

Oops if you accept illegal positions then, the position with the maximum moves in a context of men positions (no kings) is not a position with captures but simply the obvious following one :

...
45 moves

It looks like we're having two conversations with no connections so let me clarify. In this thread you ask a vague question about the maximum number of captures. By contrast, Rein describes very precisely his idea:

The math is pretty easy: a capture victim can only sit in the inner 8x8 board, so 32 squares. You can capture at most 19 men, so you need all binom(32, i) for i = 1 through 19, which is 4 billion positions. Then you put up to 3 or 4 kings on the edges (18 squares), so binom(18, i) for i = 1 through 4, which is 4K positions, so 1.6 10^13, pretty big but comparable to generating 8 pc dbs. If you just fix the number of men to 10 and kings to 3, it's only 52 billion positions.

That's much better and very easy to do (< 1 hour) so I did it, except that I used random search. There's nothing more to it: I have little interest in the question itself (especially not for BT draughts where those numbers will always be tiny) nor studying position reachability. That being said, the latter could be used to compress endgame tables further, assuming that's not already standard.

[TAILLE]

Oops if you accept illegal positions then, the position with the maximum moves in a context of men positions (no kings) is not a position with captures but simply the obvious following one :

...
45 moves

It looks like we're having two conversations with no connections so let me clarify. In this thread you ask a vague question about the maximum number of captures. By contrast, Rein describes very precisely his idea:

The math is pretty easy: a capture victim can only sit in the inner 8x8 board, so 32 squares. You can capture at most 19 men, so you need all binom(32, i) for i = 1 through 19, which is 4 billion positions. Then you put up to 3 or 4 kings on the edges (18 squares), so binom(18, i) for i = 1 through 4, which is 4K positions, so 1.6 10^13, pretty big but comparable to generating 8 pc dbs. If you just fix the number of men to 10 and kings to 3, it's only 52 billion positions.

That's much better and very easy to do (< 1 hour) so I did it, except that I used random search. There's nothing more to it: I have little interest in the question itself (especially not for BT draughts where those numbers will always be tiny) nor studying position reachability. That being said, the latter could be used to compress endgame tables further, assuming that's not already standard.

Hi Fabien,
I guess my english wording was not very correct (sorry for that) because my initial question was not that vague at least in my head.

I showed the position

120 legal moves
and every body can see very easily that the position is a legal one because you can see the possible last black move 10-4 (promotion).

Should my quesion have concerned non legal position I would have begun by showing the following quite simple position

128 moves

In my head my question was about still a legal position but with captures.
I was a little upset by Rein post because it was not really in line with my question but, anyway it was also interesting wasn't it?

Of course I quite understand you prefer Rein approach and I undertand you do not see a great interest in legal positions.

Curiously Rein himself told us he "made a proof game of a position where a white king captures 19 black men: viewtopic.php?f=65&t=276&p=122166#p122166"
As a consequence I do not know if Rein is only interested by theoritical (non legal) positions or is also interested by the maximum moves we can reach for a legal position.

In any case thank you for your contribution Fabien.

[Fabien Letouzey]

Hi Gérard,

Should my quesion have concerned non legal position I would have begun by showing the following quite simple position

128 moves

You are playing with words. For me the "obvious" properties that a position must have are:
- at most one piece on a given square (sounds obvious, but draughts FEN does not enforce this syntactially so we have to state it explicitly)
- no man on the last rank
- not more than 20 pieces for one side
- at least one piece for the side who just moved

Are those arbitrary "Fabien's definition of legal positions"? I don't think so. For one thing, it's easy to imagine a program, especially array based, crashing if one of those is not met. This is the computer subforum, after all. We often make assumptions like these in advanced implementations, so we'd better check them. As another example, we all use those conditions when enumerating positions to build endgame tables. Or do you stay true to your definition?

So why choose the "wrong" definition (above), then? I claim that it's mathematically superior. It's easy to check (even without thinking about it), does not go haywire when we make a small change in the position (e.g. taking hours to check), and programs will generally behave in a predictable manner when the conditions are met (interestingly enough, with the possible exception of an astronomical number of captures, including Scan).

Of course I quite understand you prefer Rein approach and I undertand you do not see a great interest in legal positions.

Indeed I argue above that your definition of a legal position (reachability) is not easily manipulated either by humans or programs. I can imagine, with a lot of implementation effort, an optimised algorithm for this problem, but it will still occasionally choke for a long time on difficult positions, presumably near the frontier between reachable and unreachable. Furthermore, it would serve no purpose similar to protecting programs from crashes.

Fabien.

[ildjarn]

For me the "obvious" properties that a position must have are:
- not more than 20 pieces for one side

I agree with the other criteria, but not this one. Draughts programs are not just used for games, but also to check composed positions for correctness (that's the main usage for me at least). And a composed position can have more than 20 pieces of one side.

[Fabien Letouzey]

I agree with the other criteria, but not this one. Draughts programs are not just used for games, but also to check composed positions for correctness (that's the main usage for me at least). And a composed position can have more than 20 pieces of one side.

That certainly seems arbitrary, but older programs used arrays to represent the board and needed "piece lists" to speed up finding pieces of one side. One usually has to pick a maximum size for those lists, and 20 is the obvious candidate. In bitboard programs, the condition can indeed be relaxed, although it is also useful to detect bugs (since this is not supposed to happen during a game).

http://chessprogramming.wikispaces.com/Piece-Lists
(I'm afraid the URL will become invalid soon)

[Rein Halbersma]

Curiously Rein himself told us he "made a proof game of a position where a white king captures 19 black men: viewtopic.php?f=65&t=276&p=122166#p122166"
As a consequence I do not know if Rein is only interested by theoritical (non legal) positions or is also interested by the maximum moves we can reach for a legal position.

Sometimes I answer questions on StackOverflow. There are many sister sites for specific topics, one of them is Board Games. Sometimes people post checkers questions there. I answered the following two

https://boardgames.stackexchange.com/q/20378
https://boardgames.stackexchange.com/q/18949

The 40 kings solution I found fascinating, and so when somebody asked whether the 19-piece jump could happen in a game, I decided to try and construct one. It turned out to be very easy, I think it took me about 5 minutes to come up with one, except for the end sequence, getting the tempo just right. But that only took changing a single 2-piece sacrifice into 2 single-piece sacrifices.

Fabien is right: for a computer constructing proof games seems quite hard. In my program, I do check for illegal position in the constructor (see: viewtopic.php?t=7693) but only for immediate conflicts (overlapping squares or men on the promotion line). The indirect conflicts due to pending captures for both sides which never could have arisen is also possible to detect I think, but non-trivial. But going back to the initial position is much harder to automate.

So I have no general interest in doing that, apart from a few entertaining one like the 40 kings or 19 piece positions posted on StackOverflow.

EDIT: I also have a general interest in creating "reachability databases" for smaller board sizes (6x6, see the topic that Jan-Jaap is busy with right now). Such information can give you some information about the tree shape for forward searches.

[Rein Halbersma]

By contrast, Rein describes very precisely his idea:

The math is pretty easy: a capture victim can only sit in the inner 8x8 board, so 32 squares. You can capture at most 19 men, so you need all binom(32, i) for i = 1 through 19, which is 4 billion positions. Then you put up to 3 or 4 kings on the edges (18 squares), so binom(18, i) for i = 1 through 4, which is 4K positions, so 1.6 10^13, pretty big but comparable to generating 8 pc dbs. If you just fix the number of men to 10 and kings to 3, it's only 52 billion positions.

That's much better and very easy to do (< 1 hour) so I did it, except that I used random search. There's nothing more to it: I have little interest in the question itself (especially not for BT draughts where those numbers will always be tiny) nor studying position reachability. That being said, the latter could be used to compress endgame tables further, assuming that's not already standard.

Note that the 19 pieces located on the inner 32 squares is precise, but the "3-4 kings on the outer 18 squares" was only meant as a suggestion to reduce the search space to something manageable. Maybe placing kings in the inner 32 squares is more likely to achieve the record, I don't know.

[Fabien Letouzey]

Fabien is right: for a computer constructing proof games seems quite hard. In my program, I do check for illegal position in the constructor (see: viewtopic.php?t=7693) but only for immediate conflicts (overlapping squares or men on the promotion line). The indirect conflicts due to pending captures for both sides which never could have arisen is also possible to detect I think, but non-trivial. But going back to the initial position is much harder to automate.

So I have no general interest in doing that, apart from a few entertaining one like the 40 kings or 19 piece positions posted on StackOverflow.

I have no interest either, but will give an external pointer in case someone else wants to tackle the problem. Someone suggested using A* to solve the reachability problem. For whatever reason, I cannot see the original question(s), so I could be misinterpreting it.

---
You can use A* search to find a sequence of moves that transforms one position into another. The first problem reduces to transforming an initial position into a given one. Time complexity depends on the heuristic.
---
https://www.reddit.com/r/chess/comments ... _in_chess/

I think that, more generally, the idea is to realise that we switch "back" to one-player games (puzzles), since both players are now cooperating. Hopefully, programmers did not skip this interesting topic that is surprisingly similar to our more familiar adversarial domain; and I know you didn't.