I have been hacking on some libcamera experiment, and this time I had the misfortune to have to try and use a Jetbrains product in a local VM and on the host system at the same time.
Since it is practical I was using UTM shared networking, but that had the unfortunate side effect that Clion in the VM and IntelliJ on the host detected each other and refused to both be open at the same time. Incredibly annoying…
Googling I figured out that if you use the same username in the VM and on the host it will all work out. I got more and more confused as to why this feature exists, but a glimmer of hope emerged. I was not ready to change user in the VM or on the host though, since I had used some time to set up that user.
Thankfully, this detection feature uses the JVM system property user.name, to lookup the user, so adding -Duser.name=<host username> to the clion64.vmoptions file made it all work out.
I really like that the constraints for this format are so simple. It is easy to make a format that is fresh, but where the constraints are complex. For some reason such complex constraints make a format feel inelegant and less appealing to me.
My expectiminimax based solution works well for a game with random elements and perfect information, but it is not very useful for a game with imperfect information. Get1000 is played simultaneously by the players, and the opponents choices are hidden until the end of the game.
This meant I had to go back to find a new strategy for solving the game. I decided to try and find the correct brute force way first, and then see if that could be made faster in some way.
Exploring brute force
A solution to the game involves finding a Nash equilibrium from all the pure strategies of the game. A brute force solution could be done by creating a matrix where all pure strategies are pitted against all the other pure strategies.
A strategy here refers to a function which given any game state gives a Get1000 placement . Below is an illustration of what i mean by a state. A state could also include the history (order of placement), which would increase the count a lot, but that is hopefully not needed for a solution.
A gamestate can be represented as the current number (in this case 1), the entries in hundres (7), tens (5) and ones (12) as well as the amount of free positions for hundreds (1), tens (2), ones(2).
The total amount of such states is but in at least the choice is forced. This means there are at most. relevant states, probably quite a bit fewer.
Each state has at most 3 choices, therefore there is an upper bound of unique pure strategies.
This is of course not that helpful, since a matrix is enormous, and for each cell in the matrix all possible games would have to be played to find the payoff for the pure strategy pairs. On top of that, the best mixed strategy would then have to be calculated.
While this sounds straighforward in theory, I found it quite hard to figure out where my information sets are, and whether I could consider each choice node in Get1000 a subgame. After struggling for a while, I ended up with an extensive form structure looking like this. Players are P1 and P2, and “move by nature” is the dice roll.
This structure means that only the roots of the tree are subgames, since all other nodes are part of larger information sets.
Attempting backwards induction
The above structure means that it is not practical to naively use subgame perfection and backwards induction to solve the game, but taking inspiration from it could still be useful to get a good strategy.
The algorithm for subgame perfection goes like this:
Consider the final subgames (those with no further subgames), pick a Nash equilibrium as solution there.
When considering the next subgames up the tree, the payoffs in the subgames already considered are used to create the payoff matrix.
Iterate step 2 until the root node of the extensive form tree is reached.
To get something working, I pretend that the other player is at the same state as me always. This means I can only focus on the branches below that state. To keep memory in check i also recalculate payoffs instead of storing the result for each combination of states and games. The final algorithm I ended up with works like this:
Consider the final subgames and pick a Nash equilibrium as solution.
When looking at subgames higher up the tree, I use the choices (not payoffs) computed in 1, and use those choices to play out the game. Then I compare end results to get the payoff matrix for that subgame.
As before, I iterate step 2 until I reach the root node.
This seems intuitively pretty reasonable.
The above method gives me a strategy that partly takes the imperfect information nature of the game into account. At many states it detected mixed strategies that had much higher payoffs compared to the pure versions. The strategies smashes all my previous best strategies by winning 1.75% more games.
At this point, I was not really sure how to approach the game in a better way. In fact I was pretty ready to admin defeat for quite some time. Of course, immediately after i wrote that, I found this thesis, and this report.
Following this post, this contains a review of the sci-fi books I have read lately in no particular order. Book explanations are very light on purpose, since I do not want to spoil the books.
The TLDR: The books I enjoyed the most of this batch, were Cixin Liu’s Three Body Problem books. The last two books in the series are not an easy read, but they are worth it, and I enjoyed them despite inconsistent pacing, and huge differences in style and scope.
The last humans leaving a dying Earth reach a terraformed planet with a spider civilisation which has been helped along by a human scientist. We follow the spiders as their society advances, and the humans as they struggle to survive.
The book was a quick read. I enjoyed the chapters following the Spiders quite a bit, and the humans as as much. The book reminded me quite a bit of Vernor Vinge’s A Deepness in the Sky.
A security bot (an android overseeing a science expedition) has broken out of the system that constrains its behaviour. As a rogue bot it tries to keep to itself, but that becomes more and more difficult as the expedition makes some unexpected discoveries.
Very quick read. Mostly fine, but I feel like it resorts to breaking into systems as a quick fix for most problems encountered. This gets very predictable and feels too easy a lot of the time.
A sci-fi mystery, set in the same universe as Ancillary Justice. It explores inheritance, culture collisions, and planetary and interplanetary power struggle from the perspective of a very small player Ingray who has taken a huge gamble to become heir to her adoptive mother.
I enjoyed this. A turn to local small scale politics compared to Ancillary Justice/Sword/Mercy and not as memorable as those books.
Interesting exploration of a society where teleportation (jaunting) to anywhere you can visualise within a certain distance is possible. It follows a man who was marooned on a spaceship, and who when saved goes after the crew of the ships that left him behind.
Well pulled off. In general I think abilities like jaunting are a bit too powerful, and typically lead to silly logical problems very easily. The Stars my Destination, probably has those, but they are not very apparent.
Revelation space is a galactic scale space-opera where we follow the Lighthugger ship Nostalgia for Infinity, which Ultranaut crew is looking for someone to treat their captain from an illness. That someone is an archeologist studying the death of a long dead race called the Amarantin on the planet Resurgam.
Solid space-opera on a galactic scale. Contains an interesting explanation for the Fermi Paradox.
Explores a universe where technology is based on populations following specific patterns. In the society we follow, their technology is based on the populations belief in the imperial calendar and the associated culture. Calendrical rot (heresy) must be avoided at all costs.
Very hard to follow initially, and sometimes very confusing, but I sort of enjoyed it. It was very hard to tell if it is consistent with itself, since the concepts are so foreign. I think I have to read it again to form a better opinion.
Humanity has sent an expedition (generation ship) to a possibly habitable planet around Tau Ceti. The mission is to colonise this planet after traveling for more then a hundred years. We follow the humans and the ships AI as they struggle to survive on the way.
Robinson writes in his very (maybe overly) detailed style, with lots of details on environmental systems and specific challenges faced by the biomes on the ship. In some cases it works well, in others it feels a bit like the author researched this, and so it has been put in regardless if it fits or not.
It is hard to write anything about this book without spoiling too much. In the first book, we initially follow a Chinese police officer as he investigates the deaths of several scientists. These are connected to interstellar messages sent by a astrophysicist several years earlier.
The next two books follow up on the events of the first, but they are very different. The scope increases a lot as the books go on. The trilogy (especially book 2 and 3) is quite critical of human society, and explores how we fail to make good collective decisions as a species. It is mostly ok reasoned and well integrated in the story, so it never feels out of place.
The series is great, and I recommend it to everyone. Some parts are a bit slow and feel very obscure at first, but they are well worth the payoff.J
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.
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.
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).
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.
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.
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.
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:
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.
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.
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.
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.
192.168.1.100 58713 – Your offered address and port.
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.
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.
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.
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.
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.
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.
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.