6
\$\begingroup\$

In this challenge, your bot has landed on an island with the stereotypical knights and knaves. Knights always tell the truth, and knaves always lie. The objective is to find the correct 32 digit hexadecimal string before anyone else, by asking knights and knaves and trying to trick other bots into giving you answers or accepting fake ones.

Knights and Knaves

Every bot will be given an array of 48 people, who are the same for all bots. The bots do not know whether any one person is a knight or knave. Each person is assigned two characters of the 32 digit string. Exactly half of all people are knights, and half are knaves: a knight will always give you the correct characters and their indexes within the result string; a knave, however, will give an incorrect character each time along with the correct index. These incorrect characters will always be the same for any one bot, so a knave is indistinguishable from a knight without outside help or some deductive skills. Every character of the string is known by exactly three people, and no person has the same character twice.

Interacting

In order to find knaves, bots can interact with one another. One bot will request help from another for a specific character of the string, and the second bot can return any character. It is up to the first bot to decide if this character is real or fake, likely by asking for more help and comparing the results.

In order to prevent help-vampire bots, no bot can have more outgoing help requests than twice the number of incoming requests it has answered, plus four.

Bots

Every bot is assigned a random Unique ID (UID) number each round. This number is used to communicate with other bots, and ranges from 0 to one less than the number of bots. It can request help from another bot using the function sendRequest(uid, index), and read from responses with readResponses(), which is formatted as an array/list of objects containing uid, index, and char properties.

Additionally, a bot can view the requests sent to it using viewRequests(). Each request is an object containing two properties: index, and uid. To reply to a request, use the function replyRequest(uid, index, char). There must be a request in viewRequests() from that UID asking about the index specified in order for this to work, and char must be a hexadecimal character.

Both sendRequest and replyRequest will output false if something is invalid (UID for sendRequest, and no request to reply to for replyRequest), and true otherwise.

The bot will receive three arguments as input to its function. The first is an array/list of each knight/knave, with each one represented as an array/list of two objects (index and char are their properties).

The second argument is the number of bots. UIDs range from zero to one less than this number. Finally, the third argument is an empty object, which the bot can use to store any information it needs.

Rules

  • The bot can be programmed in JavaScript (heavily recommended), Python, or any language with functions, strings, numbers, arrays/lists, and objects/dictionaries/hash maps
  • All bots will be converted to JavaScript to be run in the controller
  • A bot may not read or modify any variables outside of its function arguments and local/function scoped variables it creates
  • A bot may not execute any functions declared outside its scope, aside from the four interaction functions (sendRequest, readResponses, viewRequest, and replyRequest)
  • Your bot's guess is submitted by return value. If it does not know, it can return null/false/undefined, or a random guess. Each bot has a win count. If multiple bots guess correctly in the same turn, this increments by 1/correctGuesses
  • Standard Loopholes are prohibited, per the usual
  • Controller, Chatroom
  • By the way, this is not a dupe. The other questions based around knights and knaves have a very different objective, they are just similar in their topic
\$\endgroup\$
  • \$\begingroup\$ So? How do you win? By looking at the controller, it seems bots have to submit guesses using the return value of their run function, but this isn't mentioned in the question. \$\endgroup\$ – Grimy May 20 at 11:34
  • 1
    \$\begingroup\$ @Grimy Oh, just forgot to mention the return value is the guess. It does say "The objective is to find the correct 32 digit hexadecimal string before anyone else", I just forgot to specify how (: \$\endgroup\$ – Redwolf Programs May 20 at 12:29
  • \$\begingroup\$ Okay, but, "before anyone else" how? Is it time based, or number of responses received? Is it valid to answer responses from particular bots and not others? Why would I not return a random response to any request? \$\endgroup\$ – Spitemaster May 20 at 14:07
  • \$\begingroup\$ @Spitemaster Just updated the code and the explanation along with the page \$\endgroup\$ – Redwolf Programs May 20 at 14:40
  • 1
    \$\begingroup\$ Not really. NNN happens about 4 times on average for every new password. So even if we take KNN as more likely (there will be 12 on average) and assume that all NNN are KNN, and assume that NN# isn't masquerading as KK# (1:256 odds) we still have 16 positions with 3 possible values, or 4096 variations, to check before having to give up and assume that all KNN are NNN (because even one of them is enough to make sure that none of those 4096 are the right password). Even if we COULD identify which singular position is NNN and not KNN, that results in 186,535,791 possible passwords. \$\endgroup\$ – Draco18s May 28 at 18:24
1
\$\begingroup\$

Zero Information Bot

function ZeroInformationBot(people, bots, data) {
    if (!data) {
        data = {
            botData: [],
            knaves: [],
            guess: "",
            newKnaves: false,
            attestations: Array(36).fill(0),
            threshold: -5,
        };
    }
    let newResponses = [];
    readResponses().forEach(res => {
        if (!data.botData[res.uid][res.index]){
            newResponses.push(res);
            data.botData[res.uid][res.index] = res.char;
        }
    });
    newResponses.forEach(res => {
        if (people.find(p => (p[0].index == res.index && p[0].char == res.char) || (p[1].index == res.index && p[1].char == res.char))){
            people.forEach((p, i) => {
                if ((p[0].index == res.index && p[0].char == res.char) || (p[1].index == res.index && p[1].char == res.char)) data.attestations[i] += 2;
                if ((p[0].index == res.index && p[0].char != res.char) || (p[1].index == res.index && p[1].char != res.char)) data.attestations[i] -= 1;
                if (data.attestations[i] < -1 && !data.knaves.find(i)) {
                    data.knaves.push(i);
                    data.newKnaves = true;
                }
            });
        }
    });
    viewRequests().forEach(req => {
        if (!data.botData[req.uid]){
            data.botData[req.uid] = Array(36).fill([]);
        } else if (!data.botData[req.uid][req.index]) {
            sendRequest(req.uid, req.index);
            data.botData[req.index] = "-"
        } else if (data.botData[req.uid][req.index] != "-") {
            replyRequest(req.uid, req.index, data.botData[req.uid][req.index]);
        }
    });
    if (!data.newKnaves && data.guess) return data.guess;
    data.newKnaves = false;
    let detected = true;
    let loop = false;
    let possibilities;
    while (detected){
        detected = false;
        possibilities = Array(36).fill(new Set());
        let examined = [], chargroups = [];
        people.forEach((p, i) => {
            if (data.knaves.find(i)) return;
            possibilities[p[0].index].add(p[0].char);
            possibilities[p[1].index].add(p[1].char);
            let first = examined.find(e => e.index == p[0].index && e.char == p[0].char);
            let second = examined.find(e => e.index == p[1].index && e.char == p[1].char);
            if (first && !second){
                chargroups[first.group].push(p[1]);
                examined.push({index: p[1].index, char: p[1].char, group: first.group});
            } else if (!first && second){
                chargroups[second.group].push(p[0]);
                examined.push({index: p[0].index, char: p[0].char, group: second.group});
            } else if (!first && !second){
                examined.push({index: p[0].index, char: p[0].char, group: chargroups.length});
                examined.push({index: p[1].index, char: p[1].char, group: chargroups.length});
                chargroups.push(p);
            } else if (first && second && first.group != second.group){
                chargroups[first.group].push(...chargroups[second.group]);
                examined = examined.map(e => {
                    if (e.group == second.group) e.group = first.group;
                    return e;
                });
                chargroups.splice(second.group, 1);
            }
        });
        possibilities.forEach((p, i) => {
            if (p.size == 1) {
                let char = Array.from(p)[0];
                chargroups.forEach(c => {
                    if (c.find(ch => ch.index == i && ch.char != char)) {
                        people.forEach((person, j) => {
                            if (data.knaves.find(j)) return;
                            // We don't need to check both characters; if one's in the group they both are.
                            if (c.find(ch => ch.index == person[0].index && ch.char == person[0].char)) {
                                data.knaves.push(j);
                                detected = true;
                            }
                        });
                    }
                });
            } else if (p.size == 0) {
                // Uh oh... need to reset.
                data.knaves = [];
                data.attestations.forEach((a, i) => {
                    if (a <= data.threshold) data.knaves.push(i);
                });
                detected = true;
                // Don't get stuck in a loop.
                if (loop) data.threshold--;
                loop = true;
            }
        });
    }
    data.guess = possibilities.map(p => Array.from(p)[0]).join("");
    return data.guess;
}

This bot lets out exactly zero information. Whenever it's asked about something, it responds by first asking what that bot thinks, and then it replies with that data.

It counts up the number of times that other bots have given it one of the values of one of the people, and uses that to give a rough confidence score to each person, tentatively marking someone as a knave if they hit -2. If it hits a paradox, it resets who it's considering as a knave, but only automatically re-marks someone as a knave if they have a score of -5 or worse.

Because this bot doesn't aggressively attempt to solve, it's quite possible it'll get stuck on one or two people for a long time; I'm interested in how well it will do. I haven't tested it yet, as it seems the controller is still (slightly) in flux.

\$\endgroup\$
  • \$\begingroup\$ @Draco18s Thanks, I've fixed those you've pointed out - though the () is unneeded for new Set and var isn't needed (I wasn't trying to make this the cleanest code...). I cleaned those up anyway, though. Also, I'm uncertain why you feel my indentation is inconsistent. \$\endgroup\$ – Spitemaster May 20 at 20:02
  • \$\begingroup\$ Line 102 also throws possibilities not defined because it is declared inside of, but used outside of, the while loop. Line 103 throws guess is not defined (you want data.guess). Additionally, making the same guess with no new information is not a smart strategy. \$\endgroup\$ – Draco18s May 20 at 20:28
  • \$\begingroup\$ Ah, that makes sense. Of course, it's a moot point if there isn't a good resolution of the "no reason to give data" issue. \$\endgroup\$ – Spitemaster May 20 at 20:38
  • \$\begingroup\$ Oh, sure, in the absence of (enough) other bots you'll never gather any information, at which point you just have to make guesses at random. But you may as well make guesses at random. \$\endgroup\$ – Draco18s May 20 at 20:40
  • \$\begingroup\$ Found another issue: chargroups will occasional be smaller than first.group or second.group throwing cannot read property 'push' of undefined on 57, 60, or 67. \$\endgroup\$ – Draco18s May 20 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.