you could apply a binary search for each slider and improve the number of tries by moving the slider by half of the shortest distance to the edge

Poor man's attempt:

        var speed = 50
        // Prime the result output
        for (col of [rin, bin, gin]) {
          rin.valueAsNumber = 0
          bin.valueAsNumber = 0
          gin.valueAsNumber = 0
        }
        rin.dispatchEvent(new Event('change'));

        async function tryit(col, incr) {
          // Increment a single color
          col.valueAsNumber = col.valueAsNumber + incr
          col.dispatchEvent(new Event('change'));
          submit.click()
          await (new Promise(resolve => setTimeout(resolve, speed)));
          var res_text = result.innerText.split(/[ ()%]/)[4]
          if (res_text === "Splendid!") {
            throw new Error("Finished")
          }
          return (parseInt(res_text))
        }

        async function trymany() {
          // We need to iterate at least twice due to rounding
          // in result percentage, sometimes making neighbouring 
          // colors have the same result. 
          var last_res = 0, max_tries = 3;
          while (--max_tries > 0) {
            for (col of [rin, gin, bin]) {
              while (true) {
                var new_res = await tryit(col, 1)
                if (last_res >= new_res) {
                  // set last value and break
                  await tryit(col, -1)
                  break
                }
                last_res = new_res
              }
            }
          }
        }
        await trymany()

Not bad, 18 to 43 attempts on 10 games I tried. Far from optimal but good enough :p

I had an updated version which implemented a binary search, but I couldn't update my previous comment so I dropped it. That being said, due to the scoring function `score(r,g,b,rr,gg,bb)` giving the exact same score sometimes for neighbouring colors, the search would still have to repeat and wasn't much more optimal than the code you see above.

how do you run this?

I imagine pasting into the JS console after inspecting the page?

nvm thought it was bugged. user issue not code

Optimized with binary search (can't figure out why ycomb formats my code all ugly)

var speed = 500;

[rin, bin, gin].forEach(col => { col.valueAsNumber = 7; col.dispatchEvent(new Event('change')); col.score = 0; });

async function tryit(col, value) { col.valueAsNumber = value; col.dispatchEvent(new Event('change')); submit.click(); await new Promise(resolve => setTimeout(resolve, speed)); var res_text = result.innerText.split(/[ ()%]/)[4]; if (res_text === "Splendid!") { throw new Error("Finished - Found correct combination"); } col.score = parseInt(res_text); return col.score; }

async function binarySearch(col) { let start = 0; let end = 15; let mid = 7; let startAccuracy = await tryit(col, start); let endAccuracy = await tryit(col, end); let midAccuracy = 0;

    while (true) {
        mid = Math.floor((start + end) / 2);
        midAccuracy = await tryit(col, mid);

        if ((end - start) <= 2) {
            const max = Math.max([startAccuracy, midAccuracy, endAccuracy]);
            if (startAccuracy == max) await tryit(col, start);
            else if (midAccuracy == max) await tryit(col, mid);
            else await tryit(col, end);
            return;
        }

        if (endAccuracy > startAccuracy) {
            start = mid;
            startAccuracy = midAccuracy;
        } else {
            end = mid;
            endAccuracy = midAccuracy;
        }
    }

} async function findOptimalCombination() { for (const col of [rin, gin, bin]) { await binarySearch(col); } /* rounding */ for (const col of [rin, gin, bin]) { const mid = col.valueAsNumber; const score = await tryit(col, mid); const left = await tryit(col, mid - 1); if (score >= left) { const right = await tryit(col, mid + 1); if (score >= right) await tryit(col, mid); } } console.log("Optimization complete"); }

await findOptimalCombination();

This is great -- it has a very consistent performance of ~20 steps. I notice that my naive attempt seems to be faster in some cases.

If we ignore the information contained in the score numbers, only comparing which score is higher, we could optimize using ternary search (or golden-section search). https://en.wikipedia.org/wiki/Golden-section_search

(Note that binary search does not apply here. This is searching for an extremum, not a zero point.)

    - Start at the range of 0-F, measure the score of 6 and 9 (2 tries)
    - Depending on which is higher, narrow the range to 0-9 or 6-F
    - Suppose the range is 0-9, measure the score of 3 and 6 (1 try. 6 is already measured)
    - Narrow the range to 0-6 or 3-9
    - Suppose the range is 0-6, measure the score of 2 and 3 (1 try. 3 is already measured)
    - The worse case is 3's score is higher. The range is now 2-6. Since 2, 3, 6 are all measured, in the worst case you need 2 more tries for 4 and 5.
    - The other case is 2's score is higher. The range is now 0-3 and 0, 2, 3 are all measured.

So in worst case there are 6 tries per slider. ~5 tries on average. I suspect this can be further optimized but I'll stop here :)

Assuming the score is 100-Euclidean distance, you should be able to triangulate to the correct answer after three random guesses. Triangulation will give you two candidates for the correct colour, so if you choose between them randomly you should get the correct colour in 4.5 tries on average.

Because the space is bounded and discrete, you can further optimize by triangulating smartly. If you always pick a triangulation point on the boundary, you will always end up with a single candidate as the other candidate will be out of bounds. (Due to discreteness, you can only pick a point near the boundary, but this will still work in a vast majority of cases.) That reduces the average to ~4.

The score is floor(100*(1-distance/max_distance)) where max_distance is the greatest distance to the target from any point in the cube. This means that the spheres used in triangulation look funny. Rounding also gets in the way, but you can do it in 5 guesses starting with #B74, #448, #B8B and #4B7 (the first 3 are enough in to uniquely identify it in 3911 out of 4096 cases, and the first 2 are enough in 735; giving an average of less than 4 tries).

Excellent work!

We can also probably prove that 3 guesses are not enough by some sort of adversarial argument. That is, instead of having the color be fixed at the start, imagine that the game picks the colors adversarially to try to make the job of the guesser as difficult as possible, while remaining consistent with the answers it has already given. If we can pick a function for the adversary that does not fully disambiguate the color completely for any sequence of three guesses, we will be done.

I wouldn't be surprised if there is a way of doing it in 4 guesses (3 to identify and a 4th that's known to be right), although you probably need to adjust the later guesses based on the results of the first. It wouldn't be impossible to search the space of strategies exhaustively. Precomputing the score function (and storing it as 4096*101 4096-bit bitstrings for efficient set intersection) would speed things up, and it could be a chance to use the 3D texture handling features of a GPU (I've done very little GPU programming so take my enthusiasm with a pinch of salt).

There's a way to do it in 4 guesses, I described it here: https://news.ycombinator.com/item?id=39888130

I meant 3 tries in total, not just the random guesses.

I just tried this and it took 12 goes to get "12) #02C (Splendid!)". Admittedly the target colour was very blueish, so I started with the blue slider and then added a couple of green clicks.

It's calculating distance in 3D space, scaled by the longest distance available. Without the scaling (and ignoring the rounding for the moment), distances from the target to any 3 non-collinear points would narrow it down to at most 2 options, regardless of the precision required on each axis; giving a 50% chance to get it on guess 3 and a 50% chance to get it on guess 4.

With the scaling, it can still be thought of as a problem of intersecting spheres, but the spheres begin to look quite strange since the distance function isn't symmetric. For example if your first guess was a corner of the cube, 1/8 of the space would have the same score (0%) since you've picked the furthest available point. This probably could be analyzed in the same way as above, since the 'spheres' centered at non-corner points aren't degenerate, and their intersections probably still have the right topological dimensions (dropping by 1 each time you add a new sphere, so 3 spheres are still likely to take you to a finite set of points in the continuous case) but that would require some work to prove.

Since we still need to consider the loss of precision from rounding, we can just look at this as a discrete problem and try to find a tuple of points that are sufficient to distinguish everything. It took a me couple of attempts, but the following 4 tetrahedrally arranged ones work: [11,7,4],[4,4,8],[11,8,11],[4,11,7].

There might be a smaller set that work, it would take ~2^48 work to exhaustively search for 3 points that could distinguish everything, and it might be possible to do better since you can choose the second point based on results from the first.

So after calculating the 4 scores for [11,7,4],[4,4,8],[11,8,11],[4,11,7] we can put the 4 scores into a formula and it outputs the correct 3 values? Which formula would that be?

I didn't have a formula, just a Javascript object with 4096 keys. You could try to use a formula, but the rounding would make it quite blurry, so an "exact" answer wouldn't necessarily be right.

Here's the code to generate the object and check that it works: https://gist.github.com/penteract/8957d7d18a60f021d8d74ef2f4...

This is beautiful! Simple and effective.

Could you binary search on the slider to find the optimum?

Here's a solution with ~3.27 average tries total (including the last guess). It works by spreading the possibilities across each of the 100 "score" buckets as evenly as possible (aka minimizing the variance).

It can identify more than half of all colors in just 2 guesses. If you edit the code to minimize the size of the largest bucket instead, you get an algorithm that has a slightly worse average case, but never needs more than 4 guesses.

Paste it in the site's browser console to try.

    function solve() {
      let possibleTargets = new Array(0x1000).fill(0).map((_, i) => i);
      while (true) {
        // for each possible guess, calculate the score-buckets
        const guessResults = possibleTargets.map((guess) => {  // for better brute-force, iterate through all colors, but this performs better (probably because we don't reward for guessing correctly in the current turn)
          const buckets = new Array(101).fill(0).map(() => []);
          for (const possibleTarget of possibleTargets) {
            buckets[calcScore(possibleTarget, guess)].push(possibleTarget);
          }
          return { guess, buckets };
        });

        // find guess with lowest variance
        const best = guessResults.sort((a, b) => calcVariance(a.buckets) - calcVariance(b.buckets))[0];

        // make the guess & update possible targets
        const sc = makeGuess(best.guess);
        if (sc >= 100) return "Success!";
        possibleTargets = best.buckets[sc];
      }
    }

    function calcVariance(buckets) { const maxBucketSize = Math.max(...buckets.map(b => b.length)); return buckets.reduce((acc, b) => acc + (b.length - maxBucketSize) ** 2, 0); }

    function deconstruct(color) { return [(color & 0xF00) >> 8, (color & 0x0F0) >> 4, (color & 0x00F)]; }

    function calcScore(target, guess) { return score(...deconstruct(target), ...deconstruct(guess)); }

    function makeGuess(guess) { [rr, gg, bb] = deconstruct(guess); submitInput(); return score(r, g, b, rr, gg, bb); };

    solve();

That's great. What's the first guess? And does this prove that there is no way of identifying the answer in 2 guesses? I tried running a version of your code across all targets, but my current machine isn't up to it (and there are obviously more efficient ways that you've probably implemented).

I'd like to try out a few alternatives in place of your variance function. Something like b.length*log(b.length) to estimate the expected number of guesses, and perhaps using a version of log closer to ceil(log(x)/log(100)).

You can do 2 guesses if you get lucky. If you want to assume worst possible luck you can't even do it in 3, you need 4.

The first color is #015.

Regarding computing it for all targets, I optimized it by precomputing the value of guessResults in the first iteration, since it's always the same (no matter the target color), which saves most of the computation. I removed the optimization so the code wouldn't be so long here.

Binary search on each channel is the optimal general solution without starting from an educated guess on the first try. This is how a successive approximation ADC performs a conversion.

You can do a lot better than binary search because you get a weighted score for each guess.

What is this next best option called? A weighted binary search?

You should be able to use BFGS to search for the optimal vector [r, g, b] [1]. BFGS estimates the hessian, and then takes a step in the right direction, so you don’t need any derivatives (the score should be enough).

[1] https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80...