Indice de vitesse

Cluedo / Clue est un jeu de société classique avec un composant de gameplay de déduction convaincant. Indice de vitesse est une variante pour 3-6 joueurs qui met l'accent sur ce composant en utilisant uniquement les cartes. Le résultat est que la seule différence entre le Cluedo standard et le Speed ​​Clue est que chaque joueur encore dans le jeu peut faire toute suggestion qu'il souhaite à son tour au lieu d'attendre d'atteindre une salle spécifique à la merci des jets de dés et des suggestions des autres joueurs. Si vous n'avez jamais joué à Cluedo auparavant, ou si vous voulez être certain des différences explicites entre les deux versions, vous pouvez trouver un ensemble complet de règles de Speed ​​Clue ici .

Objectif

Écrivez et soumettez un programme d'IA pour jouer à Speed ​​Clue avant le 15 mai 2014 à 00h00 GMT. Après ce temps, je dirigerai un tournoi en utilisant toutes les entrées légales. Le participant dont l'IA remporte le plus de matchs du tournoi remporte le défi.

Spécifications AI

Vous pouvez écrire votre IA dans à peu près n'importe quelle langue que vous choisissez, en utilisant toutes les techniques que vous utilisez, tant qu'il utilise strictement le protocole d'application sur une connexion TCP / IP pour jouer à des jeux avec le serveur. Une explication détaillée de toutes les restrictions peut être trouvée ici .

Comment jouer

Commencez par bifurquer le référentiel du concours GitHub . Ajoutez un répertoire sous le entriesrépertoire nommé à l'aide de votre nom d'utilisateur StackExchange et développez votre code dans ce dossier. Lorsque vous êtes prêt à soumettre votre candidature, faites une demande de tirage avec vos révisions, puis suivez ces instructions pour annoncer votre candidature sur ce site.

J'ai fourni du code et des fichiers JAR dans le corerépertoire pour vous aider à démarrer; voir mon site pour un guide approximatif pour les matériaux. De plus, d'autres joueurs soumettent un code d'assistance en plus de leurs entrées pour vous aider à être opérationnel. Prenez le temps d'explorer les entrées et n'oubliez pas de tester votre entrée par rapport aux entrées des autres avant de soumettre!

Résultats

Place | User         | AI                 | Result
------+--------------+--------------------+-------------------------------------------------------
    1 | gamecoder    | SpockAI            | 55.75%
    2 | Peter Taylor | InferencePlayer    | 33.06%
    3 | jwg          | CluePaddle         | 20.19%
    4 | Peter Taylor | SimpleCluedoPlayer |  8.34%
    5 | gamecoder    | RandomPlayer       |  1.71%
 ---- | ray          | 01                 | Player "ray-01" [3] sent an invalid accuse message: ""

Les résultats ci-dessus montrent le pourcentage de victoires de chaque IA qualifiée sur les 25 200 matchs valides auxquels elle a participé. Il y a eu 30 000 matchs au total qui ont compté dans les résultats, et 6 100 environ ont été réduits lors de la 01disqualification.

Une mention honorable doit être attribuée à l' 01IA de ray . Mes premiers tests ont montré que c'était le plus fort, et je m'attendais à ce qu'il gagne la compétition. Cependant, il semble avoir un bug très intermittent qui, pour autant que je puisse deviner, le conduit à éliminer toutes les solutions possibles. Le tournoi avait terminé tous les matchs à trois joueurs et avait commencé les matchs à quatre joueurs (12 000 matchs en!) Lorsque 01le bug a été révélé. Si je considère simplement le classement des matchs à 3 joueurs, les résultats ressemblent à ceci:

Place | User         | AI                 | Result
------+--------------+--------------------+--------
    1 | ray          | 01                 | 72.10%
    2 | gamecoder    | SpockAI            | 51.28%
    3 | Peter Taylor | InferencePlayer    | 39.97%
    4 | Peter Taylor | SimpleCluedoPlayer | 17.65%
    5 | jwg          | CluePaddle         | 16.92%
    6 | gamecoder    | RandomPlayer       |  2.08%

J'avais prévu de faire de l'exploration de données sur les résultats, mais je suis épuisé. J'ai eu des difficultés techniques à faire en sorte que la compétition se poursuive (pannes de courant, redémarrages du système), ce qui a nécessité une réécriture complète du serveur du concours pour sauvegarder sa progression au fur et à mesure. Je vais commenter et valider toutes les modifications du code avec tous les fichiers de résultats qui ont été générés au cas où quelqu'un serait toujours intéressé. Si je décide de faire également l'exploration de données, mes résultats seront également ajoutés au référentiel.

Merci d'avoir joué!

AI01 - Python 3

Je ne peux pas encore trouver un meilleur nom pour cela :-P.

Identifiant : ray-ai01

Technologie : Python 3

Sélectionné : oui

Arguments :ai01.py identifier port

Description : Travail par inférence. Lorsque le nombre de cartes dont le propriétaire n'est pas connu est inférieur à un seuil, cette IA commence à éliminer toutes les solutions impossibles par inférence globale récursive. Sinon, il utilise l'inférence locale.

#!/usr/bin/env python
import itertools

from speedclue.playerproxy import Player, main
from speedclue.cards import CARDS
from speedclue.protocol import BufMessager

# import crash_on_ipy


class Card:
    def __init__(self, name, type):
        self.name = name
        self.possible_owners = []
        self.owner = None
        self.in_solution = False
        self.disproved_to = set()
        self.type = type

    def __repr__(self):
        return self.name

    def log(self, *args, **kwargs):
        pass

    def set_owner(self, owner):
        assert self.owner is None
        assert self in owner.may_have
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.owner = owner
        owner.must_have.add(self)
        self.type.rest_count -= 1

    def set_as_solution(self):
        # import pdb; pdb.set_trace()
        assert self.owner is None
        self.type.solution = self
        self.in_solution = True
        for player in self.possible_owners:
            player.may_have.remove(self)
        self.possible_owners.clear()
        self.type.rest_count -= 1

    def __hash__(self):
        return hash(self.name)


class CardType:
    def __init__(self, type_id):
        self.type_id = type_id
        self.cards = [Card(name, self) for name in CARDS[type_id]]
        self.rest_count = len(self.cards)
        self.solution = None


class PlayerInfo:
    def __init__(self, id):
        self.id = id
        self.must_have = set()
        self.may_have = set()
        self.selection_groups = []
        self.n_cards = None

    def __hash__(self):
        return hash(self.id)

    def set_have_not_card(self, card):
        if card in self.may_have:
            self.may_have.remove(card)
            card.possible_owners.remove(self)

    def log(self, *args, **kwargs):
        pass

    def update(self):
        static = False
        updated = False
        while not static:
            static = True
            if len(self.must_have) == self.n_cards:
                if not self.may_have:
                    break
                for card in self.may_have:
                    card.possible_owners.remove(self)
                self.may_have.clear()
                static = False
                updated = True
            if len(self.must_have) + len(self.may_have) == self.n_cards:
                static = False
                updated = True
                for card in list(self.may_have):
                    card.set_owner(self)

            new_groups = []
            for group in self.selection_groups:
                group1 = []
                for card in group:
                    if card in self.must_have:
                        break
                    if card in self.may_have:
                        group1.append(card)
                else:
                    if len(group1) == 1:
                        group1[0].set_owner(self)
                        updated = True
                        static = False
                    elif group1:
                        new_groups.append(group1)
            self.selection_groups = new_groups

            if len(self.must_have) + 1 == self.n_cards:
                # There is only one card remain to be unknown, so this card must
                # be in all selection groups
                cards = self.may_have.copy()
                for group in self.selection_groups:
                    if self.must_have.isdisjoint(group):
                        cards.intersection_update(group)

                for card in self.may_have - cards:
                    static = False
                    updated = True
                    self.set_have_not_card(card)

        # assert self.must_have.isdisjoint(self.may_have)
        # assert len(self.must_have | self.may_have) >= self.n_cards
        return updated


class Suggestion:
    def __init__(self, player, cards, dplayer, dcard):
        self.player = player
        self.cards = cards
        self.dplayer = dplayer
        self.dcard = dcard
        self.disproved = dplayer is not None


class AI01(Player):
    def prepare(self):
        self.set_verbosity(0)

    def reset(self, player_count, player_id, card_names):
        self.log('reset', 'id=', player_id, card_names)
        self.fail_count = 0
        self.suggest_count = 0
        self.card_types = [CardType(i) for i in range(len(CARDS))]
        self.cards = list(itertools.chain(*(ct.cards for ct in self.card_types)))
        for card in self.cards:
            card.log = self.log
        self.card_map = {card.name: card for card in self.cards}
        self.owned_cards = [self.card_map[name] for name in card_names]
        self.players = [PlayerInfo(i) for i in range(player_count)]
        for player in self.players:
            player.log = self.log
        self.player = self.players[player_id]
        for card in self.cards:
            card.possible_owners = list(self.players)
        n_avail_cards = len(self.cards) - len(CARDS)
        for player in self.players:
            player.may_have = set(self.cards)
            player.n_cards = n_avail_cards // player_count \
                + (player.id < n_avail_cards % player_count)
        for card in self.owned_cards:
            card.set_owner(self.player)
        for card in self.cards:
            if card not in self.owned_cards:
                self.player.set_have_not_card(card)
        self.suggestions = []
        self.avail_suggestions = set(itertools.product(*CARDS))
        self.possible_solutions = {
            tuple(self.get_cards_by_names(cards)): 1
            for cards in self.avail_suggestions
        }
        self.filter_solutions()

    def filter_solutions(self):
        new_solutions = {}
        # assert self.possible_solutions
        join = next(iter(self.possible_solutions))
        for sol in self.possible_solutions:
            for card, type in zip(sol, self.card_types):
                if card.owner or type.solution and card is not type.solution:
                    # This candidate can not be a solution because it has a
                    # card that has owner or this type is solved.
                    break
            else:
                count = self.check_solution(sol)
                if count:
                    new_solutions[sol] = count
                    join = tuple(((x is y) and x) for x, y in zip(join, sol))
        self.possible_solutions = new_solutions
        updated = False
        for card in join:
            if card and not card.in_solution:
                card.set_as_solution()
                updated = True
                self.log('found new target', card, 'in', join)

        # self.dump()
        return updated

    def check_solution(self, solution):
        """
        This must be called after each player is updated.
        """
        players = self.players
        avail_cards = set(card for card in self.cards if card.possible_owners)
        avail_cards -= set(solution)
        if len(avail_cards) >= 10:
            return 1
        count = 0

        def resolve_player(i, avail_cards):
            nonlocal count
            if i == len(players):
                count += 1
                return
            player = players[i]
            n_take = player.n_cards - len(player.must_have)
            cards = avail_cards & player.may_have
            for choice in map(set, itertools.combinations(cards, n_take)):
                player_cards = player.must_have | choice
                for group in player.selection_groups:
                    if player_cards.isdisjoint(group):
                        # Invalid choice
                        break
                else:
                    resolve_player(i + 1, avail_cards - choice)

        resolve_player(0, avail_cards)
        return count

    def suggest1(self):
        choices = []
        for type in self.card_types:
            choices.append([])
            if type.solution:
                choices[-1].extend(self.player.must_have & set(type.cards))
            else:
                choices[-1].extend(sorted(
                    (card for card in type.cards if card.owner is None),
                    key=lambda card: len(card.possible_owners)))

        for sgi in sorted(itertools.product(*map(lambda x:range(len(x)), choices)),
                key=sum):
            sg = tuple(choices[i][j].name for i, j in enumerate(sgi))
            if sg in self.avail_suggestions:
                self.avail_suggestions.remove(sg)
                break
        else:
            sg = self.avail_suggestions.pop()
            self.fail_count += 1
            self.log('fail')
        self.suggest_count += 1
        return sg

    def suggest(self):
        sg = []
        for type in self.card_types:
            card = min((card for card in type.cards if card.owner is None),
                key=lambda card: len(card.possible_owners))
            sg.append(card.name)
        sg = tuple(sg)

        if sg not in self.avail_suggestions:
            sg = self.avail_suggestions.pop()
        else:
            self.avail_suggestions.remove(sg)
        return sg

    def suggestion(self, player_id, cards, disprove_player_id=None, card=None):
        sg = Suggestion(
            self.players[player_id],
            self.get_cards_by_names(cards),
            self.players[disprove_player_id] if disprove_player_id is not None else None,
            self.card_map[card] if card else None,
        )
        self.suggestions.append(sg)
        # Iter through the non-disproving players and update their may_have
        end_id = sg.dplayer.id if sg.disproved else sg.player.id
        for player in self.iter_players(sg.player.id + 1, end_id):
            if player is self.player:
                continue
            for card in sg.cards:
                player.set_have_not_card(card)
        if sg.disproved:
            # The disproving player has sg.dcard
            if sg.dcard:
                if sg.dcard.owner is None:
                    sg.dcard.set_owner(sg.dplayer)
            else:
                # Add a selection group to the disproving player
                sg.dplayer.selection_groups.append(sg.cards)
            self.possible_solutions.pop(tuple(sg.cards), None)

        self.update()

    def update(self):
        static = False
        while not static:
            static = True
            for card in self.cards:
                if card.owner is not None or card.in_solution:
                    continue
                if len(card.possible_owners) == 0 and card.type.solution is None:
                    # In solution
                    card.set_as_solution()
                    static = False

            for type in self.card_types:
                if type.solution is not None:
                    continue
                if type.rest_count == 1:
                    card = next(card for card in type.cards if card.owner is None)
                    card.set_as_solution()
                    static = False

            for player in self.players:
                if player is self.player:
                    continue
                if player.update():
                    static = False

            if self.filter_solutions():
                static = False

    def iter_players(self, start_id, end_id):
        n = len(self.players)
        for i in range(start_id, start_id + n):
            if i % n == end_id:
                break
            yield self.players[i % n]

    def accuse(self):
        if all(type.solution for type in self.card_types):
            return [type.solution.name for type in self.card_types]
        possible_solutions = self.possible_solutions
        if len(possible_solutions) == 1:
            return next(possible_solutions.values())
        # most_possible = max(self.possible_solutions, key=self.possible_solutions.get)
        # total = sum(self.possible_solutions.values())
        # # self.log('rate:', self.possible_solutions[most_possible] / total)
        # if self.possible_solutions[most_possible] > 0.7 * total:
        #     self.log('guess', most_possible)
        #     return [card.name for card in most_possible]
        return None

    def disprove(self, suggest_player_id, cards):
        cards = self.get_cards_by_names(cards)
        sg_player = self.players[suggest_player_id]
        cards = [card for card in cards if card in self.owned_cards]
        for card in cards:
            if sg_player in card.disproved_to:
                return card.name
        return max(cards, key=lambda c: len(c.disproved_to)).name

    def accusation(self, player_id, cards, is_win):
        if not is_win:
            cards = tuple(self.get_cards_by_names(cards))
            self.possible_solutions.pop(cards, None)
            # player = self.players[player_id]
            # for card in cards:
            #     player.set_have_not_card(card)
            # player.update()
        else:
            self.log('fail rate:', self.fail_count / (1e-8 + self.suggest_count))
            self.log('fail count:', self.fail_count, 'suggest count:', self.suggest_count)

    def get_cards_by_names(self, names):
        return [self.card_map[name] for name in names]

    def dump(self):
        self.log()
        for player in self.players:
            self.log('player:', player.id, player.n_cards,
                sorted(player.must_have, key=lambda x: x.name),
                sorted(player.may_have, key=lambda x: x.name),
                '\n    ',
                player.selection_groups)
        self.log('current:', [type.solution for type in self.card_types])
        self.log('possible_solutions:', len(self.possible_solutions))
        for sol, count in self.possible_solutions.items():
            self.log('  ', sol, count)
        self.log('id|', end='')

        def end():
            return ' | ' if card.name in [g[-1] for g in CARDS] else '|'

        for card in self.cards:
            self.log(card.name, end=end())
        self.log()
        for player in self.players:
            self.log(' *'[player.id == self.player.id] + str(player.id), end='|')
            for card in self.cards:
                self.log(
                    ' ' + 'xo'[player in card.possible_owners or player is card.owner],
                    end=end())
            self.log()


if __name__ == '__main__':
    main(AI01, BufMessager)

Le code AI peut être trouvé ici .

SimpleCluedoPlayer.java

Cette classe utilise AbstractCluedoPlayer, qui gère toutes les E / S et permet à la logique de fonctionner avec une interface typée simple. Le tout est sur github .

Cela bat le joueur aléatoire avec une forte probabilité (dans le pire des cas, il faut 15 suggestions, alors que le joueur aléatoire en prend 162 en moyenne), mais il sera facilement battu. Je lui offre de faire bouger les choses.

package org.cheddarmonk.cluedoai;

import java.io.IOException;
import java.io.PrintStream;
import java.net.UnknownHostException;
import java.util.*;

/**
 * A simple player which doesn't try to make inferences from partial information.
 * It merely tries to maximise the information gain by always making suggestions involving cards which
 * it does not know to be possessed by a player, and to minimise information leakage by recording who
 * has seen which of its own cards.
 */
public class SimpleCluedoPlayer extends AbstractCluedoPlayer {
    private Map<CardType, Set<Card>> unseenCards;
    private Map<Card, Integer> shownBitmask;
    private Random rnd = new Random();

    public SimpleCluedoPlayer(String identifier, int serverPort) throws UnknownHostException, IOException {
        super(identifier, serverPort);
    }

    @Override
    protected void handleReset() {
        unseenCards = new HashMap<CardType, Set<Card>>();
        for (Map.Entry<CardType, Set<Card>> e : Card.byType.entrySet()) {
            unseenCards.put(e.getKey(), new HashSet<Card>(e.getValue()));
        }

        shownBitmask = new HashMap<Card, Integer>();
        for (Card myCard : myHand()) {
            shownBitmask.put(myCard, 0);
            unseenCards.get(myCard.type).remove(myCard);
        }
    }

    @Override
    protected Suggestion makeSuggestion() {
        return new Suggestion(
            selectRandomUnseen(CardType.SUSPECT),
            selectRandomUnseen(CardType.WEAPON),
            selectRandomUnseen(CardType.ROOM));
    }

    private Card selectRandomUnseen(CardType type) {
        Set<Card> candidates = unseenCards.get(type);
        Iterator<Card> it = candidates.iterator();
        for (int idx = rnd.nextInt(candidates.size()); idx > 0; idx--) {
            it.next();
        }
        return it.next();
    }

    @Override
    protected Card disproveSuggestion(int suggestingPlayerIndex, Suggestion suggestion) {
        Card[] byNumShown = new Card[playerCount()];
        Set<Card> hand = myHand();
        int bit = 1 << suggestingPlayerIndex;
        for (Card candidate : suggestion.cards()) {
            if (!hand.contains(candidate)) continue;

            int bitmask = shownBitmask.get(candidate);
            if ((bitmask & bit) == bit) return candidate;
            byNumShown[Integer.bitCount(bitmask)] = candidate;
        }

        for (int i = byNumShown.length - 1; i >= 0; i--) {
            if (byNumShown[i] != null) return byNumShown[i];
        }

        throw new IllegalStateException("Unreachable");
    }

    @Override
    protected void handleSuggestionResponse(Suggestion suggestion, int disprovingPlayerIndex, Card shown) {
        if (shown != null) unseenCards.get(shown.type).remove(shown);
        else {
            // This player never makes a suggestion with cards from its own hand, so we're ready to accuse.
            unseenCards.put(CardType.SUSPECT, Collections.singleton(suggestion.suspect));
            unseenCards.put(CardType.WEAPON, Collections.singleton(suggestion.weapon));
            unseenCards.put(CardType.ROOM, Collections.singleton(suggestion.room));
        }
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, Card shown) {
        shownBitmask.put(shown, shownBitmask.get(shown) | (1 << suggestingPlayerIndex));
    }

    @Override
    protected void recordSuggestionResponse(int suggestingPlayerIndex, Suggestion suggestion, int disprovingPlayerIndex) {
        // Do nothing.
    }

    @Override
    protected Suggestion makeAccusation() {
        Set<Card> suspects = unseenCards.get(CardType.SUSPECT);
        Set<Card> weapons = unseenCards.get(CardType.WEAPON);
        Set<Card> rooms = unseenCards.get(CardType.ROOM);
        if (suspects.size() * weapons.size() * rooms.size()  == 1) {
            return new Suggestion(suspects.iterator().next(), weapons.iterator().next(), rooms.iterator().next());
        }

        return null;
    }

    @Override
    protected void recordAccusation(int accusingPlayer, Suggestion accusation, boolean correct) {
        // Do nothing.
    }

    //*********************** Public Static Interface ************************//
    public static void main(String[] args) throws Exception {
        try {
            System.setOut(new PrintStream("/tmp/speed-cluedo-player" + args[0]+".log"));
            new SimpleCluedoPlayer(args[0], Integer.parseInt(args[1])).run();
        } catch (Throwable th) {
            th.printStackTrace(System.out);
        }
    }
}

SpockAI

Identifiant: gamecoder-SpockAI

Entrée en pension: cliquez ici

Sélectionné: Oui

Technologie: Java 7 basé surcom.sadakatsu.clue.jar

Arguments: {identifier} portNumber [logOutput: true|false]

La description:

SpockAIest un joueur Speed ​​Clue construit sur une classe appelée Knowledgeque j'ai écrite. La Knowledgeclasse représente tous les états possibles que le jeu aurait pu donner à ce qui s'est passé jusqu'à présent. Il représente les solutions du jeu et les mains possibles des joueurs sous forme d'ensembles, et utilise des déductions itératives pour réduire ces ensembles autant que possible chaque fois que quelque chose est appris. SpockAIutilise cette classe pour déterminer quelles suggestions sont assurées d'avoir les résultats les plus défavorables les plus utiles et sélectionne au hasard l'une de ces suggestions à son tour. Lorsqu'il doit réfuter une suggestion, il essaie soit de montrer une carte dont il a déjà montré l'IA suggérée, soit de lui montrer une carte de la catégorie pour laquelle il a le moins réduit les possibilités. Il ne fait une accusation que lorsqu'il connaît la solution.

L'heuristique que j'ai utilisée pour déterminer la meilleure suggestion est la suivante. Une fois que toutes les informations ont été tirées d'une suggestion, la solution possible et les ensembles de mains de joueurs possibles ont été réduits (à moins que la suggestion ne révèle aucune nouvelle information). Théoriquement, la meilleure suggestion est celle qui réduit le plus le nombre de solutions possibles. Dans le cas d'une égalité, je suppose qu'une suggestion qui réduit le plus le nombre de mains possibles pour les joueurs est meilleure. Donc, pour chaque suggestion, j'essaie tous les résultats possibles qui ne conduisent pas à une contradiction dans la connaissance. Quel que soit le résultat qui présente le moins d'amélioration du nombre de solutions / mains, on suppose que c'est le résultat de la suggestion. Ensuite, je compare tous les résultats des suggestions et je choisis celui qui a le meilleur résultat. De cette façon, je garantis un gain d'informations optimal dans le pire des cas.

J'envisage d'ajouter une analyse de combinaison par force brute des solutions possibles et des mains possibles des joueurs pour les rendre SpockAIencore plus forts, mais comme SpockAIc'est déjà l'entrée la plus lente et la plus gourmande en ressources, je vais probablement sauter cela.

Avertissement:

J'avais l'intention de publier une IA pour ce concours il y a des semaines. Dans l'état actuel des choses, je n'ai pas pu commencer à écrire mon IA avant vendredi la semaine dernière, et j'ai continué à trouver des bugs ridicules dans mon code. Pour cette raison, la seule façon de me rendre SpockAIau travail avant la date limite était d'utiliser un grand pool de threads. Le résultat final est que (actuellement) SpockAI peut atteindre + 90% d'utilisation du processeur et 2 Go + d'utilisation de mémoire (bien que je blâme le garbage collector pour cela). J'ai l'intention de participer SpockAIau concours, mais si d'autres estiment que cela constitue une violation des règles , je décernerai le titre de "gagnant" à la deuxième place qui devrait l' SpockAIemporter. Si vous vous sentez de cette façon, veuillez laisser un commentaire à cet effet sur cette réponse.

InferencePlayer.java

Code complet sur Github (note: cela utilise le même AbstractCluedoPlayerque mon précédent SimpleCluedoPlayer).

Le véritable noyau de ce joueur est sa PlayerInformationclasse (ici légèrement taillée):

private static class PlayerInformation {
    final PlayerInformation[] context;
    final int playerId;
    final int handSize;
    Set<Integer> clauses = new HashSet<Integer>();
    Set<Card> knownHand = new HashSet<Card>();
    int possibleCards;
    boolean needsUpdate = false;

    public PlayerInformation(PlayerInformation[] context, int playerId, boolean isMe, int handSize, Set<Card> myHand) {
        this.context = context;
        this.playerId = playerId;
        this.handSize = handSize;
        if (isMe) {
            knownHand.addAll(myHand);
            possibleCards = 0;
            for (Card card : knownHand) {
                int cardMask = idsByCard.get(card);
                clauses.add(cardMask);
                possibleCards |= cardMask;
            }
        }
        else {
            possibleCards = allCardsMask;
            for (Card card : myHand) {
                possibleCards &= ~idsByCard.get(card);
            }

            if (playerId == -1) {
                // Not really a player: this represents knowledge about the solution.
                // The solution contains one of each type of card.
                clauses.add(suspectsMask & possibleCards);
                clauses.add(weaponsMask & possibleCards);
                clauses.add(roomsMask & possibleCards);
            }
        }
    }

    public void hasCard(Card card) {
        if (knownHand.add(card)) {
            // This is new information.
            needsUpdate = true;
            clauses.add(idsByCard.get(card));

            // Inform the other PlayerInformation instances that their player doesn't have the card.
            int mask = idsByCard.get(card);
            for (PlayerInformation pi : context) {
                if (pi != this) pi.excludeMask(mask);
            }

            if (knownHand.size() == handSize) {
                possibleCards = mask(knownHand);
            }
        }
    }

    public void excludeMask(int mask) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        if ((mask & possibleCards) != 0) {
            // The fact that we have none of the cards in the mask contains some new information.
            needsUpdate = true;
            possibleCards &= ~mask;
        }
    }

    public void disprovedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        // Exclude cards which we know the player doesn't have.
        needsUpdate = clauses.add(mask(suggestion.cards()) & possibleCards);
    }

    public void passedSuggestion(Suggestion suggestion) {
        if (knownHand.size() == handSize) return; // We can't benefit from any new information.

        excludeMask(mask(suggestion.cards()));
    }

    public boolean update() {
        if (!needsUpdate) return false;

        needsUpdate = false;

        // Minimise the clauses, step 1: exclude cards which the player definitely doesn't have.
        Set<Integer> newClauses = new HashSet<Integer>();
        for (int clause : clauses) {
            newClauses.add(clause & possibleCards);
        }
        clauses = newClauses;

        if (clauses.contains(0)) throw new IllegalStateException();

        // Minimise the clauses, step 2: where one clause is a superset of another, discard the less specific one.
        Set<Integer> toEliminate = new HashSet<Integer>();
        for (int clause1 : clauses) {
            for (int clause2 : clauses) {
                if (clause1 != clause2 && (clause1 & clause2) == clause1) {
                    toEliminate.add(clause2);
                }
            }
        }
        clauses.removeAll(toEliminate);

        // Every single-card clause is a known card: update knownHand if necessary.
        for (int clause : clauses) {
            if (((clause - 1) & clause) == 0) {
                Card singleCard = cardsById.get(clause);
                hasCard(cardsById.get(clause));
            }
        }

        // Every disjoint set of clauses of size equal to handSize excludes all cards not in the union of that set.
        Set<Integer> disjoint = new HashSet<Integer>(clauses);
        for (int n = 2; n <= handSize; n++) {
            Set<Integer> nextDisjoint = new HashSet<Integer>();
            for (int clause : clauses) {
                for (int set : disjoint) {
                    if ((set & clause) == 0) nextDisjoint.add(set | clause);
                }
            }
            disjoint = nextDisjoint;
        }

        for (int set : disjoint) excludeMask(~set);

        return true;
    }
}

Il unifie les informations sur les suggestions que le joueur n'a pas réfutées (indiquant qu'il ne détient aucune de ces cartes), les suggestions qu'il a réfutées (indiquant qu'il détient au moins une de ces cartes) et les cartes dont l'emplacement est certain. Ensuite, il applique de manière itérative quelques règles de base pour compacter ces informations dans leur essence.

Je ne pense pas qu'il y ait plus d'informations déterministes à obtenir (sauf via de fausses accusations, que je suppose trop rares pour être gênantes), même si j'ai peut-être oublié quelque chose. Il est possible pour un joueur plus sophistiqué d'estimer les probabilités que le joueur X ait la carte Y ...

L'autre domaine qui admet probablement une amélioration significative est de décider quelle suggestion faire. J'essaie de maximiser le gain d'informations en utilisant une approche de force lourde assez maladroite, mais il y a beaucoup d'heuristique mal justifiée dans l'évaluation des mérites relatifs des connaissances acquises à partir de différentes réfutations hypothétiques. Cependant, je ne vais pas essayer de régler l'heuristique jusqu'à ce que quelqu'un d'autre poste un adversaire digne.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

J'ai écrit ClueBot, un client C # pour lequel il est simple d'implémenter des IA et diverses IA, y compris la tentative la plus sérieuse appelée CluePaddle. Le code est à https://github.com/jwg4/SpeedClueContest/tree/clue_paddle avec une demande de pull a commencé à le fusionner en amont.

ClueStick est une preuve de concept qui ne fait que deviner et ignorer la plupart des événements. ClueBat est une autre IA stupide, sauf qu'elle essaie d'exploiter une faille dans ClueStick pour l'obliger à faire de fausses accusations. ClueByFour est une IA raisonnable en ce sens qu'elle fait des suggestions raisonnables et se souvient des cartes qu'elle est montrée par les autres.

CluePaddle est le plus intelligent. Il essaie de déterminer qui a quoi, non seulement en fonction des aveux proposés, mais également en fonction des joueurs qui n'ont pas proposé de rejeter une suggestion donnée. Il ne prend pas en compte le nombre de cartes que chaque joueur possède, mais cela doit être corrigé. Il comprend quelques classes assez longues, donc je ne publierai pas tout le code ici, mais la méthode suivante donne une saveur.

public void Suggestion(int suggester, MurderSet suggestion, int? disprover, Card disproof)
{
  List<int> nonDisprovers = NonDisprovers(suggester, disprover).ToList();

  foreach (var player in nonDisprovers)
  {
    m_cardTracker.DoesntHaveAnyOf(player, suggestion);
  }

  if (disprover != null && disproof == null)
  {
    // We know who disproved it but not what they showed.
    Debug.Assert(disprover != m_i, "The disprover should see the disproof");
    Debug.Assert(suggester != m_i, "The suggester should see the disproof");
    m_cardTracker.DoesntHaveAllOf(suggester, suggestion);
    m_cardTracker.HasOneOf((int)disprover, suggestion);
  }

  if (disproof != null)
  {
    // We know who disproved it and what they showed.
    Debug.Assert(disprover != null, "disproof is not null but disprover is null");
    m_cardTracker.DoesHave((int)disprover, disproof.Value);
  }
}

Si les 4 jouent les uns contre les autres, CluePaddle remporte de loin le plus de matchs, avec ClueByFour deuxième et les deux autres nulle part.

Seul CluePaddle est une entrée compétitive (jusqu'à présent). Usage:

CluePaddle.exe identifier port

Si quelqu'un d'autre veut créer une IA C #, créez simplement un projet ConsoleApplication dans la solution, implémentez le IClueAI interface dans une classe, puis de faire Programdériver ProgramTemplateet copier ce que font les autres projets Main(). La seule dépendance est NUnit pour les tests unitaires et vous pouvez facilement supprimer tous les tests du code (mais ne l'installez pas, installez simplement NUnit).