Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Well let's start with the [1]

5 of the 9 squares have negative odds. If you play those your expected value is guaranteed to be negative. One of them has even odds, so barring any positional nuance to evaluating it sooner (of which there is none up front), there is an expected value of 0. So off the bat we have eliminated 66% of the search space by doing just 6 comparisons of odds. In fact, we haven't just solved the first turn. The optimal strategy is invariant to the outcome of the first draws. You will ALWAYS want to play the top row until it's complete, regardless of who gets which slot.

Top left has an odds spread of +35 for the player. Top right has an odds spread of +40. So the right is guaranteed to be a superior choice. We haven't even begun to do any sort of nuanced analysis here and we're down to just two options.

Top middle has a superior odds spread of +50. You would need to run some sort of model to derive the exact positional score of the corner vs. the upper middle for a first guess, but I'll tell you based on strong gut instinct, the middle slot with 10 points better odds is going to be the better choice. You can validate this on the new tutor mode if you want.

Here's the algo I would use:

* Calculate all net odds * If there's positive options, ignore all neutral and negative options. If there's no positives but there are neutrals, ignore all negatives

* If there's any slot that offers you a > 50% chance of winning, play the one that does this with the best odds

* Otherwise add one point per unlocked path, (e.g. 3 on a corner at games start, 2 at the side, or 4 for the center) or stopped path for your opponents

* Pick the highest score (net odds + positional points). Break ties with higher probability or otherwise pick randomly.

A few nuances here: * It'd probably be better to use odds ratio instead of net odds but that's trickier to spout off the top of my head

* Probably underweighting the center by a bit for first choice but simplicity is good

Feel free to this against tutor mode and find a counter example.

The logic typically just gets easier and easier as the game goes on too.



I think it's a good strategy, but it's not the best unbeatable strategy.

In particular, in this example it'better to play top right than top middle.


There's for sure some minor tuning of the positional weights for the first move to be done, but I've looked at the scores of tutor mode for an example that matches the one shown (for a corner and middle equivalent) and the model agrees with me that top middle is superior by 1 p.p.

On average for boards where both positions don't appear in the same board over a few samples, the corner was rated an average of 1 p.p. higher but it's not apples to apples when its across different boards as the scores bake in the weight of first movers advantage. I can't be arsed to test this particular board in the example with manual code.

There's no such thing as an unbeatable strategy. My point is not that the greedy solution is superior at playing the game. My point is that it will perform with very nearly perfect play with more than 1000 times few calculations. With tuning it could very likely achieve provably perfect play.

You could similarly use the logic of this greedy strategy to simply remove obviously incorrect spaces of the dynamic equation to get globally optimal answer with probably > 95% fewer calculations on average.

This kind of greedy vs. slow but globally optimal solutions are super common in real world problems.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: