Einführung

Diese Herausforderung ähnelt den Problemen von Project Euler . Ich habe es mir ausgedacht, weil ich ein täuschend einfaches Brettspiel gespielt habe und keine effiziente Lösung finden konnte, um eine einfache Frage zu seiner Mechanik zu beantworten.

Quarto ist eine lustige Variante von 4 in einer Reihe. Es wird auf einem 4 x 4-Brett mit 16 Einzelstücken gespielt (es werden keine Stücke dupliziert). In jeder Runde legt jeder Spieler 1 Stück auf das Brett. Jedes Stück hat 4 binäre Eigenschaften (kurz / groß, schwarz / weiß, quadratisch / kreisförmig, hohl / massiv). Das Ziel ist es, vier in einer Reihe, entweder horizontal, vertikal oder entlang der 2 Diagonalen, für eine der vier Eigenschaften zu machen! Also 4 schwarze Stücke, 4 weiße Stücke, 4 große Stücke, 4 kurze Stücke, 4 quadratische Stücke, 4 kreisförmige Stücke, 4 hohle Stücke oder 4 feste Stücke.

Das Bild oben zeigt ein fertiges Spiel, es gibt vier in einer Reihe wegen 4 quadratischer Teile.

Herausforderung

In Quarto können einige Spiele unentschieden enden.

Die Gesamtzahl der möglichen Endpositionen beträgt 16!etwa 20 Billionen.

Wie viele dieser Endpositionen sind Unentschieden?

Regeln

1. Die Lösung muss ein Programm sein, das die Gesamtzahl der gezeichneten Endpositionen berechnet und ausgibt. Die richtige Antwort ist414298141056

2. Sie dürfen nur Informationen zu den Spielregeln verwenden, die manuell abgeleitet wurden (kein computergestützter Beweis).

3. Mathematische Vereinfachungen des Problems sind zulässig, müssen jedoch in Ihrer Lösung (manuell) erklärt und bewiesen werden.

4. Der Gewinner ist derjenige mit der optimalen Lösung in Bezug auf die CPU-Laufzeit.

5. Um den Gewinner zu ermitteln, werde ich jede einzelne Lösung mit einer gemeldeten Laufzeit von weniger als 30 m auf einem MacBook Pro 2,5 GHz Intel Core i7 mit 16 GB RAM ausführen .

6. Keine Bonuspunkte für die Entwicklung einer Lösung, die auch mit anderen Boardgrößen funktioniert. Auch wenn das schön wäre.

7. Falls zutreffend, muss Ihr Programm innerhalb von 1 Minute auf der oben genannten Hardware kompiliert werden (um Missbrauch der Compileroptimierung zu vermeiden).

8. Standardlücken sind nicht zulässig

Einsendungen

Bitte posten:

1. Der Code oder ein Github / Bitbucket-Link zum Code.
2. Die Ausgabe des Codes.
3. Ihre lokal gemessene Laufzeit
4. Eine Erklärung Ihres Ansatzes.

Frist

Einsendeschluss ist der 1. März, also noch viel Zeit.

C: 414298141056 Ziehungen in ca. 5 2,5 Minuten gefunden.

Nur einfache Tiefensuche mit einer symmetriebewussten Transpositionstabelle. Wir verwenden die Symmetrie der Attribute unter Permutation und die 8-fache Dieder-Symmetrie der Platine.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef uint16_t u8;
typedef uint16_t u16;
typedef uint64_t u64;

#define P(i, j) (1 << (4 * (i) + (j)))

#define DIAG0 (P(0, 0) | P(1, 1) | P(2, 2) | P(3, 3))
#define DIAG1 (P(3, 0) | P(2, 1) | P(1, 2) | P(0, 3))

u64 rand_state;

u64 mix(u64 x) {
    u64 a = x >> 32;
    u64 b = x >> 60;
    x ^= (a >> b);
    return x * 7993060983890856527ULL;
}

u64 rand_u64() {
    u64 x = rand_state;
    rand_state = x * 6364136223846793005ULL + 1442695040888963407ULL;
    return mix(x);
}

u64 ZOBRIST_TABLE[(1 << 16)][8];

u16 transpose(u16 x) {
    u16 t = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (x & P(j, i)) {
                t |= P(i, j);
            }
        }
    }
    return t;
}

u16 rotate(u16 x) {
   u16 r = 0;
   for (int i = 0; i < 4; i++) {
       for (int j = 0; j < 4; j++) {
           if (x & P(3 - j, i)) {
                r |= P(i, j);
            }
       }
   } 
   return r;
}

void initialize_zobrist_table(void) {
    for (int i = 0; i < 1 << 16; i++) {
        ZOBRIST_TABLE[i][0] = rand_u64();
    }
    for (int i = 0; i < 1 << 16; i++) {
        int j = i;
        for (int r = 1; r < 8; r++) {
            j = rotate(j);
            if (r == 4) {
                j = transpose(i);
            }
            ZOBRIST_TABLE[i][r] = ZOBRIST_TABLE[j][0];
        }
    }
}

u64 hash_board(u16* x) {
    u64 hash = 0;
    for (int r = 0; r < 8; r++) {
        u64 h = 0;
        for (int i = 0; i < 8; i++) {
            h += ZOBRIST_TABLE[x[i]][r];
        }
        hash ^= mix(h);
    }
    return mix(hash);
}

u8 IS_WON[(1 << 16) / 8];

void initialize_is_won(void) {
    for (int x = 0; x < 1 << 16; x++) {
        bool is_won = false;
        for (int i = 0; i < 4; i++) {
            u16 stride = 0xF << (4 * i);
            if ((x & stride) == stride) {
                is_won = true;
                break;
            }
            stride = 0x1111 << i;
            if ((x & stride) == stride) {
                is_won = true;
                break;
            }
        }
        if (is_won == false) {
            if (((x & DIAG0) == DIAG0) || ((x & DIAG1) == DIAG1)) {
                is_won = true;
            }
        }
        if (is_won) {
            IS_WON[x / 8] |= (1 << (x % 8));
        }
    }
}

bool is_won(u16 x) {
    return (IS_WON[x / 8] >> (x % 8)) & 1;
}

bool make_move(u16* board, u8 piece, u8 position) {
    u16 p = 1 << position;
    for (int i = 0; i < 4; i++) {
        bool a = (piece >> i) & 1;
        int j = 2 * i + a;
        u16 x = board[j] | p;
        if (is_won(x)) {
            return false;
        }
        board[j] = x;
    }
    return true;
}

typedef struct {
    u64 hash;
    u64 count;
} Entry;

typedef struct {
    u64 mask;
    Entry* entries;
} TTable;

Entry* lookup(TTable* table, u64 hash, u64 count) {
    Entry* to_replace;
    u64 min_count = count + 1;
    for (int d = 0; d < 8; d++) {
        u64 i = (hash + d) & table->mask;
        Entry* entry = &table->entries[i];
        if (entry->hash == 0 || entry->hash == hash) {
            return entry;
        }
        if (entry->count < min_count) {
            min_count = entry->count;
            to_replace = entry;
        }
    }
    if (to_replace) {
        to_replace->hash = 0;
        to_replace->count = 0;
        return to_replace;
    }
    return NULL;
}

u64 count_solutions(TTable* ttable, u16* board, u8* pieces, u8 position) {
    u64 hash = 0;
    if (position <= 10) {
        hash = hash_board(board);
        Entry* entry = lookup(ttable, hash, 0);
        if (entry && entry->hash) {
            return entry->count;        
        }
    }
    u64 n = 0;
    for (int i = position; i < 16; i++) {
        u8 piece = pieces[i];
        u16 board1[8];
        memcpy(board1, board, sizeof(board1));
        u8 variable_ordering[16] = {0, 1, 2, 3, 4, 8, 12, 6, 9, 5, 7, 13, 10, 11, 15, 14};
        if (!make_move(board1, piece, variable_ordering[position])) {
            continue;
        }
        if (position == 15) {
            n += 1;
        } else {
            pieces[i] = pieces[position];
            n += count_solutions(ttable, board1, pieces, position + 1); 
            pieces[i] = piece;
        }
    }
    if (hash) {
        Entry* entry = lookup(ttable, hash, n);
        if (entry) {
            entry->hash = hash;
            entry->count = n;
        }
    }
    return n;
}

int main(void) {
    TTable ttable;
    int ttable_size = 1 << 28;
    ttable.mask = ttable_size - 1;
    ttable.entries = calloc(ttable_size, sizeof(Entry));
    initialize_zobrist_table();
    initialize_is_won();
    u8 pieces[16];
    for (int i = 0; i < 16; i++) {pieces[i] = i;}
    u16 board[8] = {0};
    printf("count: %lu\n", count_solutions(&ttable, board, pieces, 0));
}

Gemessene Punktzahl (@wvdz):

$ clang -O3 -march=native quarto_user1502040.c
$ time ./a.out
count: 414298141056

real    1m37.299s
user    1m32.797s
sys     0m2.930s

Punktzahl (Benutzer + System): 1: 35,727 Sekunden

Java, 414298141056 Draws, 23m42.272s

Ich hoffe, es ist nicht verpönt, eine Lösung für die eigene Herausforderung zu veröffentlichen, aber der Grund, warum ich diese Herausforderung überhaupt veröffentlicht habe, war, dass es mich verrückt machte, dass ich selbst keine effiziente Lösung finden konnte. Mein bester Versuch würde Tage dauern.

Nachdem ich die Antwort von user1502040 studiert hatte , gelang es mir tatsächlich, meinen Code so zu ändern, dass er innerhalb einer angemessenen Zeit ausgeführt wurde. Meine Lösung unterscheidet sich immer noch erheblich, aber ich habe einige Ideen gestohlen:

• Anstatt mich auf die Endpositionen zu konzentrieren, konzentriere ich mich darauf, das Spiel tatsächlich zu spielen und ein Stück nach dem anderen auf das Brett zu legen. Auf diese Weise kann ich eine Tabelle mit semantisch identischen Positionen mit der richtigen Anzahl erstellen.
• Es ist wichtig, die Reihenfolge zu erkennen, in der die Teile platziert werden: Sie sollten so platziert werden, dass Sie die Chance auf einen frühen Gewinn maximieren.

Der Hauptunterschied zwischen dieser Lösung und der von user1502040 besteht darin, dass ich keine Zobrist-Tabelle verwende, sondern eine kanonische Darstellung einer Karte , bei der jede Karte 48 mögliche Transpositionen über die Eigenschaften aufweist (2 * 4!). Ich drehe oder transponiere nicht das ganze Brett, sondern nur die Eigenschaften der Teile.

Dies ist das Beste, was ich mir vorstellen kann. Ideen für offensichtliche oder weniger offensichtliche Optimierungen sind herzlich willkommen!

public class Q {

    public static void main(String[] args) {
        System.out.println(countDraws(getStartBoard(), 0));
    }

    /** Order of squares being filled, chosen to maximize the chance of an early win */
    private static int[] indexShuffle = {0, 5, 10, 15, 14, 13, 12, 9, 1, 6, 3, 2, 7, 11, 4, 8};

    /** Highest depth for using the lookup */
    private static final int MAX_LOOKUP_INDEX = 10;

    public static long countDraws(long board, int turn) {
        long signature = 0;
        if (turn < MAX_LOOKUP_INDEX) {
            signature = getSignature(board, turn);
            if (cache.get(turn).containsKey(signature))
                return cache.get(turn).get(signature);
        }
        int indexShuffled = indexShuffle[turn];
        long count = 0;
        for (int n = turn; n < 16; n++) {
            long newBoard = swap(board, indexShuffled, indexShuffle[n]);
            if (partialEvaluate(newBoard, indexShuffled))
                continue;
            if (turn == 15)
                count++;
            else
                count += countDraws(newBoard, turn + 1);
        }
        if (turn < MAX_LOOKUP_INDEX)
            cache.get(turn).put(signature, count);
        return count;
    }

    /** Get the canonical representation for this board and turn */
    private static long getSignature(long board, int turn) {
        int firstPiece = getPiece(board, indexShuffle[0]);
        long signature = minTranspositionValues[firstPiece];
        List<Integer> ts = minTranspositions.get(firstPiece);
        for (int n = 1; n < turn; n++) {
            int min = 16;
            List<Integer> ts2 = new ArrayList<>();
            for (int t : ts) {
                int piece = getPiece(board, indexShuffle[n]);
                int posId = transpositions[piece][t];
                if (posId == min) {
                    ts2.add(t);
                } else if (posId < min) {
                    min = posId;
                    ts2.clear();
                    ts2.add(t);
                }
            }
            ts = ts2;
            signature = signature << 4 | min;
        }
        return signature;
    }

    private static int getPiece(long board, int position) {
        return (int) (board >>> (position << 2)) & 0xf;
    }

    /** Only evaluate the relevant winning possibilities for a certain turn */
    private static boolean partialEvaluate(long board, int turn) {
        switch (turn) {
            case 15:
                return evaluate(board, masks[8]);
            case 12:
                return evaluate(board, masks[3]);
            case 1:
                return evaluate(board, masks[5]);
            case 3:
                return evaluate(board, masks[9]);
            case 2:
                return evaluate(board, masks[0]) || evaluate(board, masks[6]);
            case 11:
                return evaluate(board, masks[7]);
            case 4:
                return evaluate(board, masks[1]);
            case 8:
                return evaluate(board, masks[4]) || evaluate(board, masks[2]);
        }
        return false;
    }

    private static List<Map<Long, Long>> cache = new ArrayList<>();
    static {
        for (int i = 0; i < 16; i++)
            cache.add(new HashMap<>());
    }

    private static boolean evaluate(long board, long[] masks) {
        return _evaluate(board, masks) || _evaluate(~board, masks);
    }

    private static boolean _evaluate(long board, long[] masks) {
        for (long mask : masks)
            if ((board & mask) == mask)
                return true;
        return false;
    }

    private static long swap(long board, int x, int y) {
        if (x == y)
            return board;
        if (x > y)
            return swap(board, y, x);
        long xValue = (board & swapMasks[1][x]) << ((y - x) * 4);
        long yValue = (board & swapMasks[1][y]) >>> ((y - x) * 4);
        return board & swapMasks[0][x] & swapMasks[0][y] | xValue | yValue;
    }

    private static long getStartBoard() {
        long board = 0;
        for (long n = 0; n < 16; n++)
            board |= n << (n * 4);
        return board;
    }

    private static List<Integer> allPermutations(int input, int size, int idx, List<Integer> permutations) {
        for (int n = idx; n < size; n++) {
            if (idx == 3)
                permutations.add(input);
            allPermutations(swapBit(input, idx, n), size, idx + 1, permutations);
        }
        return permutations;
    }

    private static int swapBit(int in, int x, int y) {
        if (x == y)
            return in;
        int xMask = 1 << x;
        int yMask = 1 << y;
        int xValue = (in & xMask) << (y - x);
        int yValue = (in & yMask) >>> (y - x);
        return in & ~xMask & ~yMask | xValue | yValue;
    }

    private static int[][] transpositions = new int[16][48];
    static {
        for (int piece = 0; piece < 16; piece++) {
            transpositions[piece][0] = piece;
            List<Integer> permutations = allPermutations(piece, 4, 0, new ArrayList<>());
            for (int n = 1; n < 24; n++)
                transpositions[piece][n] = permutations.get(n);
            permutations = allPermutations(~piece & 0xf, 4, 0, new ArrayList<>());
            for (int n = 24; n < 48; n++)
                transpositions[piece][n] = permutations.get(n - 24);
        }
    }

    private static int[] minTranspositionValues = new int[16];
    private static List<List<Integer>> minTranspositions = new ArrayList<>();
    static {
        for (int n = 0; n < 16; n++) {
            int min = 16;
            List<Integer> elems = new ArrayList<>();
            for (int t = 0; t < 48; t++) {
                int elem = transpositions[n][t];
                if (elem < min) {
                    min = elem;
                    elems.clear();
                    elems.add(t);
                } else if (elem == min)
                    elems.add(t);
            }
            minTranspositionValues[n] = min;
            minTranspositions.add(elems);
        }
    }

    private static final long ROW_MASK = 1L | 1L << 4 | 1L << 8 | 1L << 12;
    private static final long COL_MASK = 1L | 1L << 16 | 1L << 32 | 1L << 48;
    private static final long FIRST_DIAG_MASK = 1L | 1L << 20 | 1L << 40 | 1L << 60;
    private static final long SECOND_DIAG_MASK = 1L << 12 | 1L << 24 | 1L << 36 | 1L << 48;

    private static long[][] masks = new long[10][4];
    static {
        for (int m = 0; m < 4; m++) {
            long row = ROW_MASK << (16 * m);
            for (int n = 0; n < 4; n++)
                masks[m][n] = row << n;
        }
        for (int m = 0; m < 4; m++) {
            long row = COL_MASK << (4 * m);
            for (int n = 0; n < 4; n++)
                masks[m + 4][n] = row << n;
        }
        for (int n = 0; n < 4; n++)
            masks[8][n] = FIRST_DIAG_MASK << n;
        for (int n = 0; n < 4; n++)
            masks[9][n] = SECOND_DIAG_MASK << n;
    }

    private static long[][] swapMasks;
    static {
        swapMasks = new long[2][16];
        for (int n = 0; n < 16; n++)
            swapMasks[1][n] = 0xfL << (n * 4);
        for (int n = 0; n < 16; n++)
            swapMasks[0][n] = ~swapMasks[1][n];
    }
}

Gemessene Punktzahl:

$ time java -jar quarto.jar 
414298141056

real    20m51.492s
user    23m32.289s
sys     0m9.983s

Punktzahl (Benutzer + System): 23m42.272s