detect ties

[simondorfman]

Here is a transcript for a game that looks like orange wins, but it is in fact a tie: N26 S10 G N39 S25 G S22 S06 G N31 N30 G N30+ S28 G S18 N31 G

Why is it a tie? Because after the last growth phase, both blue and orange achieve a winning path. Blue's winning path is: N26 N27 N28 N29 N30 N31 N32 S22 S23 S24 S25 S26

When both colors achieve a winning path at the same time, I'd like the following things to happen:

1. the GUI to highlight both winning paths and
2. tournament results to show "Draw" in the Winner column

3. tournament results to show Blue's-winning-path, Orange's-winning-path, in the Winning Path column e.g. N26 N27 N28 N29 N30 N31 N32 S22 S23 S24 S25 S26, N20 N39 N38 S28 S27 S11 S10 S02 S01 S07 S06 S20

   

Player One	Player Two	Winner	Termination	Total Moves	Total Milliseconds	Starting Tile Index	Transcript	Winning Path
Monte Carlo Tree Search	Parallel MCTS	Tie	Normal	39	152276	1	N26 S10 G N39 S25 G S22 S06 G N31 N30 G N30+ S28 G S18 N31 G	N26 N27 N28 N29 N30 N31 N32 S22 S23 S24 S25 S26 , N20 N39 N38 S28 S27 S11 S10 S02 S01 S07 S06 S20

Sidenote: Why do I want this feature?:

Ultimately, I want to update the rules so that ties don't happen. But for now, I want see when they are happening. Then I can run many game simulations again to help me figure out what to do next.

One idea: if there is any 1st- or 2nd-player advantage detected, perhaps I would update the rules to always award ties to the player that has a disadvantage, hoping to even out the game.

[skotz]

This change will impact engines (tie avoidance), tournament results (half points for ties), and the interface (path highlighting).

[simondorfman]

Hmmm, I wonder if we should try implementing a rule fix idea right away. Would this be hard to implement?:

When a tie would happen, if it’s during a growth between blue's turns, that means blue wins.

And if it’s a growth between orange's turns, that means orange wins.

[simondorfman]

I'm working on a different way to approach this problem: change the win condition such that it's impossible for ties to happen.

Instead of just connecting the antipodes, you have to connect the antipodes and go all the way "around the world". What does "around the world" mean? I'm not sure how to describe it with words (which is bad because that means explaining the rules will be difficult), but I can explain it with examples:

Example 1: N25-S25 would also need to go through either N30 or S40, and go through either N40 or S30. Like this:

Example 2: N22-S22 would also need to go through either N27 or S37, and go through either N37 or S27. Like this:

I'm not sure if this would make it too hard to win, or cause games to potentially last forever, but I'd like to try it.

To help players see this win condition, when you mouse-over a tile, I'd like to expand the highlight to show these new around-the-world tiles too, like this:

I was thinking the yellow color would communicate that you need to go to one of those two tiles. I thought this color might work for the yellow: dbd800

[skotz]

How do you implement the rules such that this isn't a win or a tie?

[skotz]

Probably have to use a pathfinding algorithm to find a path from any tile back to itself, without traversing any tile twice, and traversing the yellow and antipode tiles. That could slow down calculations a lot if not implemented correctly, especially for engines.

[simondorfman]

Good question. Maybe implement it by breaking it into 4 separate tests?

Like this:

[simondorfman]

My hope is that these around-the-world rules will make ties impossible. But your good questions are making me doubt myself. Testing the 4 segments seems like a flawed idea too because how do you make sure each test isn't using tiles from another test, which could result in your example, which looks like a tie? Hmmm.

[simondorfman]

How do you implement the rules such that this isn't a win or a tie?

Thinking about this more, I know the answer to this question now. The blue line is missing the connection from N25 to S30 or N40.

I'm feeling more confident about this around-the-world idea resulting in ties not being possible.

[simondorfman]

After talking through some ideas about how to implement this with my brother, he pointed out that I'm missing some yellow tiles. Here's an updated image with the missing yellow tiles added:

The algorithm to get the yellow tiles is to go 5 tiles in a straight line from the antipodes, in each of the 3 direction.

I was trying to think of a good name for these yellow tiles, so I started googling things like "what is the circle called between two antipodes". I eventually figured out that they could be called "antipodal great circle" or "antipodal orthodrome". I like the latter better. (Maybe just Orthodrome tiles for short?)

So I've got an updated rule idea here and an updated algorithm idea:

Rule: To win the game, you need a path that passes through two antipodes and two antipodes on the antipodal orthodrome.

Algorithm, you win if:

1. Path passes through antipodes (e.g. N25-S25) -and-
2. Path passes through a pair of antipodes on the antipodal orthodrom (e.g. N30-S30, N14-S14, N04-S04, N19-S19, or N40-S40)

Does this algorithm seem workable? Not too hard to program, and hopefully wouldn't slow things down too much for the engines?

Lastly, here's how I'd try to explain this new rule in plain terms that most humans would understand (hopefully):

To win the game, you need to build a path around the world. Here's how you think through this:

• Pick a tile on the board. Imagine it's the North Pole. (hover over it with your mouse, see a red outline)
• Now imagine the opposite tile is the South Pole. (the tile with the green outline)
• Now imagine there's an equator between your South Pole and North Pole tiles. (the tiles with the yellow outline)
• To win, you have to connect the North Pole to the South Pole, and you have to connect two opposite tiles on the equator.

[simondorfman]

Shucks, I'm just realizing the algorithm described above would declare a win at 75% complete, not connecting the last 25% connection. I don't know how to fix that, any ideas? Here's a picture to help illustrate:

Blue connections are there, but the red connection is missing. Algorithm still thinks it's a win.

[skotz]

I'm thinking the idea I had above would work with an algorithm to find a path from a tile back to itself, that passes through all required tiles, and doesn't repeat any tiles. Although, if the example you have were expanded to be two tiles high maybe even that would fail. Basically you want the line to completely cut the 3D object in two.

[simondorfman]

Yes, I think you're right, expanding to be two tiles high would make that algorithm fail.

Yes, basically the line needs to completely cut the 3D object in two.

How about this idea?:

Not sure how to write it as an algorithm yet, but an example: Perform 4 tests, each test can't use any of the tiles used in the other tests (except the antipode tiles and orthodrome tiles)

1. test that N25 connects to S40
2. test that S40 connects to S25
3. test that S25 connects to N40
4. test that N40 connects to N25

[simondorfman]

And perform those 4 tests 5 separate times, once with each of the 5 sets of antipodes in the antipodal orthodrome.

These 5 sets (for this example testing N25-S25):

1. N40-S40
2. N30-S30
3. N19-S19
4. N14-S14
5. N04-S04

[skotz]

What about this?

It's almost like the chain must be composed only of antipode pairs, but that limits the number of possible winning paths.

[simondorfman]

Yeah, you're right, those examples follow my algorithm idea, but totally don't follow the spirit of what I'm trying to do. Hmmm...

[simondorfman]

Debating myself, maybe those winning paths you constructed are ok after all. I wonder if it's possible for ties to occur with that path for one player. I hope not, but will try to break that assumption.

Sidenote: is there some volcano.json settings you're using to test out clicking around like that? Or did you make those is some image editor like photoshop?

[simondorfman]

What about this?

Wait, this actually fails my proposed algorithm because the 4th test (N40 connects to N25) fails the "each test can't use any of the tiles used in the other tests" part.

Restating my proposed algorithm example:

Perform 4 tests, each test can't use any of the tiles used in the other tests (except the antipode tiles and orthodrome tiles)

1. test that N25 connects to S40
2. test that S40 connects to S25
3. test that S25 connects to N40
4. test that N40 connects to N25

And perform those 4 tests 5 separate times, once with each of the 5 sets of antipodes in the antipodal orthodrome.

These 5 sets (for this example testing N25-S25):

1. N40-S40
2. N30-S30
3. N19-S19
4. N14-S14
5. N04-S04

[simondorfman]

I made an image to try to make it more clear how some tiles can only be used for each of the 4 tests:

[skotz]

But isn't it still satisfied if you instead make the purple path run parallel to the other paths like in my example? Which specific rule invalidates my test above?

[simondorfman]

Yes, you're right. I finally get it. Hmmm, I'll think about this more...

[simondorfman]

Now I'm trying to answer this question: does the rule-test algorithm being discussed prevent ties from happening? Even with that weird purple tiles wrap-around thing, does it make ties impossible?

So far, it seems like the answer is: yes, yes it does make ties impossible.

Here's an example of me trying to find a tie path for the second player. It passes the test for the first three segments:

1. S8-S17
2. S17-N8
3. N8-N17

...but fails with the fourth segment:

4. N17-S8

There's no way to connect N17 to S8 without reusing some of the tiles already used for the 3rd test (N8-N17).

So this seems promising for solving the original problem of ties being possible. But, at what cost?

Will the game be much harder to grok? I imagine it will be.

Maybe this could/would/should be a next-level version of the game. Once a player gets good at connecting just antipodes, then they try this around-the-world version.

But if around-the-world becomes a "more experienced player" version of the game. Then a different solution for stopping ties is required for the original antipode-only game.

I think my best idea for that so far, is the one stated above somewhere as a quick-fix idea:

1. ties that happen during the growth between blue's turns means blue wins
2. and ties that happen during the growth between orange's turns means orange wins.

On the other hand, maybe the around-the-world version of the game will be great. So great that I think the antipode-only version of the game should be scrapped.

After sitting with it for a while, I'm still excited about trying the around-the-world version. So if I can convince you to code it, Scott, then let's do it. If you're not feeling it, maybe I'll roll up my sleeves and try to learn enough C# to get it working myself. But we all know that will be some ugly code that you don't want to see. :) So I hope I've convinced you this is worth doing.

[skotz]

Doesn't my example above demonstrate a tie?

[simondorfman]

Holy cow, sorry I'm so slow. I was thinking that was two different examples. Now I see what you mean. Yes, I see this doesn't stop ties. Ok, will ponder this further.

[simondorfman]

Well, I'm no longer enamored by the around-the-world idea. Besides the fact that it doesn't stop ties, it will:

1. ...make the game harder to understand.
2. ...make the game longer (I like how short the game is currently, so this is a negative, in my mind).
3. ...make the game feel more rigid and constrained (at least I think it will).

Yeah, it's bad. It took me a while, but I finally see it.

So back to the problem of eliminating ties. Here are my ideas so far, ordered by best-ideas-at-the-top-descending-to-worst-ideas-at-the-bottom order:

1. After doing more testing, if there's 1st- or 2nd-player advantage, minimize that advantage by giving ties to the disadvantaged player.
2. Growth between blue's turns means blue wins, and growth between orange's turns means orange wins.
3. Change growth so that it doesn't happen at the same time for everyone. Maybe take turns executing growth, one volcano at a time or something.

Idea 1 needs more data. So I think we should add a column to the tournament output like this:	WinCondition
TieOnGrowthBetweenWinnersTurns
NormalWin

But it may be that there isn't any 1st- or 2nd-player advantage. So I think we should also implement idea 2: Growth between blue's turns means blue wins, and growth between orange's turns means orange wins.

What do you think?

[simondorfman]

I was thinking: how can I simplify the fix such that I could code it myself? Maybe just detecting ties is enough. And maybe I could figure that out. Maybe the only part that would need to change is this function: https://github.com/skotz/volcanoes/blob/master/Volcanoes/Game/Board.cs#L244

        private void SearchForWin()
        {
            // We only need to cover the first 40 tiles since their antipodes cover the last 40
            for (int i = 0; i < 40; i++)
            {
                if (Tiles[i] != 0 && 
                    ((Tiles[Constants.Antipodes[i]] > 0 && Tiles[i] > 0) || (Tiles[Constants.Antipodes[i]] < 0 && Tiles[i] < 0)) && 
                    Math.Abs(Tiles[i]) > VolcanoGame.Settings.MaxMagmaChamberLevel && 
                    Math.Abs(Tiles[Constants.Antipodes[i]]) > VolcanoGame.Settings.MaxMagmaChamberLevel)
                {
                    List<int> path = pathFinder.FindPath(this, i, Constants.Antipodes[i]).Path;
                    if (path.Count > 0)
                    {
                        Winner = Tiles[i] > 0 ? Player.One : Player.Two;
                        WinningPath = path;
                        return;
                    }
                }
            }
        }

I think the changed needed would be something like this:

If a winning path is found:

1. remember which player won (variable: Winner) and remember the winning path that was just found (variable: WinningPath)
2. but continue the search for winning paths
3. If a winning path is found for the other player:
   1. update variable Winner to 'Tie'
   2. update variable WinningPath to a list of both winning paths

I guess a second code change would be needed, but I'm not sure where. Maybe in this spot?: https://github.com/skotz/volcanoes/blob/master/Volcanoes/Game/Board.cs#L109

            if (Winner == Player.Empty && checkForWin)
            {
                SearchForWin();
            }

The change would be something like this: If the length of list WinningPath = 2, then highlight both winning paths

Does this approach sound about right, @skotz ?

[skotz]

The issue is that those properties are referenced in over 30 locations, so you'll have to individually figure out how to handle ties in each of those places (e.g., tournaments, UI highlighting, scoring, AI searching, etc).

[simondorfman]

Ok, that makes me think it would be easier to implement the best tie-breaker idea I had so far: Growth between blue's turns means blue wins, and growth between orange's turns means orange wins.

Perhaps implementing that would just mean updating the one SearchForWin function?

[simondorfman]

My brother was helping me and I made some progress:

        //goal: update below function: if win condition is found, check to see if other player also wins
        //if other player wins also, award the win to the player who just took a turn
        private void SearchForWin()
        {
            int TentativeWinner = 0;
            List<int> PathTentativeWinner;
            // We only need to cover the first 40 tiles since their antipodes cover the last 40
            for (int i = 0; i < 40; i++)
            {
                if (Tiles[i] != 0 && 
                    ((Tiles[Constants.Antipodes[i]] > 0 && Tiles[i] > 0) || (Tiles[Constants.Antipodes[i]] < 0 && Tiles[i] < 0)) && 
                    Math.Abs(Tiles[i]) > VolcanoGame.Settings.MaxMagmaChamberLevel && 
                    Math.Abs(Tiles[Constants.Antipodes[i]]) > VolcanoGame.Settings.MaxMagmaChamberLevel)
                {
                    List<int> path = pathFinder.FindPath(this, i, Constants.Antipodes[i]).Path;
                    if (path.Count > 0)
                    {
                        if (TentativeWinner == 0)
                        {
                            TentativeWinner = Tiles[i] > 0 ? 1 : -1;
                            PathTentativeWinner = path;
                        }
                        else if (TentativeWinner == 1)
                        {
                            TentativeWinner = Tiles[i] < 0 ? 2 : 1; //2 means check which player just took a turn and make them the winner 
                            //set Winner
                            //set WinningPath
                                //if player 1 just took a turn, WinningPath = PathTentativeWinner
                                //if player 2 just took a turn, WinningPath = path
                            return;
                        }
                        else if (TentativeWinner == - 1)
                        {
                            TentativeWinner = Tiles[i] > 0 ? 2 : -1; //2 means check which player just took a turn and make them the winner
                            //set Winner
                            //set WinningPath
                                //if player 1 just took a turn, WinningPath = path
                                //if player 2 just took a turn, WinningPath = PathTentativeWinner
                            return;
                        }
                        //Winner = Tiles[i] > 0 ? Player.One : Player.Two;
                        //WinningPath = path;
                        //return;
                    }
                }
            }
        }

[simondorfman]

Todo: add if statement to only use the new code being developed above on growth turns. On other turns, use the existing code. Why? A tie can only happen on a growth turn.

[simondorfman]

Check out the pull request here: https://github.com/skotz/volcanoes/pull/50

The test case game from the beginning of this thread (N26 S10 G N39 S25 G S22 S06 G N31 N30 G N30+ S28 G S18 N31 G) now show player one (blue) as the winner.

Remaining todos:

1. find an opposite test case game where it shows player two (orange) is the winner after this code change
2. keep running tournaments until I actually get a "TieOnGrowthBetweenWinnersTurns" result. (sidenote: I'm less confident about the tournament code change. I used the code from winningPath as a template. But I don't fully understand it. Especially the result part: i.e. result.WinningPath.)
3. to make things run faster, add an if statement to only use the new code on growth turns. On other turns, use the existing code. Why? A tie can only happen on a growth turn.

[simondorfman]

regarding todo number 2: I've run many simulations and still haven't gotten a "TieOnGrowthBetweenWinnersTurns" in the results CSV file. Maybe it just doesn't happen very often. Or maybe there's a problem with my code. @skotz could you please take a look at the tournament changes in the pull request (https://github.com/skotz/volcanoes/pull/50) and see if there's anything obvious that I'm missing?

One idea for how to test the tournament code: write an AI that plays itself and chooses its moves from this game sequence so we will know it results in a game where the tiebreaker rule is invoked: N26 S10 G N39 S25 G S22 S06 G N31 N30 G N30+ S28 G S18 N31 G

regarding todo number 1: I was hoping simulations would give me another example test case, but I'm going to try and manually come up with a test case instead.

new todo, number 4: add some sort of update to the game-over screen that shows the tiebreaker rule was used to find the winner.

why? As I was writing a draft blog post, summarizing the game changes and asking folks to keep an eye out for the tiebreaker rule happening so they can report it to me, I realized I need a way for them to actually see that it happened.

[simondorfman]

@skotz found a bug in my code, think it's fixed now with this change: https://github.com/simondorfman/volcanoes/commit/3d5497ffbee8860dfedb29d2861b300bbc2be032 ...which should automatically get added to the pull request.

running tournament game simulations again...

[simondorfman]

I ran a tournament with these settings:

...and out of 400 games, got 12 results with the tie-breaker condition triggered:

Transcript

1. S08 S31 G N26 S35 G N22 S37 G S16 S17 G N37 S05 G S18 N06 G S20 S16 G S26 N20 G S17 S19+ G
2. N09 N40 G N02 S01 G S17 S08 G S12 N01 G N01 S36 G S34 S35+ G S22 S07 G S34 S35 G S10 S26 G
3. S26 S34 G N27 S01 G N17 S13 G S10 S36 G S08 S15 G N25 S05+ G S18 N26 G
4. S22 N31 G N36 N17 G S31 S16 G N34 N29 G S18 S16+ G N30+ N33 G S11 S02 G S09 N33 G N28 S02+ G S10 S29+ G
5. N34 S28 G N01 S01 G N19 N17 G S16 S14 G N10 N12 G S29+ N04 G S15 S03 G S03 S36 G N16 N04 G S16 S13 G S18 S25 G S13 S35 G
6. S22 N10 G N15 N27 G S25 S36 G S40 S18 G S34 S32 G S16 N30 G N30 S27 G N31 S21 G S27 S31+ G
7. N38 S32 G N02 S02 G S18 S29 G N04 N13 G N08 N25 G S26 S27 G S28 S16 G
8. N24 N26 G S25 S37 G S40 S33 G S17 N17 G N32 N15 G N34 N13 G N04 S29 G S03 N29 G N05 S05 G
9. N03 N13 G N35 N31 G N16 N33 G S31 S33 G N14 S40 G S21 N32 G N24 N09 G N08 N07 G N22 S23 G N08 N21 G
10. N12 N03 G S12 S07 G S27 N27 G S09 N16 G N39 N18 G N38 S06+ G S16 N33 G N38 S15 G S15+ N38+ G
11. N09 S08 G S32 N21 G N32 N23 G S28 S30 G S15 S14 G S13 S11 G S02 S29 G S01+ N30 G S02 S03+ G
12. S14 N09 G S40 S23 G N26 N15 G S35 S06 G N21 S02 G S18 S11 G S10 S09 G S10 S26 G

Full CSV attached.

tourney-data-20201101114744.csv.zip

[simondorfman]

I'm now running a huge tournament with these settings:

At the current rate, this tournament should finish around Wednesday, December 2nd.

When it's finished, here's what I plan on doing with the data. Calculate how close to 50/50 the win ration of first player vs. second player, for these 3 scenarios:

1. using the current tiebreaker rule: awarding tie wins to the player that played the last turn
2. award all ties to the first player
3. award all ties to the second player

Comparing those three numbers, whichever is closest to 50/50 is the tie-breaker rule I'll go with for now.

[simondorfman]

I started a repo where I'll answer this question and other game design questions as they come up: https://github.com/simondorfman/volcanoes-game-design