Who Wins (Simple) Gwent?

So, a few weeks back, I played some of the beta of Gwent, an online two-player deck-building card game. This post analyzes a very simple version of the game -- one where the cards have value but no text, and both players always draw the exact same cards -- and shows that in this simple version, perfect play results in a tie.

Basic Rules

Let's start with the rules.

Gwent is a two-player card-based point-accumulating game played over three rounds. Players begin the game by drawing 10 cards, of which they may redraw three. During each round, players take turns playing cards. Each card changes the players' points totals. If a player doesn't want to play any more cards during the round they can "pass". The round is over when both players pass.

The player with the higher point total at the end of the round is the winner. In the case of ties, both players are considered to have won. If either player has reached two wins, that player wins the game. If both players win simultaneously, the game is considered a draw. If neither player has reached two wins yet, another round is played.

Points totals are reset at the end of each round. Players replenish their hands by drawing two cards after the first round and one card after the second round.

The first player for the first round is determined randomly; for subsequent rounds, it is the player that won the previous round. I forget what happens in the case of ties, but it's not crucial for the analysis below. (I think that the lead switches.)

Before the game begins, each player constructs a deck of 25 (or more) cards. These decks are where each player draws their cards from. The contents of this deck is limited in various ways that I won't discuss, since part of the conceit of this post is that we're going to ignore the existence of decks and assume each player draws the same cards.

This treatment of the rules also neglects discussions of Factions, Leaders, and Card Text. Briefly, each player must choose a Faction when building their deck. This Faction limits which cards may be used in the deck, and may provide a global ability [e.g. "redraw an extra card at the start of each round"]. Each player must also choose a Leader. A Leader is essentially an extra card that is always drawn at the start of the game. Finally, each card may have complicated Card Text which specifies how it interacts with the point totals and other game state. For the discussion that follows, none of these things will be considered.

Simple Gwent: Provably Boring

In "Simple Gwent", which I will talk about for the rest of the post, all cards have a positive point value, each player starts with the same hand, and both players will draw the same cards between rounds.

It turns out that Simple Gwent always ends in a draw if played competently. Specifically, I will demonstrate that each player can force a draw, regardless of what the other player does. I break this strategy into four cases, depending on the state of the game. In each case, the players are labelled F and S, "first to act" and "second to act". Note that labels may change between rounds.

Case Zero-S: Score 0-0, Same Cards; S to draw/win

In the first round, the second player can guarantee a draw by playing a simple strategy:

• Play whatever F just played.

This always results in a draw with identical cards remaining, at which point player S uses strategy One-F or One-S to force a draw/win (I don't recall if lead switches on a draw).

Case Zero-F: Score 0-0, Same Cards; F to draw/win

In the first round, the first player can guarantee a draw by playing a very basic strategy:

• Pass.

This results in one of two outcomes:

1. Player S plays at least one card and wins; in which case Player F uses strategy Behind-S next round.
2. Player S passes, which results in a draw, in which case Player F uses strategy One-F or One-S (depending on if the lead switches in a draw) next round.

Case Behind-S: 1-0 (F winning), S Has Card Advantage; S to draw/win

In the second round, when S has a strict superset of F's cards (that is, S has all the cards F has, and at least one additional card), S can force a win/draw by playing as follows:

• If F plays, play the same card.
• Once F passes, play the cards in your hand that F does not have in their hand, then pass.

This guarantees a win for S, bringing the score to a 1-1 tie, and making both player's hands the same. At this point, S uses strategy One-F to guarantee a win/tie.

Case One-F: Score 1-1, Same Cards; F to draw/win

In a round where both players have already won and have the same cards, the first player can guarantee at least a draw by following this strategy:

• Play all cards.

This results in one of two outcomes, depending on what player S does:

1. If player S plays all their cards, resulting in a tied match and game.
2. If player S does not play all their cards, and player F wins the match and game.

Case One-S: Score 1-1, Same Cards; S to draw/win

In a round where both players have already won and have the same cards, the second player can guarantee at least a draw by using this strategy:

• Play all cards.

This results in one of two outcomes, depending on what player F does:

1. If player F plays all their cards, resulting in a tied match and game.
2. If player F does not play all their cards, and player F wins the match and game.

Conclusions and Notes

The above demonstrates that Simple Gwent is boring whenever both players draw the same hand and know it. In other words, [full] Gwent is very much a deck-building game -- your basic goal as a player is to make sure that you end up with a better draw than your opponent. Of course, this also suggests that it would be interesting to figure out just what a good draw looks like (obviously, it should be high-scoring; but perhaps it is more important that it have two [three?] high-scoring subsets).

Also, the "Pass First" strategy seems really weird in this context -- shouldn't F take the opportunity to get an early win? Not always! Consider a simplified scenario where players start with one card of value a, draw one card of value b < a after the first round, and a card of value c after the second.

• Round 1: First player has {a}, second player has {a}: First player plays a, second player passes. First player wins.
• (players draw b)
• Round 2: First player has {b}, second player has {a, b}. Then, either:
  • If first player passes, second player plays b (winning), then wins the last round because a + c > b + c.
  • If first player plays b, then second player plays a (winning), then wins the last round because c + b > c

In other words, playing first in simple Gwent can lose you the game. Maybe there's a take-away there for real Gwent (though I think some of the card text is written to explicitly mitigate this problem).

Finally, I should note that in the process of coming up with this reasonably simple proof, I also wrote some reasonably less simple code to explore Simple Gwent game trees and visualize game states. It's not particularly complete, since I ended up not using it for the final post. But if you're interested, you can check it out; it prints some things to the console and also shows a reasonably-nicely styled game state, but mostly it's some half-baked hacks.

Math: What is the right Aspect Ratio?

In the shower the other day, I thought up an interesting question: what is the right aspect ratio to work in? (With, of course, the immediate follow-up question: what does "right" mean in this context?) In this post, I'll attempt to answer both questions with some simple math.

Setup

I've been doing some pre-production work on a storybook game for iOS devices. The game will likely be composed of full-screen scenes with hand-drawn background plates. I don't want to have require new background plates for every resolution (much less aspect ratio), so the plan is to create one background and fit it to the screen.

So, depending on the screen aspect ratio (in this case: 4:3 on the left, 16:9 on the right), some of the image will be cropped, either off the sides or off the top and bottom.

Minimizing Waste

Since I'm not of a mind to have something drawn that isn't needed, one possible definition of "right" aspect ratio is the one that minimizes wasted area in the background image. So how much area is wasted?

Well, denoting the aspect ratio of the screen s and the aspect ratio of the background image b, and -- without loss of generality -- assuming the screen height is 1, it is easy to draw a picture of the situation:

So, if the background is wider than the screen, the percentage of the background image wasted is (b-s) / b. Similarly, when the background is narrower, the waste is (1/b-s) / (1/b).

As expected, on a 4:3 screen a background image of aspect ratio 4:3 wastes the least.

Of course, on iOS one needs to worry about three aspect ratios: 4:3 [iPad], 3:2 [iPhone <= 4], and 71:40 [iPhone >= 5]. (In case you are wondering, 71:40 is 'nearly 16:9'.):

NOTE: I'm only considering landscape aspect ratios because that's the target for this game.

Assuming one wants to give equal weight to background waste on each device, the proper aspect ratio of the background image should minimize the sum of these three curves.

This minimization happens at the 3:2 aspect ratio. Indeed, my intuition is that with equally-weighted devices the minimum-waste aspect ratio will always be the median aspect ratio.

Maximizing Excitement

In the previous section, I counted areas of the background for each time they were cropped -- that is, background that didn't show at 4:3 and at 3:2 was counted as being twice as bad as background that was only cropped at 3:2. Perhaps, instead of obsessing over these lost pixels, one should instead maximize the percentage of the background that is cropped by no device (i.e. the part of the background every screen sees).

What is this percentage? Consider a background of size bx1 to be shown on screens of aspect s1, ..., sN. The width of the visible-on-all-screens region is w = min(b, s1, ..., sN), because the background will be cropped after its aspect exceeds the smallest screen aspect. The height of the visible region is h = min(1, b / s1, ..., b / sN), because of cropping on the top and bottom of edge of the background when it is scaled to the widest aspect ratio. (More intuition: consider scaling the visible region to [horizontally] fit a screen of size sx1. The scale factor is s / b, so it must be the case that h * s / b <= 1; thus h <= b / s.)

Putting these figures together gives percentage 100 * min(b, s1, ..., sN) * min(1, b / s1, ..., b / sN) / (b * 1). Interestingly, this means that maximizing visible area only depends on the narrowest and widest aspect ratio under consideration:

The unfortunate news is that with aspect ratios of 4:3 and 71:40 in the mix there isn't any background size that doesn't end up with about 25% of its area not visible on all screens. The fortunate news is that the best aspect ratio in terms of waste (3:2) is within this 75%-used plateau.

Going Further

In this article I didn't talk at all about foreground content (which must be scaled to fit within each aspect ratio), and only explored two objective functions. Other interesting objective functions might include one weighted for all browser sizes, or one that is concerned with fairness (forcing all screens to lose about the same area of the background).

If you have other ideas, feel free to leave a comment or send an e-mail.

Brighter 'Bows

The HTML5 version of Rainbow features vibrantly colored Rainbows; when porting to C++, I traded off a bit of the brightness of the rainbows for softer intersection behavior. This weekend, I set out to brighten the bows in the C++ port, while retaining nice bow intersections.

html5: bright bows

old C++: dull bows

new C++: bright bows

As you can see, the C++ version has been improved to have bows as bright as the HTML5 version.

The Goal

In Rainbow, the player can split the rainbow they control into multiple "fronts" and drive these fronts separately. Each front leaves a rainbow trail.

I would like several conditions to hold:

1. Trails freshly produced by a front should draw over older trails.
2. Fronts should always remain visible.
3. No hard edges should be introduced.

To justify briefly: (1) arises because I want players to see what they are currently controlling; (2) is important because players should be able to see how much rainbow they have left; and (3) just seems like how magical rainbow substance should behave.

The Old Solutions

HTML5

In the HTML5 version of Rainbow, the entire rainbow is redrawn each frame with each vertex's depth set based on the number of ticks from the beginning of the rainbow. This method actually fails all three of my ideal conditions in some cases, e.g. when drawing with an older front.

C++

In the C++ port, the rainbow is accumulated into a framebuffer. This pretty much guarantees that condition (1) holds. Condition (2) is satisfied by always drawing (but not accumulating) the very front of the bow over the top of everything in a different rendering pass.

This leaves condition (3) -- no hard edges. This is solved by drawing the blow slowly instead of all at once. Specifically, every time a front moves, it draws over its last 10 positions with partially-transparent segments. This has the effect of slowly building up the bow color over 10 steps:

Unfortunately, because it draws over each of the old positions with the same opacity (alpha value) -- set, in an ad-hoc way to 1/8th -- the effective opacity of the bow is only about 73%.

The New Solution

Let me start by considering a simpler version where we only draw over the last 4 locations. Labeling the segments that get drawn as 1-4 and the locations traversed a-g (both from oldest to newest), one can sketch this diagram:

  ...               ...
frame 4:         1 2 3 4
frame 3:       1 2 3 4
frame 2:     1 2 3 4
frame 1:   1 2 3 4
          ---------------
location:  a b c d e f g

I.e. location a will be drawn into by segment 1, and then no others; location b gets drawn by 2 then 1, location c by 3 then 2 then 1, and so on.

So what opacity value should we pick for segment 4 if we want locations d and beyond to have opacity α_target? Well, it depends what the next passes (1-3) will draw over it. Let's say that segments 1-3, when drawn, will cover fraction α_next of a pixel. Then we can select opacity value x for segment 4 by writing down the blending equation:

α_target = α_next + (1 - α_next)x

α_target - α_next = (1 - α_next)x

x = (α_target - α_next)/(1 - α_next)

This passes some basic sanity checks -- if we want 100% coverage after segments (1-3) are drawn (i.e. α_target = 1), we need to draw segment 4 with 100% opacity (i.e. x = 1). Also, if α_next is greater than α_target then we get negative values -- which makes sense, as segment 4 can't prevent the subsequently drawn segments from covering the location, so it needs to attempt to preemptively remove coverage.

Implementation

Since I'd like the rainbow to smoothly fade in from a cleared start, I chose a "fade" opacity value, f to vary smoothly from 0% coverage (at the trailing edge of the oldest segment) to 100% (at the leading edge of the newest).

In the pixel shader, other factors that influence opacity -- band color, edge-of-band "antialiasing" texture -- are looked up. Letting their product be called m, the shader sets:

α_target = f * m

α_next = min(1.0, f + 1/10) * m

These values are used to compute the final opacity value x as outlined above. This results in a variable-opacity front that produces a more vibrant bow:

Next Steps

I was a bit worried about having a divide in the pixel shader, but profiling on iOS shows negligible effect on frame time.

Since all of this math is actually done on 8-bit color values, some inaccuracy (and banding) does result. I could avoid this (and the above-mentioned divide) by doing the computation of x with a look-up-table that takes these errors into account. However, the artifacts are not so severe that this is a high priority.

Some Methods That Didn't Work

Before settling on the present solution, I tried all sorts of other ideas including multi-pass rendering and different blending modes. While none of them were what I wanted, they did produce some interesting pictures.

World Curation for Rktcr

As I close in on a full public release of Rktcr, one of my tasks is to settle on a set of worlds to ship with the game. I've already talked about how my code generates worlds, but this is only part of the story.

You see, the pool of worlds I generate is skewed -- only candidate worlds that are solvable are maintained, and this tends to bias toward worlds that use zones with many potential paths. But how bad is this skew? To investigate, I generated 1000 3-gem worlds and made a plot of the number of times each zone appears divided by the total number of zones:

Ideally, this curve should be flat -- each zone should appear about the same number of times. But this is not the case.

The zone on the far left (which actually only appears once out of the 1000 worlds) doesn't have its claims properly set, so -- as far as the world generator knows -- is basically impassible. This should change once I re-work the level somewhat, so it is probably safe to ignore.

However, the second-least-frequent zone is still about than 8 times less likely than the most frequent zone.

Flattening the Distribution

There is no reason for me to ship this set of 1000 worlds, however. Is there a subset with a better distribution of zones? It appears so:

One trimming method I came up with is to repeatedly pick a world whose zones all appear more frequently than average, and remove that world. This flattens the curve somewhat, but soon enough the method runs out of worlds to remove.

The max-min approach removes the world with the most frequent least frequent zone; since this can always find a world to remove, I terminate the search when there are 100 worlds remaining.

Finally, I tried an approach that repeatedly removes the world whose zones have the highest average frequency. This flattens the size-3 worlds the most of any of the methods, with the second-leftmost and rightmost zones only varying about 5% in frequency. (I'm disregarding the leftmost zone, as I mentioned above).

Using the average-frequency metric does seem to come at a slight price, however -- the average number of zones per world decreases to 5.2, from an average (over the starting 1000) of 5.5.

Large Worlds

Three-gem worlds are the smallest that appear in Rktcr. How do these approaches work on the medium (seven-gem) and large (fourteen-gem) worlds? Are they even needed?

Looking at the frequency of each zone in 1000 worlds with seven gems (left), and fourteen gems (right), it appears that some leveling might help. Interestingly, the fourteen-gem worlds already seem more balanced. I conjecture that this is because they are each already using (on average) 25 zones of the 30 possible, which makes it hard to not pick a zone; additionally, the larger world size may provide more flexibility in entering a zone resulting in more potential for completion.

The top-half strategy fails to work for both seven-gem and fourteen-gem worlds as they tend to contain more than half the zones already, so always have one which is less frequent than average.

Max-min again provides some leveling, especially effective at the bottom end (in terms of frequency).

Finally, removing worlds with the highest average frequency works well at the top end, though the fourteen-gem worlds result (right) does have a pronounced jump at the most frequent position, and both suffer from a roll-off toward the left.

Further Investigation

It appears that, for three-gem worlds, the average frequency heuristic works well; while for larger worlds, some combination of average frequency and maximum minimum frequency might be better for leveling the distribution at both the high and low ends.

However, frequency of appearance doesn't tell the whole story. In a follow-up post, I plan to investigate the co-occurrence of zones as well as (possibly) the connections between zones. It will be especially interesting to see if the trimming strategies I've outlined tend to skew these other statistics.

Design Goals for a Board Game Rulebook Langauge

I spent today drawing things for Rktcr, so it's definitely time to unwind with some recreational math. And the problem that has been on my mind recently is how to design a language for describing board games.

But before I get into that, I'd like to take a detour into the problem that got me started thinking about this.

The Motivation: A Cryptographic Primitive for Deck Shuffling

Some time ago, I spent a little bit of time thinking about a relatively basic cryptography design problem: design an protocol that allows a group of agents to collaboratively shuffle a deck of cards, such that no person in the group knows the final ordering, all cheating is detectable, and the ordering will be random as long as at least one person is acting honestly.

I don't remember the full algorithm I came up with at the time, but loosely, it involved each player obscuring (in a Diffie-Hellman-like way) each card, shuffling the cards together, and handing them to the next player. Once all the players have done this, any player wishing to draw a card receives (securely) the information required to un-obscure the top card from the other players, and is thus able to "draw" the card by revealing it to themselves.

Obviously there are some details here that I've glossed over, but they are not germaine.

The Challenge: Extending to General Games

So, while it's interesting to think of this sort of primitive, or other primitives (passing a card, say) in isolation, it seems yet more interesting to try to come up with a complete and nicely composable set of primitives that can be used for general board and card games.

Another name for a nicely composable set of primitives is, of course, a language. So, the goal becomes: design a language that can be used (ideally, by a human without an advanced degree) to express the rules of any board or card game, in such a way that they can be interpreted (by a collection of computers -- one per player) to enforce these rules and play the described game.

If such a language existed, I could write a general board-game app using it; new games would be packages consisting of a rulebook (written in the proposed language), along with some UI scripts (which would handle displaying visible portions of the game state). The core of the app would be a rulebook interpreter, which would handle communicating state updates with other players' devices, and all the crypto to make sure that hidden state stayed appropriately hidden.

Language Features

What would a good language for describing board and card games look like? Well, my first impulse (mostly due to Chris' excellent ideas -- though I can't find the exact write-up I'm thinking of at the moment) is to work in a find-replace/linear logic setting. This means that we view the state of the game as consisting of some universe of things, and actions in the game involve consuming some of those things in order to produce other things.

This works well for basic turn-taking (a player's "ability to take a turn" is a thing that can be consumed by their turn). However, it doesn't always work at a high enough level to obscure the nifty crypto tricks we'd like to effectively "build in." Here's what I think needs to be added, either to the core language or as syntactic sugar:

• Visibility -- tokens should be able to be obscured, either from all players or from some players. They must be able to be revealed to some (or all) players. However, facts about obscured tokens should still persist (e.g. an obscured sapphire card in Scepter of Zavandor has an unknown actual value, but it is known to be a sapphire card).
• Ownership -- tokens should be able to be acted upon only by certain players. This is required to prevent arbitrary players for taking actions for other players. There needs to be a way to transfer ownership of tokens as a result of actions.
• Stacking -- this would just be "nice to have", except for...
• Shuffling -- stacks of obscured tokens should be able to be mixed, drawn from, cards added, etc; just as a real stack of cards (and hearkening to my initial motivation).
• Dice -- basically syntatic sugar on top of shuffling; but a common enough feature in games that it might be good to support it.
• Pattern Matching -- some sort of generalized reasoning so one doesn't have to, e.g., enumerate all possible melds in rummy.
• Integer Math -- gotta count victory points somehow.

One thing that can't be built in, given that I want all games to be able to work in a distributed way, is simultaneous player potential to act in a way that denies other players the ability to take the same action (e.g. calling "set" in Set). This is because collusion between players can mess up any consistent ordering.

What Next?

This is more of a problem statement than any sort of conclusion or proposal of a solution. I think the next step is to actually start to put together a syntax, and start trying to write some rulebooks. From there I can see how it is convenient to express ownership and visibility. Perhaps they are simply predicates that can come into existence through special rules and be consumed by others. Perhaps they involve moving tokens between different domains (with fixed ownership rules).

As always, feedback is welcome; I especially encourage those of you with PL background to cozy your brain up and figure out the language you would want to use to, e.g., write down the rulebook for Agricola.