Conditional FEN generator?

[Guenther]

I could send you a Windows executable for testing if you PM me your mail address. The C++ source code (compiled with old VS2010 express) has exactly 200 lines for which I needed exactly 2 hours :-) If anyone is interested I can also post the source code here.

It seems to work perfect. You even added the castling rights check which
I forgot to mention.

It is a wonderful toy for new handicap and different opening positions.

BTW I don't remember why a simple pipe out put via '> file' doesn't work
in a batch file, but in cmd?

Thanks a lot,
Guenther

[Ajedrecista]

Hello again:

Thank you for sharing your code!

I did some math on the amount of possibilities. If there are {Q, R, B, N, P; q, r, b, n, p} pieces missing in {white; black} sides, then:

Code: Select all

{Q, R, B, N, P; q, r, b, n, p} pieces missing in {white; black} sides:

comb(a, b) = (a!)/{(b!)·[(a - b)!]}

Possible combinations ({Q, R, B, N, P; q, r, b, n, p}) =
= [comb(Q_max., Q)]*[comb(R_max., R)]*[comb(B_max., B)]*[comb(N_max., N)]*[comb(P_max., P)]*
 *[comb(q_max., q)]*[comb(r_max., r)]*[comb(b_max., b)]*[comb(n_max., n)]*[comb(p_max., p)] =
= [comb(1, Q)]*[comb(2, R)]*[comb(2, B)]*[comb(2, N)]*[comb(8, P)]*
 *[comb(1, q)]*[comb(2, r)]*[comb(2, b)]*[comb(2, n)]*[comb(8, p)]

I do not take into account mirrors here but I scan all over the possibilities, so the mirror subset of missing pieces will appear sooner or later. Also, mirroring may lead to identical FENs. For example:

Code: Select all

"Q R B N 4P q r b n 4p"
Imagine that all the queenside is empty in one of the iterations.
When missing pieces swap sides, you will find the queenside empty again, hence duplicating FENs.

The easiest example I can find is with "P p" removed:
You remove a2 and b7 --> no problem; mirroring: a7 and b2 missing.
You remove a2 and a7 --> problem; mirroring: a7 and a2 missing --> duplicated FENs.

Unless I misunderstood something, the maximum of 627200 includes some duplicates.

My purpose of scan all over the possibilities is only counting them. Here is a not nice Fortran 95 code:

Code: Select all

program aa
implicit none
integer::i,wq,wr,wb,wn,wp,bq,br,bb,bn,bp
integer(4)::n(0:30)
real(3)::posw(0:1,0:2,0:2,0:2,0:8)
real(3)::posb(0:1,0:2,0:2,0:2,0:8)
real(3)::f(0:8),sumpos(0:30)
!i=Missing pieces.
f(0)=1d0
do wp=1,8
  f(wp)=wp*f(wp-1)
end do
n=0;sumpos=0d0
do wq=0,1
  do wr=0,2
    do wb=0,2
      do wn=0,2
        do wp=0,8
          posw(wq,wr,wb,wn,wp)=&
          &(f(1)/(f(wq)*f(1-wq)))*&
          &(f(2)/(f(wr)*f(2-wr)))*&
          &(f(2)/(f(wb)*f(2-wb)))*&
          &(f(2)/(f(wn)*f(2-wn)))*&
          &(f(8)/(f(wp)*f(8-wp)))
          do bq=0,1
            do br=0,2
              do bb=0,2
                do bn=0,2
                  do bp=0,8
                    posb(bq,br,bb,bn,bp)=&
                    &(f(1)/(f(bq)*f(1-bq)))*&
                    &(f(2)/(f(br)*f(2-br)))*&
                    &(f(2)/(f(bb)*f(2-bb)))*&
                    &(f(2)/(f(bn)*f(2-bn)))*&
                    &(f(8)/(f(bp)*f(8-bp)))
                    n(wq+wr+wb+wn+wp+bq+br+bb+bn+bp)=n(wq+wr+wb+wn+wp+bq+br+bb+bn+bp)+1
                    sumpos(wq+wr+wb+wn+wp+bq+br+bb+bn+bp)=&
                    &sumpos(wq+wr+wb+wn+wp+bq+br+bb+bn+bp)+posw(wq,wr,wb,wn,wp)*posb(bq,br,bb,bn,bp)
                  end do
                end do
              end do
            end do
          end do
        end do
      end do
    end do
  end do
end do
open(unit=10,file='a.txt',status='unknown',action='write')
do i=30,0,-1
  write(10,'(I2,A,I16)') 32-i,'     ',n(i)
end do
write(10,*)
write(10,'(A,I16)') 'SUM:   ',sum(n)
close(10)
open(unit=11,file='b.txt',status='unknown',action='write')
do i=30,0,-1
  write(11,'(I2,A,F32.0)') 32-i,'     ',sumpos(i)
end do
write(11,*)
write(11,'(A,F32.0)') 'SUM:   ',sum(sumpos)
close(11)
end program

I copy it here just in case there is something wrong. Well, after some editing of the output files:

Code: Select all

OTB = on the board pieces
Possible subsets (OTB = 32) =  1 (the standard starting position)
Possible subsets (OTB = 32) = 10 (1 missing piece:
                                 1Q or 1R or 1B or 1N or 1P or
                                 1q or 1r or 1b or 1n or 1p)
And so on

OTB         Possible subsets
 2                    1
 3                   10
 4                   53
 5                  194
 6                  546
 7                 1254
 8                 2445
 9                 4170
10                 6378
11                 8940
12                11697
13                14484
14                17109
15                19320
16                20820
17                21354
18                20820
19                19320
20                17109
21                14484
22                11697
23                 8940
24                 6378
25                 4170
26                 2445
27                 1254
28                  546
29                  194
30                   53
31                   10
32                    1

SUM:             236196

Code: Select all

OTB = on the board pieces
Possible combinations (OTB = 32) =  1 (the standard starting position)
Possible combinations (OTB = 31) = 30 (1 missing piece in one of the following squares:
                                      a1, b1, c1, d1, f1, g1, h1,
                                      a2, b2, c2, d2, e2, f2, g2, h2,
                                      a7, b7, c7, d7, e7, f7, g7, h7,
                                      a8, b8, c8, d8, f8, g8, h8)
And so on

OTB                    Possible combinations
 2                                   1
 3                                  30
 4                                 435
 5                                4060
 6                               27405
 7                              142506
 8                              593775
 9                             2035800
10                             5852925
11                            14307150
12                            30045015
13                            54627300
14                            86493225
15                           119759850
16                           145422675
17                           155117520
18                           145422675
19                           119759850
20                            86493225
21                            54627300
22                            30045015
23                            14307150
24                             5852925
25                             2035800
26                              593775
27                              142506
28                               27405
29                                4060
30                                 435
31                                  30
32                                   1

SUM:                        1073741824

I hope no typos. I think I got rid of duplicates just looking at OTB = {2, 32}. Please correct me if there is anything wrong.

All in all, 1073741824 = 2^(30). Also: 236196 = (2²)·[3^(10)]... nice finds!

Regards from Spain.

Ajedrecista.

[Guenther]

Hello again:

Thank you for sharing your code!

I did some math on the amount of possibilities. If there are {Q, R, B, N, P; q, r, b, n, p} pieces missing in {white; black} sides, then:

Code: Select all

{Q, R, B, N, P; q, r, b, n, p} pieces missing in {white; black} sides:

comb(a, b) = (a!)/{(b!)·[(a - b)!]}

Possible combinations ({Q, R, B, N, P; q, r, b, n, p}) =
= [comb(Q_max., Q)]*[comb(R_max., R)]*[comb(B_max., B)]*[comb(N_max., N)]*[comb(P_max., P)]*
 *[comb(q_max., q)]*[comb(r_max., r)]*[comb(b_max., b)]*[comb(n_max., n)]*[comb(p_max., p)] =
= [comb(1, Q)]*[comb(2, R)]*[comb(2, B)]*[comb(2, N)]*[comb(8, P)]*
 *[comb(1, q)]*[comb(2, r)]*[comb(2, b)]*[comb(2, n)]*[comb(8, p)]

I do not take into account mirrors here but I scan all over the possibilities, so the mirror subset of missing pieces will appear sooner or later. Also, mirroring may lead to identical FENs. For example:

Code: Select all

"Q R B N 4P q r b n 4p"
Imagine that all the queenside is empty in one of the iterations.
When missing pieces swap sides, you will find the queenside empty again, hence duplicating FENs.

The easiest example I can find is with "P p" removed:
You remove a2 and b7 --> no problem; mirroring: a7 and b2 missing.
You remove a2 and a7 --> problem; mirroring: a7 and a2 missing --> duplicated FENs.

...

Unless I misunderstood something, the maximum of 627200 includes some duplicates.

Thanks for all the math Jesus!
Is there a not too complicated way to count the possible duplicates?
If I understand it right they appear when the same piece type with the same amount is removed for both sides and the total amount removed for both sides must be identical too?

Guenther

[Sven]

Is there a not too complicated way to count the possible duplicates?
If I understand it right they appear when the same piece type with the same amount is removed for both sides and the total amount removed for both sides must be identical too?

I think that duplicates can only occur when mirroring is enabled and the whole specification of missing pieces is identical for white and black, regarding both the types and the number of missing pieces. So mirroring "Q q" produces duplicates (here only one) as well as "2R B 2r b" but not "R 2N P r n 2P".

To remove duplicates you could use the "sort -u" Unix command, or you could ask the programmer of the FEN generator tool to add an option "-u" that ensures to only print unique FENs

[Guenther]

Is there a not too complicated way to count the possible duplicates?
If I understand it right they appear when the same piece type with the same amount is removed for both sides and the total amount removed for both sides must be identical too?

I think that duplicates can only occur when mirroring is enabled and the whole specification of missing pieces is identical for white and black, regarding both the types and the number of missing pieces. So mirroring "Q q" produces duplicates (here only one) as well as "2R B 2r b" but not "R 2N P r n 2P".

To remove duplicates you could use the "sort -u" Unix command, or you could ask the programmer of the FEN generator tool to add an option "-u" that ensures to only print unique FENs ;-)

That would be nice. Otherwise I could use the WIN Powershell as it seems to have that Unix style sort integrated too.
But if I am not mistaken it seems mirroring in the given cases with exact same material for both sides just gives a duplicate for each FEN?
Thus, just don't mirror in that cases ;-)

BTW I noticed now a little glitch.
When searching for a certain position which already was played out from my fen file, I did not find it, but I knew it must be there because it was played.
Finally I found out that some FENs are not 100% to the standard, but most programs do accept them e.g. Polyglot/Winboard/Shredder/Chessbase, but change them internally!
Scid vs. PC does not accept them though.

Examples:
FenGen created

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PP1PPPP1/R1BQKBN w Qkq - 0 1

internally changed too

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PPPPPP2/RNBQKBN1 w Qkq - 0 1

FenGen created

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PPPPPP2/RNBQKB w Qkq - 0 1

internally changed too

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PPPPPP2/RNBQKB2 w Qkq - 0 1

It seems the placeholder for the empty end files (and only for White)is omitted.

Guenther

[Guenther]

I corrected a copy/paste error in one fen.

Examples:
FenGen created

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PP1PPPP1/R1BQKBN w Qkq - 0 1

internally changed too

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PP1PPPP1/RNBQKBN1 w Qkq - 0 1

FenGen created

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PPPPPP2/RNBQKB w Qkq - 0 1

internally changed too

Code: Select all

rnb1kbnr/pppppppp/8/8/8/8/PPPPPP2/RNBQKB2 w Qkq - 0 1

It seems the placeholder for the empty end files (and only for White) is omitted.

Guenther

[Sven]

It seems the placeholder for the empty end files (and only for White) is omitted.

I'll take a look at that issue during the next days.