The now irregularly returning Sci-fi book review

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.

I also read The Expanse and Rendevouz with Rama, but they are both great, and well known to most, I do not really have anything to add.

Adrian Tchaikovsky – Children of time

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.

Martha Wells – The Murderbot Diaries

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.

Ann Leckie – Provenance

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.

Alfred Bester – The stars My Destination

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.

Alistair Reynolds – Revelation Space

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.

Yoon Ha Lee – Ninefox Gambit

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.

Kim Stanley Robinson – Aurora

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.

Cixin Liu – Three Body Problem trilogy

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

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…

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

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?