introduction

Ce défi est similaire aux problèmes du projet Euler . Je l'ai trouvé parce que je jouais à un jeu de société trompeusement simple et que je ne pouvais pas trouver de solution efficace pour répondre à une simple question sur ses mécanismes.

Quarto est une variante amusante de 4 d'affilée. Il se joue sur un plateau de 4 x 4 avec 16 pièces uniques (aucune pièce n'est dupliquée). Chaque tour, chaque joueur place 1 pièce sur le plateau. Chaque pièce a 4 caractéristiques binaires (courte / haute, noire / blanche, carrée / circulaire, creuse / solide). Le but est d'en faire quatre de suite, soit horizontalement, verticalement ou le long des 2 diagonales, pour n'importe laquelle des quatre caractéristiques! Donc 4 pièces noires, 4 pièces blanches, 4 pièces hautes, 4 pièces courtes, 4 pièces carrées, 4 pièces circulaires, 4 pièces creuses ou 4 pièces solides.

L'image ci-dessus montre un jeu terminé, il y a quatre de suite à cause de 4 pièces carrées.

Défi

Dans Quarto, certains matchs peuvent se terminer par un match nul.

Le nombre total de positions finales possibles est d' 16!environ 20 000 milliards.

Combien de ces positions finales sont des tirages?

Règles

1. La solution doit être un programme qui calcule et génère le nombre total de positions finales qui sont des tirages. La bonne réponse est414298141056

2. Vous ne pouvez utiliser que les informations des règles du jeu qui ont été déduites manuellement (pas de preuve assistée par ordinateur).

3. Les simplifications mathématiques du problème sont autorisées, mais doivent être expliquées et prouvées (manuellement) dans votre solution.

4. Le gagnant est celui qui a la solution la plus optimale en termes de temps d'exécution du processeur.

5. Pour déterminer le gagnant, j'exécuterai chaque solution avec une durée d'exécution inférieure à 30 m sur un MacBook Pro Intel Core i7 2,5 GHz avec 16 Go de RAM .

6. Aucun point bonus pour trouver une solution qui fonctionne également avec d'autres tailles de cartes. Même si ce serait bien.

7. Le cas échéant, votre programme doit compiler en 1 minute sur le matériel mentionné ci-dessus (pour éviter les abus d'optimisation du compilateur)

8. Les failles par défaut ne sont pas autorisées

Soumissions

Veuillez poster:

1. Le code ou un lien github / bitbucket vers le code.
2. La sortie du code.
3. Votre temps de course mesuré localement
4. Une explication de votre approche.

Date limite

La date limite pour les soumissions est le 1er mars, donc encore beaucoup de temps.

C: 414298141056 tirages trouvés en environ 5 2,5 minutes.

Recherche simple en profondeur avec une table de transposition sensible à la symétrie. Nous utilisons la symétrie des attributs sous permutation et la symétrie dièdre 8 fois de la carte.

#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));
}

Score mesuré (@wvdz):

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

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

Score (utilisateur + sys): 1m35.727s

Java, 414298141056 nuls, 23m42.272s

J'espère que ce n'est pas mal vu de publier une solution à son propre défi, mais la raison pour laquelle j'ai posté ce défi en premier lieu était que cela me rendait fou de ne pas pouvoir trouver une solution efficace moi-même. Mon meilleur essai prendrait des jours.

Après avoir étudié la réponse de user1502040 , j'ai réussi à modifier mon code pour qu'il s'exécute dans un délai assez raisonnable. Ma solution est toujours très différente, mais j'ai volé quelques idées:

• Au lieu de me concentrer sur les positions finales, je me concentre sur le fait de jouer le jeu, en mettant un morceau après l'autre sur le plateau. Cela me permet de construire un tableau de positions sémantiquement identiques avec le nombre correct.
• La réalisation de l'ordre dans lequel les pièces sont placées est importante: elles doivent être placées de manière à maximiser les chances de gagner tôt.

La principale différence entre cette solution et celle de l'utilisateur1502040 est que je n'utilise pas une table Zobrist, mais une représentation canonique d'une carte, où je considère que chaque carte a 48 transpositions possibles sur les caractéristiques (2 * 4!). Je ne fais pas pivoter ou transposer la planche entière, mais juste les caractéristiques des pièces.

C'est le mieux que j'ai pu trouver. Les idées d'optimisations évidentes ou moins évidentes sont les bienvenues!

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];
    }
}

Score mesuré:

$ time java -jar quarto.jar 
414298141056

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

Score (utilisateur + sys): 23m42.272s