1. icon for News
  2. icon for TCHOW

News

Sunday, April 9, 2017

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.

Wednesday, February 22, 2017

Come At Me Slow

I can't very well mention last year's New Year's album and not point out that the 2016/2017 album is also out. It's called "Come At Me Slow" and you can listen below, on SoundCloud, or on Spotify.

The standouts for me this year are the amazing cover art by Kathleen and the epic sounds of the title track. It is with some regret that I note that I still haven't been awarded the steam achievement described by "Hate Plus / Love Note", despite sending a verification photo and e'rything.

The New Year We Missed

With the crush of the SIGGRAPH deadline, I failed to both create a New Year's card or even make a post detailing the Jimike New Year's album for 2015/2016. So let's fix that right now, shall we?

Grid Line

My remedial New Year's card for last year is titled "Grid Line", and that about sums it up. The grid gets interesting half-way through. Play here (works on smartphones, too!).

I think this might also be my first New Year's card with sound effects (though those don't work on phones; sorry).

36-Hour Day

Last year's album was titled 36-Hour day, since we were producing it in such widely separated time zones. You can listen on SoundCloud (widget below) or Spotify

Standout tracks for me are "Dear Snails" and "The Only Fi I Have" both of which have honest, if shallow, lyrics.

Tuesday, May 17, 2016

Convex Horizons

Today, I started thinking about the complexity of a certain geometric problem: finding the horizon of a set of convex objects. In this post, I'll first state the problem and then attempt to explain why this is an interesting problem to think about.

The Convex Horizon Problem

Given a list of 2D convex objects, return a function h that maps each x-coordinate to the maximum y-coordinate such that (x, h(x)) is contained in some object. This is the "horizon" or "skyline" of the objects.

First Reduction: when working with convex polygons, this is equivalent to finding the horizon of a series of line segments; or, equivalently, trapezoids with bottom edges at negative infinity. So this is the version of the problem I'll be thinking of:

(The horizon of the many-hued trapezoids is the thick black polyline.)

Thoughts on Complexity

Any algorithm that computes such a horizon must spend time at least linear in the number of output points in the horizon line. So it's interesting to think about how many points this could be. Particularly, I find this intriguing because of two different (related) problems.

The Box Horizon problem pretty clearly has output of size at most 4N (for N boxes). The argument goes something like: the horizon is a chain of line segments alternating between flat segments and vertical segments. The vertical segments correspond to the vertical edges of boxes, and each box edge appears at most once in the list. This means there are at most 2N vertical segments, which must (therefore) separate at most 2N horizontal segments.

(Mind you, the time complexity of an algorithm that computes a box horizon from an unsorted set of boxes is likely O(N log N), given as reducing sorting to box horizon seems likely to be trivial.)

The logic used to argue for the output complexity of box horizon breaks for trapezoid horizon because the topmost trapezoid can switch not just at an edge, but at a line segment intersection. And it's easy to see that there can be quadratically many intersections among lines:

But this standard lines example doesn't have a clear translation to the trapezoid horizon setting! So that leaves an interesting puzzle: is there some other argument that can be used to demonstrate linear output complexity of trapezoid horizon? Or, failing that, what's a super-linear output complexity example for this setting?

I plan to ponder this more over the next few days. If you have some ideas, feel free to get in touch.

Wednesday, April 1, 2015

The Rktcr Benchmark

In preparing Rktcr for release on Steam, I've been making some minor adjustments to the code and art (Steam Achievements! Blinking characters!). As I've made a bit of a fuss about before, Rktcr is a game that plays exactly the same across three compiler/OS combinations (g++/Debian, clang++/OSX, cl.exe/Windows). As such, part of any update is confirming determinism with an extensive test suite.

Specifically, I have the game compute SHA1 hashes of relevant state as it plays itself on a hand-crafted set of ~1,600 par time paths. Yes, there are over 1,600 individual paths segments you might want to play in Rktcr, and I have a plan to add cheat-proof leaderboards for all of those. But that's a topic for another post.

The Benchmark

So how do my Windows and Linux partitions stack up against each-other on this (blended filesystem/compiler optimization) benchmark? (I'm not testing clang++/OSX since that's not installed on the same machine.)

OSCompilerTime
WindowsVS2013, Update 3120 seconds
WindowsVS2013, Update 4121 seconds
WindowsVS2013, Update 4, optimizations off137 seconds
Linuxg++ 4.8.179 seconds
Linuxg++ 4.9.276 seconds

I'm pretty sure that the one-second difference between VS updates is within noise, though I dread that it may be a performance regression. Turning optimizations off demonstrates that they are at least doing something.

Under Linux, there is a noticeable improvement between the steam-runtime-targeting g++ 4.8 and my system-wide g++ 4.9; whether it's a compiler or standard library difference isn't clear; but it is certainly nice when newer compilers make old code faster.

Finally, I'm surprised that the Windows/VS version is doing so poorly compared to Debian/g++ -- my previous experience has been that cl.exe produces code that is a fair bit faster than either g++ or clang++. I'm left wondering if this particular code is something that cl.exe fails to optimize properly, or if the Windows stack is failing somewhere else (filesystem read performance? standard library implementation?). There could even be exotic hardware causes -- Windows and Linux are run from different [though identically-branded, purchased-at-the-same-time] SSDs -- perhaps one is slower.

Saturday, February 21, 2015

Rainbow is a Pocket Gamer 2015 Nominee

My rainbow-driving game, Rainbow (available for iOS and Android for approximately $1) has been nominated for a Pocket Gamer award in the "Most Innovative" category.

Please head over to Pocket Gamer to vote. It's almost certainly not going to win, but one must try, eh?

Thursday, January 1, 2015

New Year Paraphernalia

Each year, my brother and I spend the new year's eve building a new album to release. Also, I've been trying to get in the habit of releasing a little interactive solstice / new year card around the same time. So here they are.

Game

This year's game is a quick implementation of a puzzle interaction involving moving blocks around. The opening animation explains it better than I could:


Play

Album

This year's is called "Sassy Bunny" and you can listen to it right now:

Some highlights: Weird To Me -- a classic one-take Jimike song; Undone -- all sorts of interesting sounds in here; Intro -- really energetic track. Some lowlights: weird mixing in Great In The Future; She -- a track that is perhaps too mellow.

We are starting to accumulate a fair bit of audio gear. This year's album involved two guitars, a banjo, a Monotribe, three mics, and two different midi control devices -- a keyboard and a Push (run through a custom script to make it nice for use in Reason).

As always, expect Spotify links when we get around to pushing the files to our distributer.