Attempting to solve Get 1000

For quite some time I have been trying to completely solve the Get 1000 game. More specifically I am trying to find the strategy in a 1 on 1 game of Get 1000 that maximises the chance to win.

Analysis of a game with one choice left. If I analyse this sub-game using expected value, I return the average of the distances to 1000. In this case 184 for strategy 1 (S1) and 107 for strategy 2 (S2). This is the wrong metric though, a better metric (if the goal is to win in a 1 on 1 game) is to count wins for each strategy. In this case 1 draw, 1 win for strategy 1 and 4 wins for strategy 2.

Solving for expected value rather then winning

My initial attempt at solving the game failed spectacularity, since I attempted to solve the game by minimising the average distance of the expected value to a 1000. This is an easy to compute strategy (using a sort of bottom up dynamic programming, where I start with the easy sub-games above, and calculate backwards to the top), but it is the wrong goal. This leads to a strategy minimising the distance to 1000 on average. This interestingly enough differs quite a lot from the goal I wanted to solve, which was to maximise the chance to win any 1 on 1 game.

The strategy that bases itself of minimising the distance to 1000 curiously has a big lump of results around a distance of 50, while the win based strategy has more games at distance of 0 and 100, as well as more games with very heavy over or undershoot.

Since Get 1000 is quite small I can calculate how much the two strategies differ by running all possible games. Above is the result of such a calculation. The two strategies draw 41.2% of the time, while the win based wins 30.8% and the distance based wins 28% of the time.

Trouble with situations where choices are equally good

After figuring out I had the wrong goal, I found a way to create a strategy based on wins rather than expected value (this is much harder to compute, even using the same bottom up approach, since it is not possible to collapse results to an average, and ever growing lists of results must be compared). These strategies I suspect are very close to optimal, but there was something funky going on.

There are situations in my calculations where two placement choices have equal amounts of winning sub-games. Initially I thought I could just set an order of preference of my choice for these, but the resulting strategies beat each other when applied to all possible games. If the order of preference did not matter this should not happen.

For the longest time I could not figure out why this happened. I started questioning whether the markov property held in the game (I am still not 100% sure it does).

Enlightenment

At this point I took a few steps back and looked at what would be the correct framework to model this game in. Turns out it can be modelled as a Markov Decision Process. That in itself was not very helpful, but it eventually got me reading about the expectiminimax algorithm. Expectiminimax is a version of minimax for games with chance involved. While I had to modify it a bit for a simultaneous turn game, I implemented it for some subproblems of get 1000, which I could calculate to the bottom.

While implementing it I realised that I again would have to code resolution for when two choices are equally good. While googling a bit about that, I randomly read about Nash Equilibrium, and mixed strategies. I was already aware of most of this, but it suddenly it dawned on me that my game might contain mixed strategies which could effect the outcome my expectiminimax calculation, and which I needed to take into account.

Wrong payoffs propagated in expectiminimax

Indeed, after searching for a bit, I found several cases where a mixed strategy is needed. The example below shows a expectiminimax situation where a mixed strategy is needed to get the best outcome.

A Get 1000 situation as solved by expectiminimax. The two games on top are the current situation for two players. To make a decision in expectiminimax we must then compute the payoff matrix by recursively analysing all possible sub-games until the end (returning expected payoffs), and then solve the payoff matrix. Using the solver here, this particular sub-game has the payoff of -98/39 (- means in favour of player 2). In this situation: Player 1 should play ones at ratio of 23/39 and hundreds 16/39, and player 2 should play tens at a ratio of 11/39 and hundreds 28/39.

While this exact situation will probably not arise assuming perfect play, the result still might matter since expectiminimax depends on all subgames propagating correct payoffs.

The road ahead

I need to include the support enumeration or theLemke-Howson algorithm for finding nash equlibrium in the placement situations that require it, and then I need to somehow make expectiminimax run for the full game. Currently I can only run expectiminimax (without Lemke-Howson) in reasonable time, for a game which has 6 placements left.

From AI: A modern approach, it seems A/B pruning can be used, but it seems to be less effective on games with chance. I guess it is worth a shot.

Gl hf to me…

Scary pitfalls when using Spring annotation based transactions

transactions and exceptions

Spring annotation based declarative transactions uses AOP to very easily add transactions around methods. Using it looks like this.

@Transactional
public Stuff createStuff(Input input) {
       Stuff stuff = new Stuff(input);
       dao.storeStuff(stuff);
       dao2.registerStuff(stuff2);
       return stuff;
}

Explained very quickly: If the method returns successfully then it commits, if a runtime exception passes the proxy boundary around the method, or if the transaction is marked rollback-only, then the transaction manager will do a rollback of the transaction.

It is incredibly easy to use, and it saves a lot of boilerplate compared to a more procedural approach where commit and rollback calls are specified explicitly. While useful, it comes with the cost of being tied to the scope of the annotated method, along with several other more hidden risks and costs.

Below are several examples of problematic code I have seen caused by annotation based transactions. Similar code examples and tests can be found in this repo on Github.

Catching exceptions in a transaction annotated method

In the method below, it is very easy to think that all errors are handled, and that this method will never throw, but if the transaction is marked as rollback only, this method will throw outside the try catch block. Breaking expectations and causing unexpected errors.

@Transactional
public Stuff createStuff(Input input) {
       Stuff stuff = null;
       try {
           stuff = new Stuff(input);
           dao.storeStuff(stuff);
           dao2.registerStuff(stuff2);
       }
       catch(RuntimeException e) {
           logger.info("No problem…");
           //Do more stuff
       }
       return stuff;
}

This is much more visible with a explicit transaction scope. I have seen this several times, even by experienced developers. These errors are hard to test for, and when they happen lead to very weird behaviour, since the exception is absolutely not expected where it suddenly occurs.

Order of proxies can change outcome of transaction

It is critical that AOP interceptors are stacked in a sensible order. We usually do not want to commit a transaction, and then get a timeout error from Hystrix. Or have the transaction commit, and then have validation constraints on the Stuff instance fail. Ask yourself. Do you know in which order each annotation will be applied here? Does everyone on your team know?

@Transactional
@HystrixCommand("abc")
@Valid
@OtherAOPstuff
@EvenMoreAOPStuff
public Stuff createStuff(Input input) {
       Stuff stuff = new Stuff(input);
       dao.storeStuff(stuff);
       dao2.registerStuff(stuff2);
       return stuff;
}

The order by default is (though due to this Hystrix bug/feature validation will never be applied O_o) :

  • Transaction start
  • Hystrix
  • Validation
  • Validation
  • Hystrix
  • Transaction commit/rollback

It would be nice to have Hystrix outside the Transaction, since that avoids the transaction boundary when the short-circuit is open. This is possible with ordering the AOP interceptors,at the same time, it is important to avoid Validation happening outside the Transaction, since then we might commit and then throw an exception (typically a rollback is wanted if data is invalid).

Nested transactions joins existing transaction by default

This is very nefarious, and I have no idea why nesting transactions does not cause an exception by default.

The example that I think best shows this problem, is when you reuse a method in a service class which uses a transaction further down the call chain. That method uses a transaction to ensure it is rolled back if it throws an exception, but the calling method catches that exception and does some business decision based on the exception.

Now along comes an unsuspecting victim who has a transactional method that wants to use this method for some business purpose.

What happens now, is that the second transaction joins the first. Then an exception is thrown by one of the database queries in moveStuffInDB. That exception passes the first transaction boundary marking the transaction rollback only but is then caught. Processing continues, and then the exception reappears at the last boundary on commit. This means that the semantics of reusedMethod might have been changed a lot, and there is no way createStuff can see from the outside that this will happen.

@Transactional
public Stuff createStuff(Input input) {
       Stuff stuff = new Stuff(input);
       dao.storeStuff(stuff);
       reused.reusedMethod(stuff.getInfo());
       return stuff;
}

//A method in another class calling another transactional method.
public void reusedMethod(String input) {
     try {
         deepClass.moveStuffInDB(input);
     }
     catch(RuntimeException e) {
         //Swallow exception and do some action
     }
}

//Tx method with several db update calls
@Transactional
public void moveStuffInDB(String input) {
      dao.moveStuff(input);
      dao2.moveStuff(input);
}

To add to the confusion, use checked exceptions

When a checked exception passes the boundary of an @Transactional annotated method, it does not cause rollback by default (it can be changed in the annotation though). Add Spring Batch, which will also start transactions that a nested transactions will happily join, and transaction outcomes become even more foggy and hard to reason about.

I think using nested transactions usually is a bad idea, and it should be an opt in feature. In the normal case throwing an exception if a transaction within a transaction is encountered seems sensible to me.

Lambdas provide a much better API for transactions

In any language with good support for lambdas, I think it is very natural to do declarative transaction management using them. Spring sort of supports this, but you need to depend on a platformTransactionManager and a TransactionTemplate. This seems weird to me, given that the annotation based transactions does not make you depend on these.

With lambdas, transactions can be done like below (example is using Kotlin). This is declarative, while providing explicit transaction boundaries. It is therefore very easy to catch around the transaction, and the transaction does not have an unclear order when combined with other annotations.


fun createStuff(stuff : Input ) : Stuff {
       return doInTransaction { //Explicit tx scope
           val stuff = new Stuff(input);
           dao.storeStuff(stuff);
           dao2.registerStuff(stuff2);
           stuff 
       }
}

fun multipleTransactionsInMethod(stuff : Input ) : Stuff {
       val res = doInTransaction {
           val stuff = dao.storeStuff(stuff);
           stuff;
       }

       val res2 = doInTransaction {
           val stuff = dao2.storeStuff(stuff);
           stuff;
       }

       try {
           doInTransaction {
              dao.storeStuff(stuff);
            }
       } catch(e : RuntimeException) {
           //Handle stuff
       }
} 


Along with the previously mentioned advantages, this also makes transactions much more visible, and allows easy inspection of the transaction code by developers.

To be honest I am a bit uncertain how good it is to rely on exceptions passing boundaries to do rollback in the first place, but if that is the chosen way, I think the above approach is much better then annotation based transactions. I am really looking forward to try Exposed, which is an ORM tool from JetBrains that seems to go in this direction.

Learning what WebRTC SDP a=setup values mean

My very hacky webRTC datachannel implementation stopped working a while back, and I could not figure out why.

The way it behaved was hard to understand. Signaling worked as expected, and I received a STUN on the correct port and responded to that. Both Firefox and Chrome reported the response as fine, and kept sending new STUN heartbeats at the normal rate, but no DTLS handshake was initiated.

Initially i thought something was really broken with my STUN/DTLS multiplexing, but I soon figured out that it behaved as expected.

This meant I was probably sending some wrong parameter during signaling, but what?

This is the SDP of my answer to the given offer from the browser.

v=0
o=- 1234567 2 IN IP4 192.168.1.158
s=-
t=0 0
a=group:BUNDLE data
a=msid-semantic: WMS
m=application 51410 DTLS/SCTP 5000
c=IN IP4 192.168.1.158
a=candidate:1 1 udp 2113937151 192.168.1.158 51410 typ host
a=ice-ufrag:4a64ca2b
a=ice-pwd:a26b6a15a8b4d35db21692d37906840a
a=ice-options:trickle
a=fingerprint:sha-256 C9:E2:48:09:47:C8:CC:B3:51:A8:A1:C5:AA:63:51:26:50:1D:FF:76:AE:EF:CB:31:0C:E7:41:21:5A:11:FA:D5
a=setup:actpass
a=mid:data
a=sctpmap:5000 webrtc-datachannel 1024

SDPs are confusing to me, and figuring out what stuff really means in WebRTC context is a lesson in reading RFCs with a microscope, while always wondering if this is the correct RFC for this concrete problem.

Suddenly it dawned on me that it seemed like both sides were waiting for the other side to initiate the DTLS handshake.

It turned out this was the problem:

a=setup:actpass

Since i responded with actpass in my answer SDP, the browser could not know if it wanted to initiate DTLS or not, and I guess it defaults to passive now. actpass is an illegal response value according to this RFC, and defaulting to passive is probably more correct then active. Setting a=setup:passive fixed the issue, since that tells the browser to be the initiating party.

Good times.

Starting Marathon Infinity in vidmaster mode on linux

A few days ago I installed Marathon Infinity for some multiplayer games. I wanted to practice a bit first, but sadly it is not possible to start a multiplayer game alone, so the only way to get some fast action is to play singleplayer in vidmaster mode.

This resulted in another problem. I could not figure out the button combination to trigger vidmaster mode on linux. After some minutes searching I was quite frustrated, but thankfully the Aleph One source is available, and the source revealed:


static bool has_cheat_modifiers(void)
{
	SDL_Keymod m = SDL_GetModState();
#if (defined(__APPLE__) && defined(__MACH__))
	return ((m & KMOD_SHIFT) && (m & KMOD_CTRL)) || ((m & KMOD_ALT) && (m & KMOD_GUI));
#else
	return (m & KMOD_SHIFT) && (m & KMOD_CTRL) && !(m & KMOD_ALT) && !(m & KMOD_GUI);
#endif
}

Based on this, vidmaster mode on linux is activated by holding SHIFT and CTRL while clicking BEGIN NEW GAME, and sure enough:

Pledging hard here

Draft Engine

Start a draft

For a while I have been working on a generic draft engine for card games. In trading card games (TCGs), drafting is a way to distribute cards in a semi random way, where players interact with how cards are distributed. In the TCG world this is distinct from sealed deck (semi randomly distributed cards, but no player interaction during dustribution) and constructed (you design your deck before playing from a set of allowed cards).

Supported draft styles

My draft engine supports two styles of draft:

  • Grid draft: A draft style for two people where you select rows or columns of cards from 9 face up cards.
  • Regular draft: In this draft style you pick a card from a pack and pass the pack to the next player. It works with 2-8 players, but 6-8 is recommended.

grid draft
The draft engine in action. This example is an Magic the Gathering grid draft.

These forms of draft can be used for most kinds of TCGs. Since the engine is not tied to any specific kind of game, you can draft anything you can give a name and an image. You can draft your family photos if you want to.

Drafts with custom content

The engine works by using a very simple JSON structure to supply card names and card images, it looks like this:

[
  [
    {
      "name": "CardOnePackOne",
      "url": "http://crazymedia.com/cardonepackone.png",
      "id": 0
    },
    {
      "name": "CardTwoPackOne",
      "url": "http://crazymedia.com/cardtwopackone.png",
      "id": 0
    }
  ],
  [
    {
      "name": "CardOnePackTwo",
      "url": "http://crazymedia.com/cardonepacktwo.png",
      "id": 0
    },
    {
      "name": "CardTwoPackTwo",
      "url": "http://crazymedia.com/cardtwopacktwo.png",
      "id": 0
    }
  ]
]

The values are pretty self explanatory, but for clarity:

  • “name” – The name of the card, which you can export when finished drafting.
  • “url” – An URL pointing to an image of the card.
  • “id” – Not in use, so 0 is a fine value.

The engine comes with several predefined card list. Packs will then be drawn from those lists, but if you want to supply your own set (for example a cube or your own game) it is possible to start a draft where you send in any number of packs of cards using the JSON format shown above.

Have fun drafting.

Writing a WebRTC data channel implementation

After looking at webtorrent a while ago I really wanted to dig deep down into WebRTC to see how it actually worked. WebRTC is a web standard that allows two browsers to set up a peer to peer connection (usually browsers only talk through intermediary servers). It also brings unreliable and unordered networking to the browser, which is great for some kinds of applications.

WebRTC

Searching for WebRTC and Java on Github mostly gave me some very simple applications that use a Java server to set up a peer to peer application between two browsers. There also seemed to be some unmaintained JNI wrappers for the WebRTC libs. What I wanted was a pure Java WebRTC implementation so that I could talk directly to the browser more on my terms.

Since this was lacking I decided to try to write my own Java WebRTC implementation. To limit the scope, I decided that I would only try to talk to Firefox, and only support an unordered unreliable DataChannel. Which is WebRTC’s greatest selling point for me. What I ended up with can be found on my profile on GitHub. It is not pretty or solid, but it sort of works.

Protocols

WebRTC is made up of bunch of protocols: ICE (to establish communication), STUN (binding and NAT traversal), DTLS (encryption), SCPT (over UDP) (message flow control), TURN (fallback for difficult network situations, which I have chosen to ignore).

The initial part of starting a WebRTC connection uses the ICE protocol, the ICE protocol is typically carried out over an encrypted WebSocket connection, though you can use encrypted pigeons if you like.

To be honest I have not looked a lot at ICE, but the parts most relevant for WebRTC works a bit like this:

  • A goes: This is my password and certificate signature, this is referred to as an offer.
  • B goes: This is my password and certificate signature, this is referred to as an answer.
  • Then A and B send each other different options of connectivity as candidates. I am currently blissfully ignorant of how this is supposed to work, in my current implementation I just send the first candidate from the browser and replace IP, port and auth data in the response.

The message format used in the browsers WebRTC implementation for offers and answers is JSON containing an SDP. The SDP contains tons of information that is not used (afaik). The values I have touched are marked in green below, for more information about the fields, this is a great overview.

The green highlights the important parts of the offer and candidate
The important parts of the offer and candidates, this is SDPARTA!

Important SDP values:

  • fingerprint:sha-256 – DTLS certificate sha-256 fingerprint.
  • ice-pwd – Your chosen password for STUN.
  • ice-ufrag – Your chosen user for STUN.
  • 192.168.1.100 58713 – Your offered address and port.

STUN

Once candidates have been exchanged, a STUN binding request is sent to establish connectivity, this request must be responded to with a binding response with a xor mapped address. The received message integrity hash is a HMAC-SHA1 which can be checked against the message hashed with the ice-pwd as key.

DTLS

After the STUN the next step is a DTLS handshake. Thank you Legion of the Bouncy Castle, without you I would have given up here.

Over the same UDP socket where DTLS is running, STUN must be multiplexed. STUN is here used to send “consent” requests every X seconds. If you do not respond to the STUN the browser reports ICE error and shuts down the connection. Bouncy Castle DTLS will silently drop these STUN “consent” packets, so this was a pain to figure out and debug.

SCTP

Once the DTLS is set up an SCTP connection is initiated. SCTP can be configured to work in all constellations of ordered/unordered and reliable/unreliable.

SCTP over UDP challenges

With SCTP over UDP several issues crop up. My main languages are all JVM based (Kotlin, Java). There is no SCTP implementation in Java, but there is an API for the systems SCTP. The API is very hard to integrate with an UDP socket though (I tried a bit, but it seemed very hard), so the simpler solution is probably to use a userland C lib like the one used by libjitsi.

Sadly i did not know libjitsi existed so I started hacking my own SCTP implementation in Java land. Way more fun…

Writing my own SCTP implementation

The SCTP spec is mostly ok, if a bit unclear in some parts. Once I found the SCTP parameter list it got better. It should also be mentioned that SCTP uses a CRC32C for checksums, this differs from the one used by STUN. This took me quite a while to figure out.

I currently have a very minimal “working” SCTP implementation. Meaning that it can talk to a browser, but does not shut down nicely, and does not do congestion control, and does not handle resends properly. These are very tricky areas to do well, and I have no clue, so I will probably change to use the lib used by libjitsi.

Getting the all important firefox logs

To not go in blind when debugging, logging from the connected browser is invaluable. This is my script to run firefox with WebRTC logging. The different modules can be turned on and off by not including them in the NSPR_LOG_MODULES. It took me a while to figure out the correct modules, so hopefully this helps someone else.

#!/bin/bash
dat=`echo ~`
path="$dat/webrtc_firefox.log"
export NSPR_LOG_FILE=$path
export NSPR_LOG_MODULES='signaling:5,mtransport:5,SCTP:5'
export R_LOG_LEVEL=9
export R_LOG_DESTINATION=stderr
open /Applications/Firefox.app/

Where is the code?

If this was interesting and you want to take a look at the source code. It is available on my GitHub profile.

Artifact 1.0.4 – Hello integer overflowing highscore!

Yesterday I finally finished some of my planned Artifact updates. The new version can be downloaded from here. Below is a detailed account of the changes in this version.

  • Added a game mode (rascal), where you can not lose:

    As my 4 year old daughter was playing the game I had to keep typing cheat codes to keep her alive. This made me realise that I could introduce a game mode where it is not possible to lose, and where the player has infinite resources. Once I added the rascal mode she played for quite a while, and she even figured out some smart plays all by herself.

  • Artifact
    Rascal mode allows exploration of the game in a different way. Hello integer overflowing high score!

  • Removed global score tracking:

    Global score tracking from games not played on a server will always be prone to modified clients posting fake scores. This can be mitigated though obfuscation, but not really solved. My implementation was also very bad, and very hard to maintain. Maybe I’ll revisit this one day, but for now I am glad its gone.

  • Removed hash checks of local data:

    I do not care if you hack your local files so that you have insane scores. Hack the game all you want!

  • Prepare for OS X removal of some carbon audio API:

    I kept getting this message in my logs:

    WARNING: 140: This application, or a library it uses, is using the deprecated Carbon Component Manager for hosting Audio Units. Support for this will be removed in a future release. Also, this makes the host incompatible with version 3 audio units. Please transition to the API’s in AudioComponent.h

    The solution was to upgrade openal-soft by building from source, and replace the old openal.dylib that came with Slick2D with the libopenal.dylib built, which I guess uses the API Apple wants you to use.

BitBreeds stand with the humans; we won’t let it slide.

Aliens

With the discovery of a possibly habitable planet around one of our closest stellar neighbours, it has become clear that sooner rather then later, there will be aliens and UFOs around.

A new hope

This summer, UFO Hunter, a simulator for waging war against UFOs was revived and released to the public.

Our consultant getting accustomed to the simulator
Our consultant getting accustomed to the simulator.

Since the future of humanity rests on the shoulders of this simulator and spacex, we have called back one of our most important assets (a veteran from future wars carefully regrown from DNA retrieved in the Artifact) to perform a thorough test of the simulator.

The force awakens

In the spirit of Shi Qiang, Lou Ji and Thomas Wade, we at BitBreeds have declared for the humans. Like our spacex and UFO Hunter friends, we have set our sight on the stars, and we are going for the goal.

What will you do?

Webtorrent; we get signal.

Lately I have been looking into WebRTC which is an open standard for real time communication between browsers. It allows communication styles in the browser which previously were not possible.

WebTorrent uses WebRTC for a protocol similar to bittorrent. Instead of having to download a program or install a browser plugin, you can download a webtorrent (which currently must be seeded as a webtorrent, by forexample instant.io) directly in the browser.

To test Webtorrent, I made a small javascript project. WT-widgets, is a collection of graphics for starting webtorrent downloads and showing download progress. Below is an example where you can download Artifact for Mac OS X using webtorrent.

No seeds

If there are no seeds, you can seed the file yourself by visiting the differently styled button below. This button uses a feature of WT-widgets that does a fallback to XMLHttpRequest after 5 seconds. When it is finished downloading the file, it will start seeding. Then the first button should work, since there is a seed.

The file will be downloaded in your browser, and you can then copy it to your filesystem by clicking the link that appears when the file finished downloading. This does not follow the usual download flow, so one of the aims of WT-widgets is to ensure that it clear to the user that a download is happening. I am not sure how well my widgets succeed in that regard, as my current widgets might not be the best at communicating that there is a download happening.

Suggestions or pull requests with fixes/additions are always welcome. I hope to expand WT-widgets with some widgets that show progress horizontally, as well as some widgets that more clearly show when it is in the different states of a download.

What Webtorrent sorely needs

While seeding in the browser works great, I do not want to have a browser fired up at all times to ensure there are seeds for my content. The best option I found for seeding webtorrents was webtorrent-hybrid, but when I tried it, I sadly could not get it to build.

Once Webtorrent has a solid solution for server side bootstrap seeding, I think it is will become a great alternative for distributing some kinds of content.

Take off every ‘ZIG’!!

Artifact 1.0.2.1 – Fixing OS X level 10+ crash

The obligatory level 10 death

For some reason Artifact-1.0.2 would crash on level 10+ on some OS X installations. This seems to stem from some issue with my LWJGL version, the bundled JVM and those OS X installations.

Artifact-1.0.2.1 includes a later JVM which seems to work in my tests. If you experience any issues with it please report using the address here.

Download Artifact-1.0.2.1 for Mac OS X