Kata

It depends what you mean by "properly randomly generated", but if you mean 100 or 1_000 or 10_000 tests generated with random spray, then this would not help much either? You will always have some potentially interesting positions which will not make into the tested pool. The best way would be to generate and test all possible board setups (modulo transformations), which would boil down to a couple of thousands of tests cases I believe? Is it possibl to test this task by running the solution on all "uniquely relevant" boards?

Why not a mix then? The 918 boards are, I think, too small a pool.

At any rate, here's my tester script, which relies on python-chess to do the heavy work.

import chess

CENTRE = 0x007e_7e7e_7e7e_7e00
BKING = chess.Piece.from_symbol("k")
WKING = chess.Piece.from_symbol("K")
WROOK = chess.Piece.from_symbol("R")

def base_positions():
    for bk in chess.scan_forward(CENTRE):
        rook_mask = chess.BB_FILE_ATTACKS[bk][0] | chess.BB_RANK_ATTACKS[bk][0] | chess.BB_SQUARES[bk]
        for wr in chess.scan_forward(chess.BB_ALL & ~rook_mask):
            choices = ~(chess.BB_KING_ATTACKS[bk] | chess.BB_SQUARES[bk] | chess.BB_SQUARES[wr])
            if chess.BB_KING_ATTACKS[bk] & chess.BB_SQUARES[wr]:
                choices &= chess.BB_KING_ATTACKS[wr]
            for wk in chess.scan_forward(chess.BB_ALL & choices):
                board = chess.Board(None)
                board.turn = chess.BLACK
                board.set_piece_map({bk: BKING, wk: WKING, wr: WROOK})
                yield board


print("Total boards:", sum(1 for _ in base_positions()))

The number of boards can be revised downwards a little, to 88060.

Dang I'd have to do some math but 88k is WAY more than I expected it to be. I am also not sure how your scipt handles discarding of equivalent, rotated/flipped boards, but I can't test it today, I will try tomorrow.

It doesn't discard rotation and mirror variants, no, but that's because I wanted to be able to compare the number to the expanded number of unique boards used in the random tests. There are 121 test positions, but when you rotate and mirror those, there are 13 boards where both kings are on the same diagonal. These boards produce 52 expanded boards instead of 104, so you get a total of 121 * 8 - (4 * 13) = 916 expanded boards.

When you just randomise the positions based on bitboard masks like above you don't need to expand afterwards anyway.

The following variant of the script does limit itself to just the 1/8th B2D2D4 wedge of the centre for the black king positions and limits the white king to the larger A1H1H8 triangle when the black king is located on the B2D4 diagonal:

import chess

BKING = chess.Piece.from_symbol("k")
WKING = chess.Piece.from_symbol("K")
WROOK = chess.Piece.from_symbol("R")

WEDGE_B2D2D4 = 0x0000_0000_080c_0e00
DIAG_B2D4 = 0x0000_0000_0804_0200
TRIANGLE_A1H1H8 = 0x80C0_E0F0_F8FC_FEFF

def base_positions():
    for bk in chess.scan_forward(WEDGE_B2D2D4):
        rook_mask = chess.BB_FILE_ATTACKS[bk][0] | chess.BB_RANK_ATTACKS[bk][0] | chess.BB_SQUARES[bk]
        for wr in chess.scan_forward(chess.BB_ALL & ~rook_mask):
            choices = ~(chess.BB_KING_ATTACKS[bk] | chess.BB_SQUARES[bk] | chess.BB_SQUARES[wr])
            if DIAG_B2D4 & chess.BB_SQUARES[bk]:
                choices &= TRIANGLE_A1H1H8
            if chess.BB_KING_ATTACKS[bk] & chess.BB_SQUARES[wr]:
                choices &= chess.BB_KING_ATTACKS[wr]
            for wk in chess.scan_forward(chess.BB_ALL & choices):
                board = chess.Board(None)
                board.turn = chess.BLACK
                board.set_piece_map({bk: BKING, wk: WKING, wr: WROOK})
                yield board

print("Total boards:", sum(1 for _ in base_positions()))

There are 11340 such boards, with 665 positions where both the kings lie on the A1H8 diagonal, so these expand to 88060 unique chess boards:

>>> sum(1 for b in base_positions() if not b.kings & ~0x8040_2010_0804_0201)
665

Here is a version that doesn't use the chess module and yields just the square names:

SQUARE_NAMES = [f"{file}{rank}" for file in "abcdefgh" for rank in range(1, 9)]
WEDGE_B2D2D4 = 0x0000_0000_080C_0E00
DIAG_B2D4 = 0x0000_0000_0804_0200
TRIANGLE_A1H1H8 = 0x80C0_E0F0_F8FC_FEFF
BB_ALL = 0xFFFFFFFFFFFFFFFF
BB_FILE_1 = 0x0101_0101_0101_0101
BB_RANK_A = 0xFF

def bb_scan(bb):
    # forward bitscan, https://www.chessprogramming.org/BitScan#Bitscan_forward,
    # as a Python iterator.
    while bb:
        lsb = bb & -bb
        yield lsb.bit_length() - 1
        bb ^= lsb

# simplified rook attack masks without blockers, combining rank and file masks
# and including the starting position.
# See https://www.chessprogramming.org/On_an_empty_Board#By_Calculation_3
ROOK_MOVES = [
    ((BB_RANK_A << (i & 0o70)) | (BB_FILE_1 << (i & 0o07))) for i in range(64)
]

# king attack masks, https://www.chessprogramming.org/King_Pattern#by_Calculation
KING_MOVES = [
    (
        (att := ((bb := 1 << i) << 1 & ~BB_FILE_1) | (bb >> 1 & ~(BB_FILE_1 << 7)))
        | ((bb | att) << 8)
        | (((bb | att) & BB_ALL) >> 8)
    )
    & BB_ALL
    for i in range(64)
]

def base_positions():
    for bk in bb_scan(WEDGE_B2D2D4):
        rook_mask = ROOK_MOVES[bk]
        for wr in bb_scan(BB_ALL & ~rook_mask):
            choices = ~(KING_MOVES[bk] | (1 << bk) | (1 << wr))
            if DIAG_B2D4 & (1 << bk):
                choices &= TRIANGLE_A1H1H8
            if KING_MOVES[bk] & (1 << wr):
                choices &= KING_MOVES[wr]
            for wk in bb_scan(BB_ALL & choices):
                yield (SQUARE_NAMES[wk], SQUARE_NAMES[wr], SQUARE_NAMES[bk])

or, alternatively, a version that picks a random position out of the 11340:

import random

SQUARE_NAMES = [f"{file}{rank}" for file in "abcdefgh" for rank in range(1, 9)]
ALL_SQUARES = set(range(63))
WEDGE_B2D2D4 = [9, 10, 11, 18, 19, 27]
DIAG_B2D4 = {9, 18, 27}
TRIANGLE_A1H1H8 = {f + (r << 3) for r in range(0, 8) for f in range(r, 8)}
ROOK_MOVES = [
    set(range(sq & 0o70, (sq & 0o70) + 8)) | set(range(sq & 0o07, 64, 8))
    for sq in range(64)
]
KING_MOVES = [
    {sq + d for d in (-9, -8, -7, -1, 1, 7, 8, 9)} & ALL_SQUARES for sq in range(64)
]

def random_position():
    while True:
        bk = random.choice(WEDGE_B2D2D4)
        wr = random.choice(tuple(ALL_SQUARES - ROOK_MOVES[bk]))
        choices = ALL_SQUARES.difference(KING_MOVES[bk], {bk, wr})
        if bk in DIAG_B2D4:
            choices &= TRIANGLE_A1H1H8
        if wr in KING_MOVES[bk]:
            choices &= KING_MOVES[wr]
        if choices:
            wk = random.choice(tuple(choices))
            return (SQUARE_NAMES[wk], SQUARE_NAMES[wr], SQUARE_NAMES[bk])

or a version that doesn't need subsequent rotations, so picking from the 88060 unique boards:

import random

SQUARE_NAMES = [f"{file}{rank}" for file in "abcdefgh" for rank in range(1, 9)]
ALL_SQUARES = set(range(63))
CENTRE = [sq for sq in ALL_SQUARES if (sq & 0o70) not in {0, 56} and (sq & 0o07) not in {0, 7}]
ROOK_MOVES = [
    set(range(sq & 0o70, (sq & 0o70) + 8)) | set(range(sq & 0o07, 64, 8))
    for sq in range(64)
]
KING_MOVES = [
    {sq + d for d in (-9, -8, -7, -1, 1, 7, 8, 9)} & ALL_SQUARES for sq in range(64)
]

def random_position():
    while True:
        bk = random.choice(CENTRE)
        wr = random.choice(tuple(ALL_SQUARES - ROOK_MOVES[bk]))
        choices = ALL_SQUARES.difference(KING_MOVES[bk], {bk, wr})
        if wr in KING_MOVES[bk]:
            choices &= KING_MOVES[wr]
        if choices:
            wk = random.choice(tuple(choices))
            return (SQUARE_NAMES[wk], SQUARE_NAMES[wr], SQUARE_NAMES[bk])

Then it's definitely not a 2kyu kata, maybe 5kyu at best. Whether you had fun solving the kata or not is an entirely different matter (that has nothing to do with the difficulty assessment).

OK, I have reduced the number of tests by a factor of 10.

I am not sure I agree with this... My solution is an example of one which has largely correct logic, but with many specific cases that it handles wrong. Yesterday when there were 500 I was passing anywhere between 1-150 of the random tests, but usually about 20-30 before finding a case which I handle wrong. (You can fork the solution to test it out yourself and see how often it fails)

I think for a purple kata its fair enough to require high performance, but thats just my opinion. If the new low amount now allows for 'basic' search algorithms, etc. then this might even be blue.

Yes you need a lot of tests to get enough variety.. forgot about that. 50 probably isnt enough. About performance, I dont know if you could do a basic search algorithm that consistently needs 16 moves without implementing a lot of logic (and being somewhat fast). But maybe thats wrong

I reverted the change on the number of random tests, and added a paragraph in the description that references the Chess Endgame Database you referenced, Kacarott.

Thank you for the suggestion!

Glad you took the time to work on this kata, and thank you for the suggestion! What state of the game would you suggest to include in the output? The starting position, the position before the last one or two moves, or all states of the sequence from start to end? The latter might produce long output (a sequence could have up to 50 moves)? What did you have in mind?

What I used for testing, was every position when it was white's turn, so comparing two boards I could see where I moved, and then how black reacted. And I think somewhat long output is quite ok, as long as it is only produced when the user fails a test (and perhaps it could be an optional thing, that the user has to set DISPLAY = True or something)

No idea. It doesn't make sense. I estimated its difficulty to 2 kyu when I created it over a year ago. But I guess no-one has ever since given an estimation for it, so I don't have any hope anymore something will happen with it.

This "exception" was intended and mentioned in the description, as well as whether this would be applicable to the full test suite. Maybe you missed that part?

True, such example tests assume that a solution would always find a mate in one, but I have trouble imagining a solution that would somehow not go for the direct win, so I consider such example tests to actually help with what one would want to achieve first in doing this kata. Maybe my imagination for alternative solutions falls short... On the other hand, if the example tests would have to play a game for potentially 16 moves, they would become unpredictable and thus need much more logic, which would maybe give too much code that could be reused for solving the kata itself.

Maybe you missed that part?

Seems so.... x)

about the tests, what you can do is put the "tester" in the preloaded part (being sure it cannot solve the task in place of the user), then, you put a copy of it in the test cases, so that the user cannot abuse of that preloaded part (you can even delete the function at the beginning of the test cases, to be sure). This way, you could have sample tests following the contract (take a look at doc's hard kata, this is the wy he implements them, generally).

About the logic/imagination and all, I honestly don't know. I honestly think I won't solve this one (the only way I could think of for now is to build sort of a FSM. I can picture the general thing by playing the game myself but cannot see how to actually implement it...), unless spending A LOT of time on it.

You're right, that solution setup could have given the impression that some properties are required to be present. This is not true, so I have removed that code and instead added the suggested parsing in comments, as I don't consider that parsing to be relevant to this kata's objective. I could of course have given the positions as individual arguments, but I prefer the human readable (and common) position format.

It is true that the initial position of the black king is not adding anything, but I prefer to stick with a complete initial position. Leaving out the black king could come across as strange to some. Anyway, you are free to ignore it. ;-)

I had taken the default choice of the Python version :/ So now it's updated to 2.7 which indeed is a tad faster.

There are currently 500 random tests in the Python version, and 10 000 in the JavaScript version.

ah no, don't default it to 2.7, please. rather, put that in the preloaded part:

try:
    str.maketrans('r','e')
except:
    test.expect(False, "don't use python 2.7.")

so that there is not "perf cheat", but enforcing 2.7 seems just very wrong to me... ;)

About the input, the string format is perfect, and I wouldn't even provide the parser. Considering the task, it's absolutely trivial ofr any user who will attempt the kata. ;)

OK, version is now 3.6, and I added the preloaded code you suggested. Thanks!

I removed the parser from the initial code. You're right, it should be trivial.