KQ vs. K code review

Discussion of chess software programming and technical issues.

Moderator: Ras

Koistinen
Posts: 29
Joined: Sun May 23, 2021 10:05 pm
Location: Stockholm, Sweden
Full name: Urban Koistinen

KQ vs. K code review

Post by Koistinen »

I am trying to write a simple KQ vs. K tablebase generator in Nim.
So far it is computing Stale Mates, Check Mates and Mate in 1 correctly but I think there is something wrong as there are no white wins in 10.
If it is not this code, it might be my chess library: https://github.com/Koistinen/chess/blob/main/chess.nim which is not well tested.

Code: Select all

# Copyright 2023 Urban Koistinen, Affero License
import chess
import streams

const illegal = -1
const checkMate = 0
const unknown = 101
const draw =102

var dtc: array[2*64*64*64, int8]

proc genIndex(p: Pos): int =
  var ♔sq, ♚sq, ♕sq: 0..63
  for sq in 0..63:
    case p.bd[sq]
    of ♔:
      ♔sq = sq
    of ♚:
      ♚sq = sq
    of ♕:
      ♕sq = sq
    else:
      discard
  return ♕sq+64*(♚sq+64*(♔sq+64*p.side))

for i in 0..<(2*64*64*64):
  dtc[i] = unknown
  
for ply in -1..24:
  echo "Ply: ", ply
  for side in white..black:
    echo "Side: ", side
    var c = 0
    for ♔sq in 0..63:
      for ♚sq in 0..63:
        for ♕sq in 0..63:
          if ♔sq != ♚sq and ♔sq != ♕sq and ♚sq != ♕sq:
            var p: Pos
            p.addPiece(♔, ♔sq)
            p.addPiece(♚, ♚sq)
            p.addPiece(♕, ♕sq)
            p.side = side
            var index = p.genIndex
            if unknown == dtc[index]:
              case ply
              of -1: # illegal?
                dtc[index] = if p.kingCapture: illegal
                             else: unknown
              of 0: # check mate?
                if black == side:
                  if p.isCheckmate:
                    dtc[index] = checkMate
                  else:
                    if p.isStalemate:
                      dtc[index] = draw
                      inc c
              else:
                if white == side:
                  for mv in p.genLegalMoves:
                    var p2 = p
                    p2.makeMove(mv)
                    if ply > dtc[p2.genIndex]:
                      if dtc[index] != ply.int8:
                        inc c
                      dtc[index] = ply.int8
                else:
                  var best = checkMate
                  for mv in p.genLegalMoves:
                    var p2 = p
                    p2.makeMove mv
                    best = max(best, dtc[p2.genIndex])
                  if ply > best:
                    inc c
                    dtc[index] = ply.int8
    echo "count: ", c
var f = newFileStream("KQK.bigbin", fmWrite)
if not f.isNil:
  f.write dtc
else:
  echo "Error creating file."
f.flush
# ♚, ♛, ♜, ♝, ♞, ♟, □, ♙, ♘, ♗, ♖, ♕ , ♔
Anyone got ideas on where my mistakes are?
mig2004
Posts: 256
Joined: Wed Oct 02, 2013 12:36 am

Re: KQ vs. K code review

Post by mig2004 »

Chat GPT generated this response to your problem:

" The code you've provided seems mostly reasonable for generating a KQ vs. K tablebase, but there are a few areas that might be causing the issue you're facing. Let's go through some potential problems and suggestions:

Index Calculation: The genIndex procedure is used to calculate the index for the tablebase array. Make sure that your genIndex function is generating unique indices for different board positions. A wrong index calculation can lead to unexpected behavior.

Conditionals and Loops: The nested loops and conditionals in your code are quite complex, which makes it harder to debug. Try breaking down your code into smaller, more manageable functions to isolate potential issues.

Logic for Plys: The code seems to handle different plys and sides well, but make sure you have a clear understanding of how the plys are being handled. Since you're dealing with KQ vs. K positions, it's not expected that the plys would go up to 24. Make sure your loops and logic match your intentions.

Best Move for Black: In the block that handles black's moves, you're using max(best, dtc[p2.genIndex]) to find the best move for black. However, this approach might not be accurate. For black's moves, you should be looking for the lowest value of dtc[p2.genIndex] since black is trying to minimize the value of the position.

Check for White Wins: It seems that you're checking for white wins by checking if ply > best and then updating dtc[index] accordingly. However, the condition for a white win should be ply >= best, not ply > best, since white wants to minimize the ply value to win sooner.

Output and Debugging: You can add more detailed output statements to understand the flow of your program better and identify where the code might be failing. This can help you pinpoint specific positions that are causing the unexpected behavior.

Chess Library: Since your chess library is not well-tested, it could potentially introduce unexpected behavior. Make sure your chess library is functioning correctly before using it in the tablebase generator.

Data Types and Ranges: Double-check your data types and ranges. For example, ensure that ply.int8 is an appropriate representation for the ply values you're dealing with.

Legal Moves Generation: Double-check your move generation logic. Make sure you're generating all legal moves correctly, considering all possible scenarios.

Memory Usage: Generating a complete KQ vs. K tablebase can require a significant amount of memory. Make sure your system has enough memory available for this task.

Remember, debugging complex chess-related code can be challenging. Consider implementing additional debugging and logging mechanisms to help you understand what's going on at each step of the process."
syzygy
Posts: 5693
Joined: Tue Feb 28, 2012 11:56 pm

Re: KQ vs. K code review

Post by syzygy »

Code: Select all

                if white == side:
                  for mv in p.genLegalMoves:
                    var p2 = p
                    p2.makeMove(mv)
                    if ply > dtc[p2.genIndex]:
                      if dtc[index] != ply.int8:
                        inc c
                      dtc[index] = ply.int8
Here the current position is unknown, white is to move, and you find a shortest win if any legal white move leads to a position that is a known loss for black.
So the test "ply > dtc[p2.genIndex]" seems a bit misleading, although probably not giving wrong results. What you want to test is "dtc[p2.genIndex] < unknown", which is independent of ply.

I say misleading because at first sight it looks as if you are trying to find longer and longer wins for white instead of the shortest.

Also, I would break out of the loop after finding a win if your language allows that, so you don´t have to check dtc[index].

Code: Select all

                else:
                  var best = checkMate
                  for mv in p.genLegalMoves:
                    var p2 = p
                    p2.makeMove mv
                    best = max(best, dtc[p2.genIndex])
                  if ply > best:
                    inc c
                    dtc[index] = ply.int8
Here black is to move and the current position is unknown (and known to be not mate or stalemate, so black has legal moves).
I would probably again write "if best < unknown" instead of "ply > best", meaning that all of black's legal moves lead to a known win for white. But it seems what you have should work too.

So I don't immediately see a bug.
Koistinen
Posts: 29
Joined: Sun May 23, 2021 10:05 pm
Location: Stockholm, Sweden
Full name: Urban Koistinen

Re: KQ vs. K code review

Post by Koistinen »

I say misleading because at first sight it looks as if you are trying to find longer and longer wins for white instead of the shortest.
I am finding longer and longer wins, starting with check mate and then increasing length one half move at a time.
Also, I would break out of the loop after finding a win if your language allows that, so you don´t have to check dtc[index].
In this code I very much prioritize readability over speed. I intend to use it as scaffoldinging when writing more general code and then that when writing more performant code in an iterative manner.
So I don't immediately see a bug.
Thanks, I guess this means the library is the most likely place to have mistakes. It is messier.
I'll go test/rewrite it next.
Koistinen
Posts: 29
Joined: Sun May 23, 2021 10:05 pm
Location: Stockholm, Sweden
Full name: Urban Koistinen

Re: KQ vs. K code review

Post by Koistinen »

I found a bug, something is missing is a hint if you want to find it by yourself.
Now I get these mate in 10 positions:

Code: Select all

8/8/8/5k2/8/8/1Q6/K7 w - - 0 0
8/8/4k3/8/8/8/1Q6/K7 w - - 0 0
8/8/8/2k5/8/8/6Q1/7K w - - 0 0
8/8/3k4/8/8/8/6Q1/7K w - - 0 0
K7/1Q6/8/8/8/4k3/8/8 w - - 0 0
K7/1Q6/8/8/5k2/8/8/8 w - - 0 0
7K/6Q1/8/8/8/3k4/8/8 w - - 0 0
7K/6Q1/8/8/2k5/8/8/8 w - - 0 0
All mirrorings matching the Syzgy result at https://syzygy-tables.info/?fen=8/8/8/8 ... _b_-_-_0_1
In conclusion: looks like it wasn't the library.
syzygy
Posts: 5693
Joined: Tue Feb 28, 2012 11:56 pm

Re: KQ vs. K code review

Post by syzygy »

Koistinen wrote: Mon Aug 14, 2023 2:04 pm I found a bug, something is missing is a hint if you want to find it by yourself.
Why would I?
Koistinen
Posts: 29
Joined: Sun May 23, 2021 10:05 pm
Location: Stockholm, Sweden
Full name: Urban Koistinen

Re: KQ vs. K code review

Post by Koistinen »

syzygy wrote: Mon Aug 14, 2023 11:12 pm
Koistinen wrote: Mon Aug 14, 2023 2:04 pm I found a bug, something is missing is a hint if you want to find it by yourself.
Why would I?
It is for those who enjoy puzzles.
syzygy
Posts: 5693
Joined: Tue Feb 28, 2012 11:56 pm

Re: KQ vs. K code review

Post by syzygy »

Koistinen wrote: Tue Aug 15, 2023 2:36 pm
syzygy wrote: Mon Aug 14, 2023 11:12 pm
Koistinen wrote: Mon Aug 14, 2023 2:04 pm I found a bug, something is missing is a hint if you want to find it by yourself.
Why would I?
It is for those who enjoy puzzles.
I do wonder whether the bug is in the part you claimed to be correct or whether it is in the part that I suggested could be cleared up, but if you can't be bothered to just explain what was wrong, then I can't be bothered either.
Koistinen
Posts: 29
Joined: Sun May 23, 2021 10:05 pm
Location: Stockholm, Sweden
Full name: Urban Koistinen

Re: KQ vs. K code review

Post by Koistinen »

syzygy wrote: Tue Aug 15, 2023 6:36 pm I do wonder whether the bug is in the part you claimed to be correct or whether it is in the part that I suggested could be cleared up, but if you can't be bothered to just explain what was wrong, then I can't be bothered either.
If you want the spoiler, just read the commit message from Aug 14, 2023 at: https://github.com/Koistinen/chess
The mate in 1 and what it depends on appears to have worked correctly despite the bug.
It has nothing to do with what you wrote.