Speed ​​Clue

Cluedo / Clue é um jogo de tabuleiro clássico com um componente de jogabilidade de dedução atraente. Speed ​​Clue é uma variante de 3-6 jogadores que enfatiza esse componente usando apenas os cartões. O resultado é que a única diferença entre Cluedo padrão e Speed ​​Clue é que cada jogador ainda no jogo pode fazer qualquer sugestão que desejar no seu turno, em vez de esperar para chegar a uma sala específica à mercê dos lançamentos de dados e das sugestões de outros jogadores. Se você nunca jogou Cluedo antes ou deseja ter certeza das diferenças explícitas entre as duas versões, você pode encontrar uma regra completa do Speed ​​Clue definida aqui .

Objetivo

Escreva e envie um programa de IA para jogar o Speed ​​Clue antes de 15 de maio de 2014 às 00:00 GMT. Após esse período, irei realizar um torneio usando todas as entradas legais. O participante cuja IA vencer mais jogos no torneio vence o desafio.

AI Especificações

Você pode escrever sua IA em praticamente qualquer idioma que você escolher, usando as técnicas que você usar, desde que use estritamente o protocolo do aplicativo através de uma conexão TCP / IP para jogar com o servidor. Uma explicação detalhada de todas as restrições pode ser encontrada aqui .

Como jogar

Comece bifurcando o repositório do GitHub do concurso . Adicione um diretório ao entriesdiretório nomeado usando seu nome de usuário StackExchange e desenvolva seu código nessa pasta. Quando estiver pronto para enviar sua inscrição, faça uma solicitação de recebimento com suas revisões e siga estas instruções para anunciar sua entrada neste site.

Eu forneci algum código e JARs no corediretório para você começar; consulte o meu site para obter um guia aproximado dos materiais. Além disso, outros jogadores estão enviando o código auxiliar, além de suas entradas, para ajudá-lo a começar a trabalhar. Reserve um tempo para explorar as entradas e não se esqueça de testar sua entrada com as de outras pessoas antes de enviar!

Resultados

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: ""

Os resultados acima mostram a porcentagem de vitórias que cada IA ​​qualificada teve das 25.200 partidas válidas em que participou. No total, foram 30.000 correspondências que foram contabilizadas para os resultados e 6.100 foram descontadas quando 01desqualificadas.

Uma menção honrosa precisa ir para a 01IA da ray . Meu teste inicial mostrou que era o mais forte, e eu esperava que vencesse a competição. No entanto, parece ter um bug muito intermitente que, até onde posso imaginar, leva a eliminar todas as soluções possíveis. O torneio terminou todas as partidas de três jogadores e começou as partidas de quatro jogadores (12.000 jogos em!) Quando 01o bug foi revelado. Se eu considerar apenas a classificação de 3 jogadores, os resultados serão assim:

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%

Eu tinha planejado fazer uma mineração de dados sobre os resultados, mas estou exausto. Tive dificuldades técnicas para fazer com que a competição continuasse (falhas de energia, reinicializações do sistema), o que exigia reescrever completamente o servidor do concurso para salvar seu progresso à medida que prosseguia. Vou comentar e confirmar todas as alterações no código com todos os arquivos de resultados que foram gerados, caso alguém ainda esteja interessado. Se eu decidir fazer a mineração de dados também, meus resultados também serão adicionados ao repositório.

Obrigado por jogar!

AI01 - Python 3

Ainda não consigo encontrar um nome melhor para ele :-P.

Identificador : ray-ai01

Tecnologia : Python 3

Selecionado : sim

Argumentos :ai01.py identifier port

Descrição : Trabalho por inferência. Quando o número de cartões que o proprietário não é conhecido é menor que um limite, essa IA começa a eliminar todas as soluções impossíveis por inferência global recursiva. Caso contrário, ele usa inferência local.

#!/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)

O código AI pode ser encontrado aqui .

SimpleCluedoPlayer.java

Essa classe usa AbstractCluedoPlayer, que lida com todas as E / S e permite que a lógica funcione com uma interface digitada simples. A coisa toda está no github .

Isso supera o jogador aleatório com alta probabilidade (no pior caso, são necessárias 15 sugestões, enquanto o jogador aleatório leva uma média de 162), mas será facilmente vencido. Eu ofereço para fazer a bola rolar.

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

Identificador: gamecoder-SpockAI

Repo Entry: clique aqui

Selecionado: Sim

Tecnologia: Java 7 baseado emcom.sadakatsu.clue.jar

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

Descrição:

SpockAIé um jogador do Speed ​​Clue, construído sobre uma classe chamada Knowledgeque eu escrevi. A Knowledgeclasse representa todos os estados possíveis que o jogo poderia ter dado o que aconteceu até agora. Ele representa as soluções do jogo e as possíveis mãos dos jogadores como sets e usa deduções iterativas para reduzir esses sets o máximo possível sempre que algo é aprendido. SpockAIusa essa classe para determinar quais sugestões têm os melhores resultados de pior caso e seleciona aleatoriamente uma dessas sugestões. Quando ele precisa refutar uma sugestão, ele tenta mostrar um cartão que já mostrou a IA sugerida ou mostrar um cartão da categoria para a qual reduziu ao mínimo as possibilidades. Só faz uma acusação quando conhece a solução.

A heurística que usei para determinar a melhor sugestão é a seguinte. Após todas as informações terem sido aprendidas com uma sugestão, a solução possível e os conjuntos de mãos possíveis serão reduzidos (a menos que a sugestão não revele informações novas). Teoricamente, a melhor sugestão é a que mais reduz o número de soluções possíveis. No caso de empate, presumo que seja melhor uma sugestão que reduza o número de mãos possíveis para os jogadores. Portanto, para cada sugestão, tento todos os resultados possíveis que não levem a uma contradição no conhecimento. Qualquer resultado que tenha menos melhorias nas contagens de solução / mão é considerado o resultado que a sugestão terá. Depois, comparo os resultados de todas as sugestões e escolho qual delas tem o melhor resultado. Dessa forma, garanto o ganho ideal de informações no pior caso.

Estou pensando em adicionar uma análise de combinação de força bruta de possíveis soluções e possíveis jogadores para tornar SpockAIainda mais forte, mas como SpockAIjá é a entrada mais lenta e com mais recursos, provavelmente ignorarei isso.

Aviso Legal:

Eu pretendia lançar uma IA para este concurso semanas atrás. Tal como está, não pude começar a escrever minha IA até sexta-feira da semana passada e continuei encontrando bugs ridículos no meu código. Por esse motivo, a única maneira SpockAIde trabalhar antes do prazo final era usar um grande pool de threads. O resultado final é que (atualmente) o SpockAI pode atingir + 90% de utilização da CPU e 2 GB + de memória (embora eu culpe o coletor de lixo por isso). Pretendo participar SpockAIdo concurso, mas se outros acharem que isso é uma violação das regras , atribuirei o título de "vencedor" ao segundo lugar que deve SpockAIganhar. Se você se sente assim, por favor, deixe um comentário para esse efeito nesta resposta.

InferencePlayer.java

Código completo no Github (nota: isso usa o mesmo AbstractCluedoPlayerque o anterior SimpleCluedoPlayer).

O verdadeiro núcleo deste player é sua PlayerInformationclasse (aqui um pouco aparada):

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

Ele unifica informações sobre sugestões que o jogador não refutou (indicando que não possuem nenhuma dessas cartas), sugestões que refutaram (indicando que detêm pelo menos uma dessas cartas) e cartões cuja localização é certa. Em seguida, aplica iterativamente algumas regras básicas para compactar essas informações em sua essência.

Acho que não há mais informações determinísticas a serem obtidas (exceto por meio de falsas acusações, que suponho que sejam muito raras de se preocupar), embora eu possa ter esquecido alguma coisa. Lá é possível para um jogador mais sofisticado para probabilidades de estimativa de que o jogador X tem o cartão de Y ...

A outra área que provavelmente admite melhorias significativas é decidir qual sugestão fazer. Tento maximizar o ganho de informações usando uma abordagem de força pesada bastante desajeitada, mas há muita heurística pouco justificada na avaliação dos méritos relativos do conhecimento adquirido com diferentes refutações hipotéticas. No entanto, não vou tentar ajustar as heurísticas até que alguém poste um oponente digno.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

Eu escrevi o ClueBot, um cliente C # para o qual é fácil implementar AIs e várias AIs, incluindo a tentativa mais séria chamada CluePaddle. O código está em https://github.com/jwg4/SpeedClueContest/tree/clue_paddle com uma solicitação pull iniciada para mesclá-lo no upstream.

ClueStick é uma prova de conceito que basicamente apenas adivinha e ignora a maior parte do que acontece. O ClueBat é outra IA estúpida, exceto que ele tenta explorar uma falha no ClueStick para forçá-lo a fazer acusações falsas. O ClueByFour é uma IA razoável, na medida em que faz sugestões razoáveis ​​e lembra os cartões que são mostrados por outros.

CluePaddle é o mais inteligente. Ele tenta descobrir quem tem o quê, com base não apenas nas reprovações que foram oferecidas, mas também nos jogadores que não ofereceram uma reprovação a uma sugestão. Não leva em consideração quantas cartas cada jogador tem, mas isso deve ser corrigido. Ele inclui algumas classes bastante longas, portanto não postarei o código inteiro aqui, mas o método a seguir fornece uma amostra.

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

Se os quatro jogarem um contra o outro, o CluePaddle vence de longe a maioria dos jogos, com o ClueByFour em segundo e os outros dois em lugar nenhum.

Somente CluePaddle é uma entrada competitiva (até agora). Uso:

CluePaddle.exe identifier port

Se alguém mais quiser criar uma IA em C #, basta criar um projeto ConsoleApplication na solução, implementar a IClueAIinterface em uma classe e, então, Programderivar ProgramTemplatee copiar o que os outros projetos fazem Main(). A única dependência é o NUnit para teste de unidade e você pode facilmente remover todos os testes do código (mas não basta, basta instalar o NUnit).