Petunjuk Kecepatan

Cluedo / Clue adalah gim papan klasik dengan komponen gameplay pengurang yang menarik. Speed ​​Clue adalah varian pemain 3-6 yang menekankan komponen ini hanya dengan menggunakan kartu. Hasilnya adalah bahwa satu-satunya perbedaan antara Cluedo standar dan Speed ​​Clue adalah bahwa setiap pemain yang masih berada dalam permainan dapat membuat saran yang diinginkannya pada gilirannya alih-alih menunggu untuk mencapai ruangan tertentu dengan belas kasihan gulungan dadu dan saran pemain lain. Jika Anda belum pernah bermain Cluedo sebelumnya, atau ingin memastikan perbedaan eksplisit antara kedua versi, Anda mungkin menemukan aturan Speed ​​Clue lengkap yang ditetapkan di sini .

Tujuan

Tulis dan kirimkan program AI untuk memainkan Speed ​​Clue sebelum 15 Mei 2014 00:00 GMT. Setelah waktu itu, saya akan menjalankan turnamen menggunakan semua entri legal. Peserta yang AI-nya memenangkan pertandingan terbanyak di turnamen memenangkan tantangan.

Spesifikasi AI

Anda dapat menulis AI Anda dalam hampir semua bahasa yang Anda pilih, menggunakan teknik apa pun yang Anda gunakan, asalkan dengan ketat menggunakan protokol aplikasi melalui koneksi TCP / IP untuk bermain game dengan server. Penjelasan rinci tentang semua batasan dapat ditemukan di sini .

Cara bermain

Mulailah dengan membentuk repositori kontes GitHub . Tambahkan direktori di bawah entriesdirektori bernama menggunakan nama pengguna StackExchange Anda, dan kembangkan kode Anda di folder itu. Ketika Anda siap untuk mengirimkan entri Anda, buat permintaan tarik dengan revisi Anda, kemudian ikuti instruksi ini untuk mengumumkan entri Anda di situs ini.

Saya telah memberikan beberapa kode dan JAR dalam coredirektori untuk membantu Anda memulai; lihat situs saya untuk panduan kasar untuk materi. Selain itu, pemain lain mengirimkan kode pembantu di samping entri mereka untuk membantu Anda bangkit dan berjalan. Luangkan waktu untuk menjelajahi entri, dan jangan lupa untuk menguji entri Anda terhadap entri orang lain sebelum mengirimkan!

Hasil

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

Hasil di atas menunjukkan persentase kemenangan setiap AI yang memenuhi syarat dari 25.200 pertandingan yang valid di mana ia berpartisipasi. Ada total 30.000 pertandingan yang dihitung untuk hasil, dan 6.100 atau lebih yang didiskon ketika 01didiskualifikasi.

Disebutkan terhormat harus pergi ke ray 01AI. Pengujian awal saya menunjukkan bahwa itu yang terkuat, dan saya mengharapkannya memenangkan persaingan. Namun, tampaknya memiliki bug yang sangat intermiten, sejauh yang saya duga, mengarahkannya untuk menghilangkan semua solusi yang mungkin. Turnamen telah menyelesaikan semua pertandingan tiga pemain dan telah memulai empat pertandingan pemain (12.000 pertandingan!) Ketika 01bug terungkap. Jika saya hanya mempertimbangkan peringkat pertandingan 3-pemain, hasilnya terlihat seperti ini:

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%

Saya sudah berencana melakukan beberapa data mining pada hasilnya, tetapi saya kelelahan. Saya mengalami kesulitan teknis dalam membuat kompetisi berjalan sepanjang (kegagalan daya, sistem reboot) yang mengharuskan sepenuhnya menulis ulang server kontes untuk menyimpan kemajuannya saat berjalan. Saya akan berkomentar dan melakukan semua perubahan pada kode dengan semua file hasil yang dihasilkan jika ada yang masih tertarik. Jika saya memutuskan untuk melakukan penambangan data juga, hasil saya juga akan ditambahkan ke repositori.

Terima kasih sudah bermain!

AI01 - Python 3

Saya belum dapat menemukan nama yang lebih baik untuknya :-P.

Identifier : ray-ai01

Teknologi : Python 3

Dipilih : ya

Argumen :ai01.py identifier port

Deskripsi : Bekerja berdasarkan inferensi. Ketika jumlah kartu yang pemiliknya tidak diketahui kurang dari ambang, AI ini mulai menghilangkan semua solusi yang tidak mungkin dengan inferensi global rekursif. Kalau tidak, itu menggunakan inferensi lokal.

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

Kode AI dapat ditemukan di sini .

SimpleCluedoPlayer.java

Kelas ini menggunakan AbstractCluedoPlayer, yang menangani semua I / O dan memungkinkan logika bekerja dengan antarmuka yang diketik sederhana. Semuanya ada di github .

Ini mengalahkan pemain acak dengan probabilitas tinggi (dalam kasus terburuk dibutuhkan 15 saran, sedangkan pemain acak mengambil rata-rata 162), tetapi akan mudah dikalahkan. Saya menawarkannya untuk membuat bola bergulir.

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

Identifier: gamecoder-SpockAI

Entri Repo: klik di sini

Dipilih: Ya

Teknologi: Java 7 berdasarkancom.sadakatsu.clue.jar

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

Deskripsi:

SpockAIadalah pemain Speed ​​Clue yang dibangun di atas kelas Knowledgeyang saya tulis. The Knowledgekelas mewakili semua negara yang mungkin bahwa permainan bisa mengingat apa yang telah terjadi sejauh ini. Ini mewakili solusi permainan dan tangan pemain yang mungkin sebagai set, dan menggunakan deduksi berulang untuk mengurangi set ini sejauh mungkin setiap kali sesuatu dipelajari. SpockAImenggunakan kelas ini untuk menentukan saran mana yang dipastikan memiliki hasil kasus terburuk yang paling membantu dan secara acak memilih salah satu saran tersebut pada gilirannya. Ketika perlu menyangkal saran, ia mencoba menunjukkan kartu yang sudah menunjukkan AI yang menyarankan atau menunjukkannya kartu dari kategori yang paling sedikit mengurangi kemungkinan. Itu hanya membuat tuduhan ketika tahu solusinya.

Heuristik yang saya gunakan untuk menentukan saran terbaik adalah sebagai berikut. Setelah semua informasi telah dipelajari dari suatu saran, solusi yang mungkin dan set hand pemain yang mungkin akan berkurang (kecuali saran itu tidak mengungkapkan informasi baru). Secara teoritis, saran terbaik adalah yang paling mengurangi jumlah solusi yang mungkin. Dalam kasus seri, saya berasumsi bahwa saran yang paling mengurangi jumlah tangan yang mungkin untuk pemain adalah lebih baik. Jadi, untuk setiap saran, saya mencoba setiap hasil yang mungkin yang tidak mengarah pada kontradiksi dalam pengetahuan. Hasil mana pun yang memiliki peningkatan paling sedikit dalam jumlah solusi / tangan diasumsikan sebagai hasil saran tersebut. Lalu saya membandingkan semua hasil saran, dan memilih mana yang memiliki hasil terbaik. Dengan cara ini, saya menjamin perolehan informasi kasus terburuk yang optimal.

Saya sedang mempertimbangkan untuk menambahkan analisis kombinasi brute force dari solusi yang mungkin dan kemungkinan tangan pemain untuk membuat SpockAIlebih kuat, tetapi karena SpockAIsudah menjadi entri paling lambat dan paling intensif sumber daya, saya mungkin akan melewatkan itu.

Penolakan:

Saya berniat untuk merilis AI untuk kontes ini minggu lalu. Seperti berdiri, saya tidak dapat mulai menulis AI saya sampai Jumat pekan lalu, dan saya terus menemukan bug konyol dalam kode saya. Karena itu, satu-satunya cara saya bisa mulai SpockAIbekerja sebelum tenggat waktu adalah menggunakan kolam utas yang besar. Hasil akhirnya adalah bahwa (saat ini) SpockAI dapat menekan + 90% pemanfaatan CPU dan 2GB + penggunaan memori (meskipun saya menyalahkan pengumpul sampah untuk ini). Saya berniat ikut SpockAIdalam kontes, tetapi jika orang lain merasa itu adalah pelanggaran aturan , saya akan menghadiahkan gelar "pemenang" ke tempat kedua yang harus SpockAImenang. Jika Anda merasa seperti ini, silakan tinggalkan komentar untuk efek itu pada jawaban ini.

InferencePlayer.java

Kode lengkap pada Github (catatan: ini menggunakan sama AbstractCluedoPlayerdengan saya sebelumnya SimpleCluedoPlayer).

Inti sebenarnya dari pemain ini adalah PlayerInformationkelasnya (di sini sedikit dipangkas):

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

Ini menyatukan informasi tentang saran yang pemain tidak membuktikan (menunjukkan bahwa mereka tidak memegang kartu-kartu itu), saran yang mereka tolak (menunjukkan bahwa mereka memegang setidaknya satu dari kartu-kartu itu), dan kartu-kartu yang lokasinya pasti. Kemudian secara iteratif menerapkan beberapa aturan dasar untuk memadatkan informasi itu menjadi esensinya.

Saya tidak berpikir ada informasi deterministik lagi yang bisa diperoleh (kecuali dari tuduhan salah, yang saya anggap terlalu jarang untuk diganggu), walaupun saya mungkin telah mengabaikan sesuatu. ada adalah potensi pemain yang lebih canggih untuk probabilitas memperkirakan bahwa pemain X memiliki kartu Y ...

Bidang lain yang mungkin mengakui peningkatan yang signifikan adalah dalam memutuskan saran mana yang akan dibuat. Saya berusaha untuk memaksimalkan perolehan informasi dengan menggunakan pendekatan gaya berat yang cukup kikuk, tetapi ada banyak heuristik yang dibenarkan buruk dalam mengevaluasi manfaat relatif pengetahuan yang diperoleh dari berbagai penolakan hipotesis. Namun, saya tidak akan mencoba menyetel heuristik sampai orang lain memposting lawan yang layak.

CluePaddle (ClueStick / ClueBat / ClueByFour) - C #

Saya telah menulis ClueBot, klien C # yang mudah untuk mengimplementasikan AI, dan berbagai AI, termasuk upaya paling serius yang disebut CluePaddle. Kode ini di https://github.com/jwg4/SpeedClueContest/tree/clue_paddle dengan permintaan tarik mulai untuk menggabungkannya ke hulu.

ClueStick adalah pembuktian konsep yang pada dasarnya hanya menebak dan mengabaikan sebagian besar dari apa yang terjadi. ClueBat adalah AI bodoh lainnya, kecuali bahwa ia mencoba untuk mengeksploitasi kelemahan di ClueStick untuk memaksanya melakukan tuduhan palsu. ClueByFour adalah AI wajar yang membuat saran yang masuk akal dan mengingat kartu yang ditunjukkan oleh orang lain.

CluePaddle adalah yang paling cerdas. Ia mencoba untuk mencari tahu siapa yang memiliki apa yang didasarkan tidak hanya pada apa yang telah ditawarkan oleh penolakan, tetapi juga berdasarkan pada para pemain yang tidak menawarkan penolakan terhadap saran yang diberikan. Tidak memperhitungkan berapa banyak kartu yang dimiliki masing-masing pemain tetapi ini harus diperbaiki. Ini termasuk beberapa kelas yang cukup panjang sehingga saya tidak akan memposting seluruh kode di sini, tetapi metode berikut memberikan rasa.

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

Jika 4 bermain melawan satu sama lain, CluePaddle menang sejauh ini di sebagian besar permainan, dengan ClueByFour kedua dan dua lainnya tidak ada.

Hanya CluePaddle yang merupakan entri kompetitif (sejauh ini). Pemakaian:

CluePaddle.exe identifier port

Jika ada orang lain yang ingin membuat C # AI, buat saja proyek ConsoleApplication di soltution, terapkan IClueAIantarmuka di kelas, dan kemudian buatProgram dari ProgramTemplatedan salin apa yang dilakukan proyek lain Main(). Satu-satunya ketergantungan adalah NUnit untuk pengujian unit dan Anda dapat dengan mudah menghapus semua pengujian dari kode (tetapi jangan, cukup instal NUnit).