World Draughts Forum

It is currently Thu Jul 19, 2018 00:23

All times are UTC+02:00




Post new topic  Reply to topic  [ 38 posts ]  Go to page Previous 1 2 3
Author Message
PostPosted: Sun Jul 01, 2018 18:22 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 272
Real name: Fabien Letouzey
TAILLE wrote:
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 :P :

...
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:

Quote:
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.


Top
   
PostPosted: Sun Jul 01, 2018 19:01 
Offline

Joined: Thu Apr 26, 2007 18:51
Posts: 904
Location: FRANCE
Fabien Letouzey wrote:
TAILLE wrote:
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 :P :

...
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:

Quote:
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
Image
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
Image
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.

_________________
Gérard


Top
   
PostPosted: Mon Jul 02, 2018 08:57 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 272
Real name: Fabien Letouzey
Hi Gérard,

TAILLE wrote:
Should my quesion have concerned non legal position I would have begun by showing the following quite simple position
Image
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).

Quote:
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.


Top
   
PostPosted: Mon Jul 02, 2018 09:45 
Offline
User avatar

Joined: Tue Aug 22, 2006 15:38
Posts: 1400
Real name: Joost de Heer
Fabien Letouzey wrote:
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.

_________________
Lasst die Maschinen verhungern, Ihr Narren...
Lasst sie verrecken!
Schlagt sie tot -- die Maschinen!


Top
   
PostPosted: Mon Jul 02, 2018 10:09 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 272
Real name: Fabien Letouzey
ildjarn wrote:
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)


Top
   
PostPosted: Tue Jul 03, 2018 23:37 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1598
TAILLE wrote:
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.


Last edited by Rein Halbersma on Tue Jul 03, 2018 23:52, edited 1 time in total.

Top
   
PostPosted: Tue Jul 03, 2018 23:40 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1598
Fabien Letouzey wrote:
By contrast, Rein describes very precisely his idea:

Quote:
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.


Top
   
PostPosted: Wed Jul 04, 2018 07:43 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 272
Real name: Fabien Letouzey
Rein Halbersma wrote:
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.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 38 posts ]  Go to page Previous 1 2 3

All times are UTC+02:00


Who is online

Users browsing this forum: No registered users and 6 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited