How to resolve the algorithm Find Chess960 starting position identifier step by step in the BASIC programming language

Published on 12 May 2024 09:40 PM
#Basic

How to resolve the algorithm Find Chess960 starting position identifier step by step in the BASIC programming language

Table of Contents

Problem Statement

As described on the Chess960 page, Chess960 (a.k.a Fischer Random Chess, Chess9LX) is a variant of chess where the array of pieces behind the pawns is randomized at the start of the game to minimize the value of opening theory "book knowledge". That task is to generate legal starting positions, and some of the solutions accept a standard Starting Position Identifier number ("SP-ID"), and generate the corresponding position. This task is to go the other way: given a starting array of pieces (provided in any form that suits your implementation, whether string or list or array, of letters or Unicode chess symbols or enum values, etc.), derive its unique SP-ID. For example, given the starting array QNRBBNKR (or ♕♘♖♗♗♘♔♖ or ♛♞♜♝♝♞♚♜), which we assume is given as seen from White's side of the board from left to right, your (sub)program should return 105; given the starting lineup of standard chess, it should return 518. You may assume the input is a valid Chess960 position; detecting invalid input (including illegal characters or starting arrays with the bishops on the same color square or the king not between the two rooks) is optional. The derivation is the inverse of the algorithm given at Wikipedia, and goes like this (we'll use the standard chess setup as an example).

  1. Ignoring the Queen and Bishops, find the positions of the Knights within the remaining five spaces (in the standard array they're in the second and fourth positions), and then find the index number of that combination. There's a table at the above Wikipedia article, but it's just the possible positions sorted left to right and numbered 0 to 9: 0=NN---, 1=N-N--, 2=N--N-, 3=N---N, 4=-NN--, etc; our pair is combination number 5. Call this number N. N=5
  2. Still ignoring the Bishops, find the position of the Queen in the remaining 6 spaces; number them 0..5 from left to right and call the index of the Queen's position Q. In our example, Q=2.
  3. Finally, find the positions of the two bishops within their respective sets of four like-colored squares. It's important to note here that the board in chess is placed such that the leftmost position on the home row is on a dark square and the rightmost a light. So if we number the squares of each color 0..3 from left to right, the dark bishop in the standard position is on square 1 (D=1), and the light bishop is on square 2 (L=2).
  4. Then the position number is given by 4(4(6N + Q)+D)+L, which reduces to 96N + 16Q + 4D + L. In our example, that's 96×5 + 16×2 + 4×1 + 2 = 480 + 32 + 4 + 2 = 518. Note that an earlier iteration of this page contained an incorrect description of the algorithm which would give the same SP-ID for both of the following two positions.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Find Chess960 starting position identifier step by step in the BASIC programming language

Source code in the basic programming language

100 REM DERIVE SP-ID FROM CHESS960 POS
110 READ A$: IF A$="" THEN END
120 PRINT A$":";
130 GOSUB 170
140 PRINT SP
150 GOTO 110
160 DATA QNRBBNKR, RNBQKBNR, RQNBBKRN, RNQBBKRN,
170 IF LEN(A$)=8 THEN 190
180 PRINT "ARRAY MUST BE 8 PIECES.": SP=-1: RETURN
190 K=0:Q=0:B=0:N=0:R=0
200 FOR I=0 TO 7
210 : K(I)=0:Q(I)=0:B(I)=0:N(I)=0:R(I)=0
220 NEXT I
230 FOR I=1 TO 8
240 : P$=MID$(A$,I,1)
250 : IF P$="Q" THEN Q(Q)=I: Q=Q+1:  GOTO 310
260 : IF P$="K" THEN K(K)=I: K=K+1:  GOTO 310
270 : IF P$="B" THEN B(B)=I: B=B+1:  GOTO 310
280 : IF P$="N" THEN N(N)=I: N=N+1:  GOTO 310
290 : IF P$="R" THEN R(R)=I: R=R+1:  GOTO 310
300 : PRINT "ILLEGAL PIECE '"P$"'.": SP=-1: RETURN
310 NEXT I
320 IF K<>1 THEN PRINT "THERE MUST BE EXACTLY ONE KING.":    SP=-1: RETURN
330 IF Q<>1 THEN PRINT "THERE MUST BE EXACTLY ONE QUEEN.":   SP=-1: RETURN
340 IF B<>2 THEN PRINT "THERE MUST BE EXACTLY TWO BISHOPS.": SP=-1: RETURN
350 IF N<>2 THEN PRINT "THERE MUST BE EXACTLY TWO KNIGHTS.": SP=-1: RETURN
360 IF R<>2 THEN PRINT "THERE MUST BE EXACTLY TWO ROOKS.":   SP=-1: RETURN
370 IF (K(0) > R(0)) AND (K(0) < R(1)) THEN 390
380 PRINT "KING MUST BE BETWEEN THE ROOKS.": SP=-1: RETURN
390 IF (B(0) AND 1) <> (B(1) AND 1) THEN 410
400 PRINT "BISHOPS MUST BE ON OPPOSITE COLORS.": SP=-1: RETURN
410 FOR I=0 TO 1
420 : N=N(I)
430 : IF N(I)>Q(I) THEN N=N-1
440 : FOR J=0 TO 1
450 :  IF N(I)>B(J) THEN N=N-1
460 : NEXT J
470 : N(I)=N
480 NEXT I
490 N0=1: N1=2
500 FOR N=0 TO 9
510 : IF N0=N(0) AND N1=N(1) THEN 550
520 : N1=N1+1
530 : IF N1>5 THEN N0=N0+1: N1=N0+1
540 NEXT N
550 Q=Q(0)-1
560 FOR I=0 TO 1
570 : IF Q(0)>B(I) THEN Q=Q-1
580 NEXT I
590 FOR I=0 TO 1
600 : B=B(I)-1
610 : IF B AND 1 THEN L=INT(B/2)
620 : IF (B AND 1)=0 THEN D=B/2
630 NEXT I
640 SP = 96*N+16*Q+4*D+L
650 RETURN


Sub SP_ID(PosicPiezas As String)
    Dim As String pieza
    Dim As Integer pQ(), pK(), pB(), pN(), pR(), i, j
    Dim As Integer Q, K, B, N, R, L, D
    
    For i = 1 To 8
        pieza = Mid(PosicPiezas, i, 1)
        Select Case pieza
        Case "Q"
            Redim Preserve pQ(Q) : pQ(Q) = i: Q += 1
        Case "K"
            Redim Preserve pK(K) : pK(K) = i: K += 1
        Case "B"
            Redim Preserve pB(B) : pB(B) = i: B += 1
        Case "N"
            Redim Preserve pN(N) : pN(N) = i: N += 1
        Case "R"
            Redim Preserve pR(R) : pR(R) = i: R += 1
        Case Else 
            Print "ILLEGAL PIECE '"; pieza; "'.": Exit Sub
        End Select
    Next i
    
    If K <> 1 Then Print "THERE MUST BE EXACTLY ONE KING."
    If Q <> 1 Then Print "THERE MUST BE EXACTLY ONE QUEEN."
    If B <> 2 Then Print "THERE MUST BE EXACTLY TWO BISHOPS."
    If N <> 2 Then Print "THERE MUST BE EXACTLY TWO KNIGHTS."
    If R <> 2 Then Print "THERE MUST BE EXACTLY TWO ROOKS."
    If Not (pK(0) > pR(0)) And (pK(0) < pR(1)) Then Print "KING MUST BE BETWEEN THE ROOKS."
    If Not (pB(0) And 1) <> (pB(1) And 1) Then Print "BISHOPS MUST BE ON OPPOSITE COLORS."

    For i = 0 To 1
        N = pN(i)
        If pN(i) > pQ(i) Then N -= 1
        For j = 0 To 1
            If pN(i) > pB(j) Then N -= 1
        Next j
        pN(i) = N
    Next i

    Dim As Integer N0 = 1, N1 = 2
    For N = 0 To 9
        If N0 = pN(0) And N1 = pN(1) Then Exit For
        N1 += 1
        If N1 > 5 Then N0 += 1: N1 = N0 + 1
    Next N

    Q = pQ(0) - 1
    For i = 0 To 1
        If pQ(0) > pB(i) Then Q -= 1
    Next i
    For i = 0 To 1
        B = pB(i) - 1
        If B And 1 Then L = Int(B / 2)
        If (B And 1) = 0 Then D = B / 2
    Next i
    
    Print PosicPiezas; " has SP_ID of"; 96 * N + 16 * Q + 4 * D + L
End Sub

SP_ID("QNRBBNKR")
Print
SP_ID("RNBQKBNR")
Print
SP_ID("RQNBBKRN")
Print
SP_ID("RNQBBKRN")
Sleep

Cls
Print "Enter start array as seen by white."
120 Print
Print "Starting array";
Input Ar$
Print
If Len(Ar$) = 0 Then End
If Len(Ar$) = 8 Then 170
Print "Array must be 8 pieces.": GoTo 120

170 For I = 1 To 8
    P$ = Mid$(Ar$, I, 1)
    If P$ = "Q" Or P$ = "q" Then Q(Q) = I: Q = Q + 1: GoTo 250
    If P$ = "K" Or P$ = "k" Then K(K) = I: K = K + 1: GoTo 250
    If P$ = "B" Or P$ = "b" Then B(B) = I: B = B + 1: GoTo 250
    If P$ = "N" Or P$ = "n" Then N(N) = I: N = N + 1: GoTo 250
    If P$ = "R" Or P$ = "r" Then R(R) = I: R = R + 1: GoTo 250
    Print "Illegal piece '"; P$; "'.": GoTo 120
250 Next I

If K <> 1 Then Print "There must be exactly one King.": GoTo 120
If Q <> 1 Then Print "There must be exactly one Queen.": GoTo 120
If B <> 2 Then Print "There must be exactly two Bishops.": GoTo 120
If N <> 2 Then Print "There must be exactly two Knights.": GoTo 120
If R <> 2 Then Print "There must be exactly two Rooks.": GoTo 120
If (K(0) > R(0)) And (K(0) < R(1)) Then 330
Print "King must be between the Rooks.": GoTo 120

330 If (B(0) And 1) <> (B(1) And 1) Then 350
Print "Bishops must be on opposite colors.": GoTo 120

350 For I = 0 To 1
    N = N(I)
    If N(I) > Q(I) Then N = N - 1
    For J = 0 To 1
        If N(I) > B(J) Then N = N - 1
    Next J
    N(I) = N
Next I
N0 = 1: N1 = 2

For N = 0 To 9
    If N0 = N(0) And N1 = N(1) Then 490
    N1 = N1 + 1
    If N1 > 5 Then N0 = N0 + 1: N1 = N0 + 1
Next N
490 Q = Q(0) - 1

For I = 0 To 1
    If Q(0) > B(I) Then Q = Q - 1
Next I

For I = 0 To 1
    B = B(I) - 1
    If B And 1 Then L = Int(B / 2)
    If (B And 1) = 0 Then D = B / 2
Next I
Print "SP-ID ="; 96 * N + 16 * Q + 4 * D + L
End

You may also check:How to resolve the algorithm Execute SNUSP step by step in the D programming language
You may also check:How to resolve the algorithm Dragon curve step by step in the Go programming language
You may also check:How to resolve the algorithm Last Friday of each month step by step in the Fōrmulæ programming language
You may also check:How to resolve the algorithm Sutherland-Hodgman polygon clipping step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Memory allocation step by step in the R programming language