33
$\begingroup$

Reminder:

Everybody knows that we can place 8 queens in a chessboard without threatening each other (see here). Same reasoning can be applied for knights, bishops, rooks and kings. Giving respectively 32 knights, 14 bishops, 8 rooks, and 16 kings.

Problem:

If we assign to each type of piece a value inversely proportional of the number of this we can place. It means Knights = 1/32. Bishop = 1/14. Rook = 1/8. Queen = 1/8 and King = 1/16.

What is the best sum value we can achieve mixing these pieces still with none able to take each other?

Example

enter image description here

In this position we have 1 queen, 4 rooks, 1 knight and 2 kings, so the value would be 1/8 + 4/8 + 0/14 + 1/32 + 2/16 = 25/32 = 0.78125.
Can you beat that score?
Hard Question: Can you prove that your answer is optimal?

Actual High scores

@evargalo 1.2857
@keeta 1.303
@Blcknght 1.3125
@oray 1.3348 (optimal).

source: Gyozo Nagy in IBM Research Ponder this - August 2003 [found in Diophante.fr]

Improve this question
$\endgroup$
13
  • 12
    $\begingroup$ 0,78125. Can you beat that score? -> sure. I can get a score of 1 by using only one kind of piece ;o) $\endgroup$
    – Evargalo
    Commented Feb 23, 2018 at 13:25
  • 5
    $\begingroup$ I must just be overlooking smg obvious, but can you show one can place 16 bishops ? I'm stuck at 14... $\endgroup$
    – Evargalo
    Commented Feb 23, 2018 at 13:27
  • 1
    $\begingroup$ The puzzle is not mine, but standard chess points would be a different problem.from my point of view this way of scoring allows to give credit to the use of "difficult to place" pieces like rooks and also the use of kings (that has no "standard" value). $\endgroup$
    – Untitpoi
    Commented Feb 23, 2018 at 15:04
  • 1
    $\begingroup$ why does the queen have the same score as Rook? $\endgroup$
    – Oray
    Commented Feb 23, 2018 at 20:08
  • 1
    $\begingroup$ @Oray Because a chessboard can contain at most 8 non-attacking rooks, just like it can contain at most 8 non-attacking queens. Therefore they are both given the score of 1/8. $\endgroup$
    – Jaap Scherphuis
    Commented Feb 23, 2018 at 21:42

5 Answers 5

Reset to default
14
$\begingroup$

Here is the most probable optimal solution with some extra modification of previous answers:

enter image description here

The score is 1.3348.

Here is the brute Force Code written by @fireflame241 confirming this is actually optimal.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ My brute-force code shows that this (1.3348215) is the optimal solution. $\endgroup$
    – fireflame241
    Commented Feb 25, 2018 at 6:08
  • $\begingroup$ @fireflame241 You have the maximum six-row score listed as 236; isn’t it 240? lichess.org/editor/8/8/3bbnbb/r7/7k/2r5/1r6/3bnbbb_w_-_- $\endgroup$
    – Ry-
    Commented Feb 26, 2018 at 7:27
  • $\begingroup$ I think your maxDensity checking is too rigorous. Indeed, counterexample. At y=7 the whole clause won't run because y >= height - 1. Nor will it run at y=0 or y=1 because y < height - maxDensities.length + 1. Fine. But at y=6, x=0 it will say there are tilesLeft=15 squares left, but it's 16, we haven't placed anything on (0,6) yet! Same for y=3,4,5. So the maxDensity values are compromised, so the larger boards are compromised. $\endgroup$
    – Wolfzoon
    Commented Feb 28, 2018 at 11:34
16
$\begingroup$

1.303

Similar to @Evargalo:



Mine has 8 knights, 8 kings, 6 bishops and 1 rook: 8/32 + 8/16 + 6/14 + 1/8

Note 1 on optimization: Clearly no queens should be used since a queen will attack more squares than a rook at the same score.

Improve this answer
$\endgroup$
1
  • $\begingroup$ ahhh if smoeone can prove that this is optimal I'll get all brainwet $\endgroup$
    – Stefano
    Commented Feb 24, 2018 at 15:08
11
$\begingroup$

With a slight variation on Keeta's solution, I get a score of 1.3125:

Relative to Keeta's solution I lose a king but add a bishop. The score is:
1/8 (1 rook) + 7/14 (7 bishops) + 7/16 (7 kings) + 8/32 (8 knights) = 21/16, which is exactly 1.3125

board image

Improve this answer
$\endgroup$
1
  • $\begingroup$ +1 I had the exact same solution - I was just checking it when you posted! $\endgroup$
    – Level River St
    Commented Feb 24, 2018 at 3:02
10
$\begingroup$

Just a first attempt to demonstrate that

Yes, you can score better than $1$.
This position gets a score of $35/32=1.09375$
This position

This new attempt is even better

scoring $38/32=1.1875$
That position

Or even

scoring $2/8+8/16+4/14+8/32=1.2857$
new best

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That's a nice start, let's see if someone can beat you now! $\endgroup$
    – Untitpoi
    Commented Feb 23, 2018 at 14:42
  • 2
    $\begingroup$ Note on second attempt: you could replace the bottom-right knight with a king for +1/32 points. $\endgroup$
    – boboquack
    Commented Feb 23, 2018 at 21:48
4
$\begingroup$

This solution when rooks are excluded, scoring 37/28 ≈ 1.321, is pretty neat too:

And here’s my version of the brute-force proof that 299/224 is optimal, with a variation of the optimization @fireflame241 used. I implemented it incorrectly the first time and wasted 48 hours, oops. It now runs in about 50 seconds.

#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

enum {
    BOARD_WIDTH = 8,
    BOARD_HEIGHT = 8,
};

/* Piece values:
 * knight 1/32 = 7/224
 * bishop 1/14 = 16/224
 * rook 1/8    = 28/224
 * king 1/16   = 14/224
 *
 * loose upper bound = 64*28 = 1792 fits in int
 */
typedef int_fast8_t index_t;
typedef uint_fast16_t score_t;
typedef uint_fast8_t population_t;

_Static_assert((index_t)(-1) < 0, "easy row + dy comparisons must be possible");
_Static_assert((population_t)(BOARD_WIDTH * BOARD_HEIGHT) == BOARD_WIDTH * BOARD_HEIGHT, "population type must suit the board");
_Static_assert((index_t)(BOARD_WIDTH * BOARD_HEIGHT) == BOARD_WIDTH * BOARD_HEIGHT, "index type must be able to represent one past the last board index");

#define PRIscore PRIuFAST16
#define SCORE_MAX UINT_FAST16_MAX

enum {
    KNIGHT_VALUE = 7,
    BISHOP_VALUE = 16,
    ROOK_VALUE = 28,
    KING_VALUE = 14,
};

enum piece {
    EMPTY = 0,
    KNIGHT,
    BISHOP,
    ROOK,
    KING,
};

struct board {
    enum piece pieces[BOARD_HEIGHT][BOARD_WIDTH];

    bool downward_diagonals_attacked[BOARD_HEIGHT + BOARD_WIDTH - 1];
    population_t downward_diagonal_population[BOARD_HEIGHT + BOARD_WIDTH - 1];
    bool upward_diagonals_attacked[BOARD_HEIGHT + BOARD_WIDTH - 1];
    population_t upward_diagonal_population[BOARD_HEIGHT + BOARD_WIDTH - 1];
    bool rows_attacked[BOARD_HEIGHT];
    population_t row_population[BOARD_HEIGHT];
    bool columns_attacked[BOARD_WIDTH];
    population_t column_population[BOARD_WIDTH];
    population_t spot_attacks[BOARD_HEIGHT][BOARD_WIDTH];

    /* number of pieces that would be attacked by a knight in a given square */
    population_t knight_population[BOARD_HEIGHT][BOARD_WIDTH];

    /* number of pieces that would be attacked by a king in a given square */
    population_t king_population[BOARD_HEIGHT][BOARD_WIDTH];

    score_t score;
};

_Static_assert(EMPTY == 0, "empty piece must be zero");
static struct board EMPTY_BOARD;

__attribute__ ((nonnull))
static void print_board(struct board const* const board) {
    for (index_t row = 0; row < BOARD_HEIGHT; row++) {
        for (index_t column = 0; column < BOARD_WIDTH; column++) {
            char c;

            switch (board->pieces[row][column]) {
            case EMPTY:  c = '.'; break;
            case KNIGHT: c = 'N'; break;
            case BISHOP: c = 'B'; break;
            case ROOK:   c = 'R'; break;
            case KING:   c = 'K'; break;
            }

            putchar(c);
            putchar(' ');
        }

        putchar('\n');
    }

    score_t const score = board->score;
    printf("\nScores %" PRIscore "/224 = %.3f\n", score, score / 224.0);
}

__attribute__ ((const))
static index_t downward_diagonal(index_t const row, index_t const column) {
    return (BOARD_WIDTH - 1) + row - column;
}

__attribute__ ((const))
static index_t upward_diagonal(index_t const row, index_t const column) {
    return row + column;
}

/* only have to do forwards attacks, because only future pieces are up for consideration */
#define FOR_EACH_KING_ATTACK(row, column, attack_row, attack_column) \
    for (index_t dy = 0; dy <= 1; dy++) { \
        index_t const attack_row = (row) + dy; \
        if (attack_row < BOARD_HEIGHT) { \
            for (index_t dx = -dy; dx <= 1; dx++) { \
                index_t const attack_column = (column) + dx; \
                if (attack_column >= 0 && attack_column < BOARD_WIDTH) {

#define END_FOR_EACH_KING_ATTACK }}}}

#define FOR_EACH_KNIGHT_ATTACK(row, column, attack_row, attack_column) \
    for (index_t dy = 1; dy <= 2; dy++) { \
        index_t const attack_row = (row) + dy; \
        if (attack_row < BOARD_HEIGHT) { \
            index_t const dxd = 1 + (dy & 1); \
            for (index_t dx = -dxd; dx <= dxd; dx += 2 * dxd) { \
                index_t const attack_column = (column) + dx; \
                if (attack_column >= 0 && attack_column < BOARD_WIDTH) {

#define END_FOR_EACH_KNIGHT_ATTACK }}}}

__attribute__ ((nonnull))
static void place_piece(struct board* const board, index_t const row, index_t const column, enum piece const piece, score_t const value) {
    board->row_population[row]++;
    board->column_population[column]++;
    board->downward_diagonal_population[downward_diagonal(row, column)]++;
    board->upward_diagonal_population[upward_diagonal(row, column)]++;
    board->pieces[row][column] = piece;

    FOR_EACH_KING_ATTACK(row, column, attack_row, attack_column)
        board->king_population[attack_row][attack_column]++;
    END_FOR_EACH_KING_ATTACK

    FOR_EACH_KNIGHT_ATTACK(row, column, attack_row, attack_column)
        board->knight_population[attack_row][attack_column]++;
    END_FOR_EACH_KNIGHT_ATTACK

    board->score += value;
}

__attribute__ ((nonnull))
static void unplace_piece(struct board* const board, index_t const row, index_t const column, score_t const value) {
    board->row_population[row]--;
    board->column_population[column]--;
    board->downward_diagonal_population[downward_diagonal(row, column)]--;
    board->upward_diagonal_population[upward_diagonal(row, column)]--;
    board->pieces[row][column] = EMPTY;

    FOR_EACH_KING_ATTACK(row, column, attack_row, attack_column)
        board->king_population[attack_row][attack_column]--;
    END_FOR_EACH_KING_ATTACK

    FOR_EACH_KNIGHT_ATTACK(row, column, attack_row, attack_column)
        board->knight_population[attack_row][attack_column]--;
    END_FOR_EACH_KNIGHT_ATTACK

    board->score -= value;
}

__attribute__ ((nonnull))
static void place_rook(struct board* const board, index_t const row, index_t const column) {
    place_piece(board, row, column, ROOK, ROOK_VALUE);
    board->rows_attacked[row] = true;
    board->columns_attacked[column] = true;
}

__attribute__ ((nonnull))
static void unplace_rook(struct board* const board, index_t const row, index_t const column) {
    unplace_piece(board, row, column, ROOK_VALUE);
    board->rows_attacked[row] = false;
    board->columns_attacked[column] = false;
}

__attribute__ ((nonnull))
static void place_bishop(struct board* const board, index_t const row, index_t const column) {
    place_piece(board, row, column, BISHOP, BISHOP_VALUE);
    board->upward_diagonals_attacked[upward_diagonal(row, column)] = true;
    board->downward_diagonals_attacked[downward_diagonal(row, column)] = true;
}

__attribute__ ((nonnull))
static void unplace_bishop(struct board* const board, index_t const row, index_t const column) {
    unplace_piece(board, row, column, BISHOP_VALUE);
    board->upward_diagonals_attacked[upward_diagonal(row, column)] = false;
    board->downward_diagonals_attacked[downward_diagonal(row, column)] = false;
}

__attribute__ ((nonnull))
static void place_king(struct board* const board, index_t const row, index_t const column) {
    place_piece(board, row, column, KING, KING_VALUE);

    FOR_EACH_KING_ATTACK(row, column, attack_row, attack_column)
        board->spot_attacks[attack_row][attack_column]++;
    END_FOR_EACH_KING_ATTACK
}

__attribute__ ((nonnull))
static void unplace_king(struct board* const board, index_t const row, index_t const column) {
    unplace_piece(board, row, column, KING_VALUE);

    FOR_EACH_KING_ATTACK(row, column, attack_row, attack_column)
        board->spot_attacks[attack_row][attack_column]--;
    END_FOR_EACH_KING_ATTACK
}

__attribute__ ((nonnull))
static void place_knight(struct board* const board, index_t const row, index_t const column) {
    place_piece(board, row, column, KNIGHT, KNIGHT_VALUE);

    FOR_EACH_KNIGHT_ATTACK(row, column, attack_row, attack_column)
        board->spot_attacks[attack_row][attack_column]++;
    END_FOR_EACH_KNIGHT_ATTACK
}

__attribute__ ((nonnull))
static void unplace_knight(struct board* const board, index_t const row, index_t const column) {
    unplace_piece(board, row, column, KNIGHT_VALUE);

    FOR_EACH_KNIGHT_ATTACK(row, column, attack_row, attack_column)
        board->spot_attacks[attack_row][attack_column]--;
    END_FOR_EACH_KNIGHT_ATTACK
}

__attribute__ ((nonnull))
static void maximize(struct board* const board, struct board* const maximum_board, score_t const* const limits, index_t index) {
    if (board->score > maximum_board->score) {
        *maximum_board = *board;
        print_board(board);
    }

    if (index == BOARD_WIDTH * BOARD_HEIGHT) {
        return;
    }

    if (board->score + limits[index] <= maximum_board->score) {
        return;
    }

    index_t const row = index / BOARD_WIDTH;
    index_t const column = index % BOARD_WIDTH;
    index++;

    bool const attacked = (
        board->rows_attacked[row] ||
        board->columns_attacked[column] ||
        board->downward_diagonals_attacked[downward_diagonal(row, column)] ||
        board->upward_diagonals_attacked[upward_diagonal(row, column)] ||
        board->spot_attacks[row][column] != 0
    );

    if (!attacked) {
        if (board->row_population[row] == 0 && board->column_population[column] == 0) {
            place_rook(board, row, column);
            maximize(board, maximum_board, limits, index);
            unplace_rook(board, row, column);
        }

        if (board->downward_diagonal_population[downward_diagonal(row, column)] == 0 && board->upward_diagonal_population[upward_diagonal(row, column)] == 0) {
            place_bishop(board, row, column);
            maximize(board, maximum_board, limits, index);
            unplace_bishop(board, row, column);
        }

        if (board->king_population[row][column] == 0) {
            place_king(board, row, column);
            maximize(board, maximum_board, limits, index);
            unplace_king(board, row, column);
        }

        if (board->knight_population[row][column] == 0) {
            place_knight(board, row, column);
            maximize(board, maximum_board, limits, index);
            unplace_knight(board, row, column);
        }
    }

    maximize(board, maximum_board, limits, index);
}

int main(void) {
    struct board board = EMPTY_BOARD;
    struct board maximum_board = EMPTY_BOARD;

    /* the maximum number of points achievable using the squares from that index to the last */
    score_t limits[BOARD_WIDTH * BOARD_HEIGHT];

    for (index_t i = 0; i < BOARD_WIDTH * BOARD_HEIGHT; i++) {
        limits[i] = SCORE_MAX;
    }

    for (index_t i = BOARD_WIDTH * BOARD_HEIGHT; i--;) {
        maximize(&board, &maximum_board, limits, i);
        limits[i] = maximum_board.score;
    }
}
Improve this answer
$\endgroup$
1
  • $\begingroup$ Same sub-patterns as @Keeta has below but with a slight shift. That is a grid of K, ranks of B-N-B-N, plug the hole with a R. $\endgroup$
    – pbhj
    Commented Feb 24, 2018 at 23:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.