More WBEC output examination... {LGPGNVER}

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 26 June 2004 00:50:46:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dann Corbit at 26 June 2004 00:32:43:

White(1): setboard QB1kB2R/3N2Q1/3KQ3/R6Q/1Q6/3Q4/5Q2/Q1Q4R w - -
White(1): perft 1
total moves=186 time=0.00


my ftp site {remove http:// unless you like error messages}

[Dieter Bürßner]

Geschrieben von:/Posted by: Dieter Bürßner at 26 June 2004 00:51:08:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dann Corbit at 26 June 2004 00:47:25:

This one has 170 possible:
White(1): setboard QB1k4/6Q1/3KQ3/7Q/1Q6/3Q4/5Q2/2Q5 w - -
White(1): perft 1
total moves=170 time=0.00
Construction of a position with a huge number of moves seems quite difficult.

2 positions with 218 legal moves:
Dickins, 1986:
3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1
Nenand Petrovic, 1946
R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1
As far as I know, these are the record positions for the number of legal moves (at least the Chest documantation says that there is no known position yet, with more legal moves).
Regards,
Dieter

[Uri Blass]

Geschrieben von:/Posted by: Uri Blass at 26 June 2004 01:31:08:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dieter Bürßner at 26 June 2004 00:37:29:

323 moves will be enough for legal chess positions. 9 Q, 2 R, 2 B, 2 N, 1 K
9*27+2*14+2*13+2*8+10 (including 2 castling moves).

castling move are moves of the king and if the king can castle then by definition it have not more than 7 moves so you can replace 10 by 8.
If you are intersted in the maximal number of legal moves of 9 queens then you can try to solve by a program the maximal number of n queens for smaller n by trying all possibilities.

Yes, thanks for pointing it out. Additionally, at least one of those two rooks could not have more then 10 moves.
I thought the same. There are "only" 64!/(55!*9!) = 27,540,584,512 different positions with 9 queens. A program should be easily able to test 1e6 positions per second -> less than 8 hours (probably much less). A prove would need a bit more. Perhaps one of those queens happens to have less than 8 moves, and a 3rd knight would be better (but I doubt it).
This actually would be a nice programming excersize. One should be able to program it from scratch in a few hours.
Regards,
Dieter

I think that this problem can be solved by brute force.
You do not need to search all cases and there are cases when even after 8 queens you already know that you cannot be even close to the maximal number.
Imagine queens at a1,b1,c1.d1,e1,f1,g1,h1
Every queen see exactly 14 squares so you have 14*8=112 squares
112+27+14*2+13*2+8*2+8=215

[Dan Honeycutt]

Geschrieben von:/Posted by: Dan Honeycutt at 26 June 2004 03:31:06:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Uri Blass at 26 June 2004 01:31:08:

323 moves will be enough for legal chess positions. 9 Q, 2 R, 2 B, 2 N, 1 K
9*27+2*14+2*13+2*8+10 (including 2 castling moves).

castling move are moves of the king and if the king can castle then by definition it have not more than 7 moves so you can replace 10 by 8.
If you are intersted in the maximal number of legal moves of 9 queens then you can try to solve by a program the maximal number of n queens for smaller n by trying all possibilities.

Yes, thanks for pointing it out. Additionally, at least one of those two rooks could not have more then 10 moves.
I thought the same. There are "only" 64!/(55!*9!) = 27,540,584,512 different positions with 9 queens. A program should be easily able to test 1e6 positions per second -> less than 8 hours (probably much less). A prove would need a bit more. Perhaps one of those queens happens to have less than 8 moves, and a 3rd knight would be better (but I doubt it).
This actually would be a nice programming excersize. One should be able to program it from scratch in a few hours.
Regards,
Dieter

I think that this problem can be solved by brute force.
You do not need to search all cases and there are cases when even after 8 queens you already know that you cannot be even close to the maximal number.
Imagine queens at a1,b1,c1.d1,e1,f1,g1,h1
Every queen see exactly 14 squares so you have 14*8=112 squares
112+27+14*2+13*2+8*2+8=215You can even calculate 112+26+13*2+12*2+7*2+7=207Uri

I think a few less than 218. The queens can't control every square as the opponent king has to go somewhere. Best I could do tinkering was 198:
R6Q/5Q2/3Q4/1Q6/6Q1/4Q3/2Q4B/Q3QK1k w - -
Dan H.

[Uri Blass]

Geschrieben von:/Posted by: Uri Blass at 26 June 2004 04:35:08:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dan Honeycutt at 26 June 2004 03:31:06:

323 moves will be enough for legal chess positions. 9 Q, 2 R, 2 B, 2 N, 1 K
9*27+2*14+2*13+2*8+10 (including 2 castling moves).

castling move are moves of the king and if the king can castle then by definition it have not more than 7 moves so you can replace 10 by 8.
If you are intersted in the maximal number of legal moves of 9 queens then you can try to solve by a program the maximal number of n queens for smaller n by trying all possibilities.

Yes, thanks for pointing it out. Additionally, at least one of those two rooks could not have more then 10 moves.
I thought the same. There are "only" 64!/(55!*9!) = 27,540,584,512 different positions with 9 queens. A program should be easily able to test 1e6 positions per second -> less than 8 hours (probably much less). A prove would need a bit more. Perhaps one of those queens happens to have less than 8 moves, and a 3rd knight would be better (but I doubt it).
This actually would be a nice programming excersize. One should be able to program it from scratch in a few hours.
Regards,
Dieter

I think that this problem can be solved by brute force.
You do not need to search all cases and there are cases when even after 8 queens you already know that you cannot be even close to the maximal number.
Imagine queens at a1,b1,c1.d1,e1,f1,g1,h1
Every queen see exactly 14 squares so you have 14*8=112 squares
112+27+14*2+13*2+8*2+8=215>You can even calculate 112+26+13*2+12*2+7*2+7=207>Uri

I think a few less than 218. The queens can't control every square as the opponent king has to go somewhere. Best I could do tinkering was 198:
R6Q/5Q2/3Q4/1Q6/6Q1/4Q3/2Q4B/Q3QK1k w - -
Dan H.

218 was already done here
http://www.f11.parsimony.net/forum16635 ... /67849.htm
Uri

[Dan Honeycutt]

Geschrieben von:/Posted by: Dan Honeycutt at 26 June 2004 04:51:50:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Uri Blass at 26 June 2004 04:35:08:

218 was already done here
http://www.f11.parsimony.net/forum16635 ... /67849.htm
Uri

I saw that just after I posted. I presently allow 192 and I don't check the bounds. I guess I better raise that before my program crashes and brings down the internet
Dan H.

[Dann Corbit]

Geschrieben von:/Posted by: Dann Corbit at 26 June 2004 05:21:55:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dan Honeycutt at 26 June 2004 04:51:50:

218 was already done here
http://www.f11.parsimony.net/forum16635 ... /67849.htm
Uri

I saw that just after I posted. I presently allow 192 and I don't check the bounds. I guess I better raise that before my program crashes and brings down the internet

It seems to me that 256 would be a natural limit. In case there is some incredibly clever way to squeeze out a few more than 218 it won't matter. And 0-255 can be encoded in a single unsigned char. So it has nice properties.



my ftp site {remove http:// unless you like error messages}

[Dieter Bürßner]

Geschrieben von:/Posted by: Dieter Bürßner at 26 June 2004 06:13:45:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Uri Blass at 26 June 2004 01:31:08:

I think that this problem can be solved by brute force.
You do not need to search all cases and there are cases when even after 8 queens you already know that you cannot be even close to the maximal number.
Imagine queens at a1,b1,c1.d1,e1,f1,g1,h1
Every queen see exactly 14 squares so you have 14*8=112 squares
112+27+14*2+13*2+8*2+8=215You can even calculate 112+26+13*2+12*2+7*2+7=207

and from here on ...

[Ron Murawski]

Geschrieben von:/Posted by: Ron Murawski at 26 June 2004 07:23:15:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Dieter Bürßner at 25 June 2004 23:05:54:

I agree with your suggestions. One minor point later

"I will always get correct data from the user." is an intentional oversight. So (for instance) if you are expecting a FEN position, and you get one megabyte of binary data instead, your program does bad things. The reason I call it an intentional oversight is that it is not reasonable to assume perfect input.
There are also unintentional oversights. For instance, you may assume that no board position has more than 255 distinct moves possible. After all, the maximum ever discovered is 218. But the reasonable assumption may be incorrect. Perhaps there is some strange position with 257 moves possible.
5. Always set your compiler to the highest warning level possible.

323 moves will be enough for legal chess positions. 9 Q, 2 R, 2 B, 2 N, 1 K
9*27+2*14+2*13+2*8+10 (including 2 castling moves).
It is clear, that the actual maximum will be quite a bit lower, but I see no (easy) way, to calculate it.
I find it a PITA, with for example MSVC.

My code gets many such warnings. With -W4 too many, to make it useful. The serious warnings will be easily overseen. I don't think it would be nice, to clutter the source code with many pragmas to disable specific warnings.
I have seen other examples about warnings, which go away with a cast, that is really unneeded, and that may easily break the code, when the type of the var is changed, but one forgets to change the cast.
Such warnings may make you write worse code.

>G:\src\yace>cat m.c
>extern void foo(void)&#59;
>extern void bar(void)&#59;
>
>#define robust_macro() do { foo()&#59; bar()&#59; } while (0)
>#define fragile_macro() {foo()&#59; bar()&#59; }
>void dummy(int i)
>{
>  if (i<0)
>    robust_macro()&#59; /* won't work with fragile macro, but warning */
>  else
>    bar()&#59;
>  fragile_macro()&#59; /* No warning */
>}
>
>G:\src\yace>cl -W4 -c m.c
>Optimierender Microsoft (R) 32-Bit C/C++-Compiler, Version 12.00.8168, fuer x86
>Copyright (C) Microsoft Corp 1984-1998. Alle Rechte vorbehalten.
>m.c
>m.c(11) : warning C4127: Bedingter Ausdruck ist konstant
>(Conditional expression is constant)
>
Speaking of writing worse code...

do 
{ 
  foo()&#59; 
  bar()&#59; 
} while (0)&#59;

can be replaced by:

for (&#59;&#59;) // infinite loop
{
  foo()&#59;
  bar()&#59;
  break&#59;  // break out of loop the first time thru...
}

It's ugly, but generates no Microsoft level4 warnings. The code optimizer seems to do okay on this as well.
Ron

[Dieter Bürßner]

Geschrieben von:/Posted by: Dieter Bürßner at 27 June 2004 19:11:24:
Als Antwort auf:/In reply to: Re: More WBEC output examination... {LGPGNVER} geschrieben von:/posted by: Uri Blass at 26 June 2004 00:07:19:

I am aware, that this discussion drifted rather off topic. The moderators can warn me, or delete my post. I think, there won't be a lot more to post.

We need first table for maximal number of moves that n queens can goto.
1 queen 27 moves
2 queens 52 moves(d5 e3)
3 queens 77 moves(d5 e3 f6)
4 queens probably 100 moves(c4 e3 d6 f5)

Your numbers above get confirmed by my prog.
5 queens 123 moves
6 queens 144 moves
7 queens 163 moves
8 queens 182 moves
9 queens 201 moves
Hmmm - I hope my prog is correct. I am surprised that from 6 -> 7 -> 8 -> 9 each time 19 moves are added. Especially the last step.
I am wondering one thing. My prog generates all combinations of 9 Qs on 64 squares. They are generated in a sorted manner (say square of 2nd Q is > square of 1st queen, Sq(3rd) > sq(2nd), ...). Would it be sufficient to only look at 10 squares for the 1st Q, squares a1,b1,c1,d1,b2,c2,d2,c3,d3,d4, assuming a1=0, b1=1, ..., h8=63. Would one still hit all really different positions? (Normally such a position can be rotated/mirrored into 8 "different" positions, that are in principial the same, but my simple combination algorithm will look at all 8 positions).
Regards,
Dieter