Speed ​​Clue

Cluedo / Clue - классическая настольная игра с неотразимым игровым компонентом. Speed ​​Clue - вариант для 3-6 игроков, который подчеркивает этот компонент, используя только карты. В результате единственное различие между стандартным Cluedo и Speed ​​Clue заключается в том, что каждый игрок, находящийся в игре, может делать любые предложения, которые он пожелает, в свой ход, вместо того, чтобы ждать, пока он не достигнет определенной комнаты, в зависимости от бросков костей и предложений других игроков. Если вы никогда ранее не играли в Cluedo или хотите быть уверены в явных различиях между двумя версиями, вы можете найти здесь полное правило Speed ​​Clue .

Цель

Напишите и отправьте программу AI для игры в Speed ​​Clue до 15 мая 2014 года, 00:00 по Гринвичу. После этого я проведу турнир, используя все легальные записи. Участник, чей ИИ выигрывает большинство игр в турнире, побеждает в соревновании.

AI Технические характеристики

Вы можете написать свой ИИ практически на любом языке, который выберете, используя любые методы, которые используете, при условии, что он строго использует протокол приложения через соединение TCP / IP для игр с сервером. Подробное объяснение всех ограничений можно найти здесь .

Как играть

Начните с разветвления конкурса GitHub . Добавьте каталог в entriesкаталог, названный с использованием вашего имени пользователя StackExchange, и разработайте свой код в этой папке. Когда вы будете готовы подать заявку, сделайте запрос на внесение изменений, а затем следуйте этим инструкциям, чтобы объявить вашу запись на этом сайте.

Я дал некоторый код и JAR-файлы в coreкаталоге, чтобы вы начали; см. мой сайт для приблизительного руководства для материалов. Кроме того, другие игроки отправляют вспомогательный код в дополнение к своим записям, чтобы помочь вам начать работу. Потратьте некоторое время, чтобы изучить записи, и не забудьте проверить свою запись с записями других перед отправкой!

Полученные результаты

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

Приведенные выше результаты показывают процент побед каждого квалифицированного ИИ из 25 200 действительных матчей, в которых он участвовал. Всего было 30 000 матчей, которые учитывались при подсчете результатов, и 6 100 или около того, которые были сброшены со счетов при 01дисквалификации.

Почетное упоминание должно идти к 01ИИ луча . Мое первоначальное тестирование показало, что оно было самым сильным, и я ожидал, что оно выиграет соревнование. Тем не менее, он, кажется, имеет очень неустойчивую ошибку, которая, насколько я могу догадаться, приводит к устранению всех возможных решений. Турнир завершил все матчи с тремя игроками и начал матчи с четырьмя игроками (12 000 игр!), Когда 01была обнаружена ошибка. Если я просто рассмотрим турнирную таблицу с тремя игроками, результаты будут выглядеть так:

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%

Я планировал провести некоторый сбор данных о результатах, но я исчерпан. У меня были технические трудности в том, чтобы заставить соревнование проходить все время (сбои питания, перезагрузка системы), что требовало полной переписывания сервера соревнований, чтобы сохранить его прогресс по мере продвижения. Я прокомментирую и внесу все изменения в код со всеми файлами результатов, которые были сгенерированы на случай, если кто-то все еще заинтересован. Если я решу заняться интеллектуальным анализом данных, мои результаты также будут добавлены в хранилище.

Спасибо за игру!

AI01 - Python 3

Я не могу найти лучшего названия для этого :-P.

Идентификатор : ray-ai01

Технология : Python 3

Избранное : да

Аргументы :ai01.py identifier port

Описание : Работа по умозаключению. Когда количество карт, неизвестных владельцу, меньше порогового значения, этот ИИ начинает устранять все невозможные решения путем рекурсивного глобального вывода. В противном случае он использует локальный вывод.

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

Код AI можно найти здесь .

SimpleCluedoPlayer.java

Этот класс использует AbstractCluedoPlayer, который обрабатывает все операции ввода-вывода и позволяет логике работать с простым типизированным интерфейсом. Все это на GitHub .

Это бьет случайного игрока с высокой вероятностью (в худшем случае это требует 15 предложений, тогда как случайный игрок получает в среднем 162), но его легко победить. Я предлагаю это, чтобы заставить мяч катиться.

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

Идентификатор: gamecoder-SpockAI

Repo Entry: нажмите здесь

Избранное: Да

Технология: Java 7 на основеcom.sadakatsu.clue.jar

Аргументы: {identifier} portNumber [logOutput: true|false]

Описание:

SpockAIэто игрок Speed ​​Clue, созданный на основе класса, Knowledgeкоторый я написал. KnowledgeКласс представляет все возможные состояния , что игра могла бы дать то , что произошло до сих пор. Он представляет игровые решения и возможные комбинации игроков в виде наборов и использует итеративные вычеты, чтобы максимально сократить эти наборы каждый раз, когда что-то узнают. SpockAIиспользует этот класс, чтобы определить, какие предложения гарантируют наиболее полезные результаты в худшем случае, и случайным образом выбирает одно из этих предложений по очереди. Когда ему нужно опровергнуть предложение, он пытается либо показать карту, на которой он уже показал ИИ предложения, либо показать ему карту из категории, для которой у него меньше всего возможностей. Он обвиняет только тогда, когда знает решение.

Эвристика, которую я использовал для определения наилучшего предложения, заключается в следующем. После того, как вся информация была получена из предложения, возможное решение и возможные комбинации рук игрока будут сокращены (если в предложении нет новой информации). Теоретически, лучшее предложение - это то, которое максимально уменьшает количество возможных решений. В случае ничьей, я предполагаю, что предложение, которое больше всего уменьшает количество возможных рук для игроков, лучше. Таким образом, для каждого предложения я пробую все возможные результаты, которые не приводят к противоречию в знаниях. Предполагается, что результат, который будет иметь наименьшее улучшение в подсчете количества решений / рук, будет результатом предложения. Затем я сравниваю результаты всех предложений и выбираю, какой из них имеет лучший результат. Таким образом, я гарантирую оптимальное получение информации в худшем случае.

Я подумываю о том, чтобы добавить общий анализ возможных решений и возможных комбинаций игроков, чтобы сделать его SpockAIеще сильнее, но поскольку SpockAIэто уже самый медленный и наиболее ресурсоемкий вход, я, вероятно, пропущу это.

Отказ от ответственности:

Я собирался выпустить ИИ для этого конкурса несколько недель назад. В нынешнем виде я не смог начать писать свой ИИ до пятницы на прошлой неделе, и я продолжал находить нелепые ошибки в своем коде. Из-за этого единственным способом, которым я смог приступить SpockAIк работе до истечения крайнего срока, было использование большого пула потоков. Конечным результатом является то, что (в настоящее время) SpockAI может достичь + 90% загрузки ЦП и 2 ГБ + использования памяти (хотя я виню сборщик мусора в этом). Я намерен участвовать SpockAIв конкурсе, но если другие считают, что это является нарушением правил , я присваиваю титул «победитель», а второе место должно SpockAIвыиграть. Если вы считаете, что так, оставьте комментарий к этому ответу.

InferencePlayer.java

Полный код на Github (примечание: здесь используется то же, AbstractCluedoPlayerчто и раньше SimpleCluedoPlayer).

Истинное ядро ​​этого игрока - его PlayerInformationкласс (здесь слегка подрезанный):

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

Он объединяет информацию о предложениях, которые игрок не опроверг (указав, что у них нет ни одной из этих карт), предложения, которые он опроверг (указав, что у них есть хотя бы одна из этих карт), и карты, местоположение которых является определенным. Затем он итеративно применяет некоторые базовые правила для уплотнения этой информации в ее сущности.

Я не думаю, что можно получить какую-либо более детерминированную информацию (кроме как с помощью ложных обвинений, которые, я полагаю, слишком редки, чтобы беспокоиться), хотя я, возможно, что-то упустил. Там является потенциал для более сложного игрока , для оценки вероятности того, что игрок X имеет карты Y ...

Другая область, которая, вероятно, допускает значительное улучшение, - это решение, какое предложение сделать. Я пытаюсь максимизировать получение информации, используя довольно неуклюжий подход с применением тяжелой силы, но существует много плохо обоснованных эвристических подходов в оценке относительных достоинств знаний, полученных в результате различных гипотетических опровержений. Тем не менее, я не собираюсь пытаться настраивать эвристику, пока кто-то еще не отправит достойного противника.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

Я написал ClueBot, клиент C #, для которого легко реализовать AI и различные AI, включая самую серьезную попытку под названием CluePaddle. Код находится по адресу https://github.com/jwg4/SpeedClueContest/tree/clue_paddle, и стартовый запрос начал объединять его с апстримом.

ClueStick является проверкой концепции, которая в основном просто угадывает и игнорирует большую часть того, что происходит. ClueBat - еще один глупый ИИ, за исключением того, что он пытается использовать недостаток в ClueStick, чтобы заставить его делать ложные обвинения. ClueByFour - разумный ИИ, в котором он делает разумные предложения и запоминает карты, которые ему показывают другие.

CluePaddle является самым умным. Он пытается выяснить, кто имеет, что основано не только на том, какие опровержения были предложены, но также и на основании того, какие игроки не предложили опровержение данного предложения. Он не учитывает, сколько карт у каждого игрока, но это нужно исправить. Он включает в себя пару довольно длинных классов, поэтому я не буду публиковать здесь весь код, но следующий метод дает представление.

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

Если 4 играют друг против друга, CluePaddle выигрывает, безусловно, в большинстве игр, причем ClueByFour второй, а две другие нигде.

Только CluePaddle является конкурентной записью (пока). Использование:

CluePaddle.exe identifier port

Если кто-то еще хочет создать C # AI, просто создайте проект ConsoleApplication в решении, реализуйте IClueAIинтерфейс в классе, а затем сделайте свой Programнаследник ProgramTemplateи скопируйте то, что делают другие проекты Main(). Единственная зависимость - это NUnit для модульного тестирования, и вы можете легко удалить все тесты из кода (но не устанавливайте NUnit).