5 ms·
I wonder what the optimal strategy would be if you can't see the color and only the answers when you click submit. Hillclimbing is already somewhat efficient:
by mg 3y ago
I wonder what the optimal strategy would be if you can't see the color and only the answers when you click submit.
Hillclimbing is already somewhat efficient:
For each slider:
- Start at 0
- Move to the right until the score drops
- Move one to the left
That should result in something like 9 tries per slider on average, so 27 tries per color.
One signal that could be used to improve it: The difference in score between 0 to 1 gives you the approximate length you have to move to the right.
Due to rounding, you don't get the exact length.
So My guess is that with an optimal strategy, on average you would need something like 4 tries per slider.
That comes down to and average of 12 tries per color.
- elsombrero 3y agoyou 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
- tetris11 3y agoPoor 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()
- js4ever 3y agoNot bad, 18 to 43 attempts on 10 games I tried. Far from optimal but good enough :p
- tetris11 3y agoI 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.
- sleepingreset 3y agohow do you run this?
- andy_ppp 3y agoI imagine pasting into the JS console after inspecting the page?
- sleepingreset 3y agonvm thought it was bugged. user issue not code
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- sunnynagam 3y agoOptimized 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();
- SmartHypercube 3y agoIf 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 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 :)
- alex_smart 3y agoAssuming 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.
- n2d4 3y agoBecause 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.
- penteract 3y agoThe 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).
- alex_smart 3y agoExcellent 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.
- penteract 3y agoI 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).
- KineticLensman 3y agoI 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.
- penteract 3y agoIt'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.
- mg 3y agoSo 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?
- nvader 3y agoCould you binary search on the slider to find the optimum?
- n2d4 3y agoHere'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();
- penteract 3y agoThat'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)).
- kevin_thibedeau 3y agoBinary 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.
- Taek 3y agoYou can do a lot better than binary search because you get a weighted score for each guess.
- saintradon 3y agoWhat is this next best option called? A weighted binary search?
- pinkmuffinere 3y agoYou 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%93Goldfarb%E2%80%93Shanno_algorithm?wprov=sfti1 https://en.wikipedia.org/wiki/Broyden%E2%80%93Fletcher%E2%80...