4 ms·

I said this on the original thread. You don't need to search the whole space. A greedy solution is fine. Considering a simple score that utilizes the odds of y

I said this on the original thread. You don't need to search the whole space. A greedy solution is fine. Considering a simple score that utilizes the odds of you getting it vs. your opponent, the paths to or immediate victories/losses opened up is nearly guaranteed to give you the optimal strategy every time. If a slot has negative odds, meaning it's more likely to help your opponent, you should NEVER play that slot unless you have no dissimilar options. Many slots, based on position, assume a value of 0 and should be avoided while there's positively valued options available. If a slot has a > 50% chance of handing you the win, you should always play it. (you could argue the model proves this rigidly at the 57% level) 9 calculations are all you need

gus_massa 2y ago
This is not a strategy, it's just an idea that can lead to an strategy. A strategy must give clear rules about which move to play. To make the question more clear, let's analyze the grid in the top of the blog post. I think it's clear for everyone [1] that the first player must play one of the cells on the top row. Which one is the best move left, middel or right? How is this explained by your strategy? [1] citation needed
- spywaregorilla 2y ago
  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.
  - gus_massa 2y ago
    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.
    - spywaregorilla 2y ago
      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.

gus_massa 2y ago

This is not a strategy, it's just an idea that can lead to an strategy. A strategy must give clear rules about which move to play. To make the question more clear, let's analyze the grid in the top of the blog post. I think it's clear for everyone [1] that the first player must play one of the cells on the top row. Which one is the best move left, middel or right? How is this explained by your strategy? [1] citation needed

spywaregorilla 2y ago
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.
- gus_massa 2y ago
  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.
  - spywaregorilla 2y ago
    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.