#GameSpotlight

[indievoices]

Game Spotlight: A Short Hike

If you’re looking for a heartwarming indie game that perfectly blends exploration, relaxation, and representation, look no further than A Short Hike. Developed by Adam Robinson-Yu, this charming adventure has captured the hearts of players since its release, and for good reason.

Overview

In A Short Hike, you play as Claire, a young bird exploring the beautiful island of Hawk Peak Provincial Park. Your goal is simple: climb to the top of the mountain and enjoy the view. But as you wander through the lush landscapes, you’ll encounter a diverse cast of characters, each with their own stories and quirks. The game’s open-world design allows for a relaxed pace, encouraging players to explore and interact with the environment.

One of the first things you notice is the vibrant art style. The island is a mix of rolling hills, shimmering lakes, and quaint campsites, all rendered in a soothing palette of soft colors. It’s a place that feels inviting, where you can easily lose track of time just wandering and enjoying the scenery.

Why It Resonates

What makes A Short Hike special is its subtle yet meaningful representation of diverse identities. While the game doesn’t explicitly focus on LGBTQIA+ themes, it creates a welcoming space for all players. The characters you meet throughout your journey reflect a variety of backgrounds and experiences, making it easy for anyone to find a piece of themselves in the story.

One memorable encounter happens early in the game with a character named Judy, who runs a small shop. During your conversation, she shares her own dreams and ambitions, hinting at her struggles to find her place in the world. This moment serves as a gentle reminder that everyone has their own journey, and it’s okay to seek support and connection along the way. It’s these little interactions that make the game feel inclusive and relatable.

Another significant character is a fellow hiker who you meet at a lookout point. They share their own experiences of feeling lost and uncertain about the future, which resonates with Claire’s own journey. This exchange highlights a common theme in the game: the importance of community and the shared experiences that bind us together. It’s a reminder that no one has to navigate their path alone.

Gameplay and Aesthetics

The gameplay is relaxing and non-linear, allowing you to explore at your own pace. You can collect items, chat with fellow hikers, and even take part in mini-games along the way. For example, there’s a fun fishing mini-game where you can try to catch different types of fish in the sparkling lake. These little activities break up the exploration and add a layer of enjoyment.

One of the most enjoyable aspects of the game is the freedom it offers. You’re not forced to complete tasks in any particular order, which allows for a more organic gaming experience. You might find yourself climbing a rocky outcrop just to see what’s on the other side, or taking the time to help a character find their lost item. Every interaction feels rewarding, as the game encourages curiosity and creativity.

The art style is delightful���soft colors and simple shapes create a cozy atmosphere that draws you in. Each area of the island has its own distinct feel, from the serene beaches to the dense forests. The soundtrack is equally charming, featuring soothing melodies that enhance the sense of tranquility. It’s the perfect backdrop for a leisurely gaming session, making it easy to unwind and immerse yourself in the world.

Themes of Exploration and Identity

At its core, A Short Hike is about exploration—not just of the island, but of oneself. As you guide Claire on her journey to the mountain’s peak, you’re also encouraged to reflect on your own experiences. The game subtly touches on themes of identity, belonging, and personal growth, resonating deeply with the LGBTQIA+ community.

As players, we often seek representation in the media we consume. Games that reflect our experiences help us feel seen and validated. While A Short Hike doesn’t overtly address LGBTQIA+ issues, its inclusive environment allows for a sense of belonging that many players crave. The game embraces the idea that everyone’s journey is valid, regardless of how different it may be from others.

This is particularly evident in the way the characters interact with Claire. Each one has their own story and struggles, and the game emphasizes the importance of listening and connecting with others. This theme of empathy is essential, reminding players that understanding and support can come from unexpected places.

Community and Connection

In today’s world, where many of us face challenges related to our identities, A Short Hike serves as a gentle reminder of the importance of community. The game encourages players to engage with the world around them, fostering connections that can lead to personal growth.

For example, one character, a fellow hiker named Frank, is trying to finish a race. He expresses his anxiety about whether he’ll succeed. When you help him find items he needs for the race, he opens up about his fears and insecurities. This interaction not only aids your progress in the game but also deepens your connection with Frank. It’s moments like these that illustrate how supporting one another can make a difference, both in the game and in real life.

Personal Reflections

As I played through A Short Hike, I found myself reflecting on my own journey as a queer gamer and writer. The game’s exploration of identity resonated with me, reminding me of the struggles and triumphs I’ve faced in my own life. There’s a particular comfort in playing a game that allows for self-reflection without judgment.

In many ways, Claire’s adventure mirrors my own—navigating the landscape of identity, seeking connection, and learning to embrace who I am. It’s a powerful experience that transcends the screen and prompts meaningful introspection.

Final Thoughts

If you haven’t played A Short Hike yet, I highly recommend giving it a try. It’s a game that encourages exploration, self-discovery, and connection—elements that resonate deeply with the LGBTQIA+ experience. As we navigate our own journeys, it’s refreshing to see a game that celebrates the beauty of finding our way in the world.

So, what are you waiting for? Grab your controller, dive into this delightful adventure, and let the serene landscapes and heartfelt stories envelop you.

Have you played A Short Hike? What are your thoughts on its representation and storytelling? I’d love to hear your experiences!

Feel free to adjust any sections, add personal anecdotes, or expand on specific themes to make it even more reflective of your voice and perspective!

[thepixelchase]

Game Spotlight #3 - Catrap

Platform: Nintendo Game Boy Publisher: Asmik Year published: 1990 (JP, NA)

This series of posts is about introducing interesting games that made it from Japan to North America but not to Europe. Today’s exhibit has more to it that a portmanteau in its title. Cats and traps indicate that we are dealing with a puzzle game. But you also have to guide the avatars - antropomorphic cats - past obstacles, so to be precise, this is a puzzle-platformer game.

The goal in any of the 100 levels that the game offers is to eliminate all enemies. But your avatar cannot jump (probably just ate a big can of tuna) and you have plan your route through the level carefully, using ladders and pushing boulders. Thus far, nothing revolutionary. In a regular puzzle game, you usually have to restart the level if you find yourself unable to continue. But in Catrap, you can actually rewind time - you hold a button and see your avatar and the environment moving smoothly back through the sequence of actions you performed, and you can stop any time.

Time rewind mechanics are technically complicated, and didn’t make their way into mainstream games until early 2000s. The most memorable title is Prince of Persia: Sands of Time (2003), where you can use the scarce resource of Sands of Time (duh) to get yourself out of dangerous situations and reach new areas.

[robotsgohome]

Game Spotlight - Blood Bowl (Part II)

*rides back with big bag of explanations*

Where were we?

Discussing the rather excellent Games Workshop game Blood Bowl, in the form of a contrived fictional narrative.  I figured it was a more accessible format than dry section headings.

Fair enough.

I'd already outlined the search structure I was planning on using for a hypothetical Blood Bowl AI (multi-agent distributed system solving unit subproblems, coordinated by a "team agent"), and now I've come back to fill in the admittedly gaping hole in my argument - namely, the magic evaluation function, which will return a single number representing how "good" a given game state is for the active player.

Yeah, that was super handwavey. You do realise that any search problem in AI can be solved by a sufficiently accurate evaluation function, right?  All you do is say all states on the victory path are worth "1" and all states off the path are worth "0". It doesn't mean anything.

True - which is why I'm now going to outline an actual implementation. The trick with evaluation functions is making them general enough that they're easy to compute while making them specific enough that your chosen search process can use them in place of searching a subgame tree.  They're meant to be rough calculations that approximate how good a given state is.

There are two main ways to come up with these:

Learning Given enough examples of good and bad gamestates (supervised learning) or enough playthroughs to completion (unsupervised learning), it's possible to learn an evaluation function.  The easiest way to do this is to have your scoring algorithm already designed and just use the learning process to tighten weights on various components, but this requires you to design the scoring algorithm (a fair amount of work in itself).  Alternatively, you can throw the problem at a more general algorithmic framework (say, a neural net), and use the learning process to adjust the computation as well as the weights - however, this process is very slow, and gets exponentially slower the more "resolution" you require from the function.  For Blood Bowl, I'm guessing we'd require a lot. Learning processes are also problematic in that it's usually very difficult to discern why they think a certain state is good - the evaluation function generated is typically quite opaque and relatively immune to tweaking.  If after all this brute force offline computation you come up with something moronic, it's going to be hard to turn that into something good without restarting the entire process. As an analogy, it might be helpful to consider biological evolution. It's a very powerful unguided optimisation process that can come up with really sophisticated organisms (most humans), but it takes millions of years to do so for a specific environmental niche (and billions of years from the dawn of life to where we are today). Learning algorithms are a step above this, but they're still slow. It would be helpful if there were an alternative...

Intelligent Design Automated learning is attractive because (in theory) it saves you having to think about how an evaluation function should work - you barely even have to know anything about the domain you want it to evaluate.  The obvious alternative is to use expert knowledge of the domain to come up with a good evaluation function yourself - this is both considerably more fun and considerably more illuminating, as you can see exactly why certain choices were made and adjust them on the fly dependant on performance.  If we're ingenious enough, it should be faster to create a good function than to evolve one.

Because "point a learning algorithm at it" is almost as much of a non-answer as saying there's a "magic evaluation function", I'm going to try the latter approach.

So what should this "intelligently designed evaluation function" look like?

Crafting a good function for a complex game such as this is not going to be easy.  To do it properly would require some combination of mathematical analysis and trial-and-error iterative improvement.  I don't have the time or inclination to do either right now, so what follows is where I'd start.

(I should also warn you that I don't really have space to explain the rules of the game in detail, so I'll try to write in more general terms - it's the methods I'm using that are important.  If you want to refer to the rules anyway, they're available here.)

I'll begin by observing that the problem isn't simple enough for us to pull a fully formed function out of thin air - so we should do what we always do in this situation, and decompose the problem into a number of subproblems, solve those, then recombine the answers in a way that seems sensible (perhaps as a linear combination, or possibly something more involved).

For Blood Bowl, the first decomposition that naturally presents itself is to consider the score of a single team rather than both teams at once.  The overall evaluation function would then be the "team score" for the active player minus the "team score" for the opponent.  Due to the symmetry of the game, we only have to construct one such function (which is team-independent), and we can explicitly ignore things which are good for our opponent when calculating what is good for us, as this will be contained fully in the other component. With this in mind, my second-level subproblems (decomposing the "team score" problem) are these:

Overall Goal Satisfaction I'll start with an easy one.  Touchdowns should be worth a significant amount each, so that the AI is incentivised to make them if they're immediately available while not being tempted to perform risky actions beforehand.

Unit Score What is a unit worth when active (upright)?  What is the same unit worth when stunned or prone (temporarily incapacitated)?  What is that unit worth when removed from the board?  OK, that last one's easy - we'll say it's worth zero - but the first two questions aren't as clear cut. Having a function that spits out a unit's current worth is useful because we can plug this value into other functions, allowing us to see which opposing units are worth blocking or which of our own units are worth protecting.  In addition, the sum of all unit scores will probably be a valuable component in the overall evaluation function in its own right, as it (roughly) represents ability to act. You could approach this from the complex end and say that this depends on a variety of factors including board position and proximity to other units.  I'd prefer to keep things simple and incorporate the complex stuff as functions of a basic unit score, rather than the other way around.  Let's say my initial guess will assign a score equal to the units cost, reduced by some scalar for stunned/prone states, and increased by some scalar for carrying the ball (as this is a state that's easily determined).

Combat Advantage Half of Blood Bowl is about beating up the opposing team or preventing the opposing team from beating you up.  Hitting units successfully incapacitates them either temporarily or permanently, which results in less options available for their controlling player. It's worth examining what the simple "sum of unit scores" would incentivise with our current search model - we're not looking far enough ahead to chain together multiple unit actions, so the AI won't see that it can move units into positions where they can assist other units.  All it would do is identify the best immediate block actions (or lack thereof). A better model would take into account the quantity and quality of block actions available for the active team.  Consider the set of all block actions available to all allied units on the board.  These can have one of four real outcomes: {defender down, attacker down, both down, neither down}  (I'll ignore pushbacks for now - assume they fall into the last category).  Each outcome will have an easily calculable probability associated with it, depending on the relative strengths and skills of the participants - including assists granted to them by neighbouring players - and each outcome will have an easily calculable score based on the resulting standing-up-ness of each participant.  We can blend these in the obvious linear combination to get a score for the block action itself, and we can sum these scores for all immediate block actions to get a heuristic for combat advantage. This has immediate advantages because it considers the effects of assists on the block actions.  Positioning is now important - units should see the advantage of moving to provide assists on otherwise unfavourable blocks.  The AI would also be able to see the effect that removing an opposing unit would have on future combat advantage via simulation, which should allow it to order its block actions correctly (i.e. performing a series of favourable blocks, each removing critical opposing assists to make the next block more favourable).

Positional Defense The primary factor restricting movement in Blood Bowl are what are known as "tackle zones" - essentially, every square adjacent to an upright unit.  Opposing units in these squares suffer a penalty to perform agility-based actions, and they have a chance to be tackled (fall over and drop the ball) when moving out of them.  (The secondary factor restricting movement is through blocking off certain routes with actual units, but due to the relatively few units compared to available board space this comes up less often) Imagine that each square on the pitch has a value associated with it, representing how much "power" this team can safely move there (let's call this "influence", as in influence mapping, which is essentially what we're doing here).  If such a map existed, then one way of determining defensive strength is to ensure that the opposing team doesn't have a large influence in your half of the pitch, as this would correspond to great freedom of movement here.  Similarly, your team does want a large influence in your half of the field, as this means you can respond quickly to incursions by opposing units trying to score a cheeky touchdown.  Units in high zones of opposing influence are more at risk of being surrounded and blitzed. We can approximate this by using a diffusion process.  For each unit, we'll iterate the following process a number of times equal to their movement stat:

Starting with their full influence value on the square we currently occupy, consider all adjacent squares - give these influence equal to the influence in the source square multiplied by the success rate of moving there. For subsequent iterations, consider all squares adjacent to those already visited, and perform the same operation (choosing the maximum of the values for repeated visits).

The overall "influence map" would be a linear combination of these, weighted by (presumably) offensive power.  Admittedly, this process is likely to be quite costly - further approximations may need to be made to actually get this usable - but I think it's the right principle. As stated above, a good defense entails making sure your opponent doesn't have too much of an influence advantage in your half of the pitch.  This can be reduced by keeping units deep in your half with complete freedom of movement, or by positioning and moving units such that the freedom of opposing units is reduced in some way (either by directly putting them in tackle zones or by creating a "wall" of tackle zones to dissuade movement along a certain path).

Positional Offense Finally, how do we lead the AI in a direction that will result in it scoring touchdowns?  The above "goal satisfaction" component will result in it taking immediate touchdown actions, but we need to incentivise moving towards such a state even if it's not visible in the immediate future. We need a function that increases the closer the ball is to the opponent's endzone, and increases further if held by an allied player.  From the influence map calculated above, we're aware of how risky certain squares are, so we should take this into account as well (for both loose ball position and held ball position). In a vacuum, this should result in the AI picking up the ball and moving it closer to the opponent's endzone safely, by either fast movement or passing into zones of low opposing influence.

Together, I believe these components encompass the main strategic elements required to play an adequate game of Blood Bowl.  All that's left is some way of combining them - my gut feeling says a linear combination of the above would work, with appropriate component weights.

Is that it?  Are we done yet?

That concludes my general outline of constructing an AI to play Blood Bowl.  I hope it was informative, and not too confusing. I'll stress again that this was an entirely theoretical adventure, and that actual implementation and experimentation would be needed to refine the above into something actually good - but I'm still very open to suggestions on how to improve this or for people to point out obvious flaws in my reasoning.

Blood Bowl is a fairly nice self-contained coding project, so it's not inconceivable that I'll actually get around to trying this out at some point.  If I do, I will definitely post about it here :)

[thepixelchase]

Game Spotlight #2 - Super Mario RPG

Platform: Super Nintendo Entertainment System Publisher: Nintendo Year published: 1996 (JP, NA)

Super Mario RPG can be viewed as an attempt to introduce the genre of roleplaying games, popular in Japan but obscure in the United States, to the Western audiences. Mario was a family friendly character with solid reputation in the USA and while it has been used to market other genres (mainly sports), creators had to be very careful not to make Mario a brute that obliterates his enemies. Magic, a staple in the RPG genre, also had to be dealt with. While Mario, Bowser and Peach are all playable characters (they use their trademark moves - Mario’s fireball, for example), two new characters of clumsy Mallow and mysterious Geno were introduced as major spellcasters.

The game presented from the isometric perspectivewas praised for its stunning visuals. Some of the finest 2D graphics in gaming period were made possible by the integration of an additional computing chip in the game's cartridge, a treatment that only seven games outside of Japan got.

Source: http://usebu.forumactif.org/t1255-tuto-super-mario-rpg-en-francais

Ironically enough, the game was released much earlier on the European region of Nintendo's Virtual Console service for Wii and then later for Wii U, even though it was never physically in Europe. Super Mario RPG was a succesful effort and even though it never recieved a direct sequel, two lines of Mario RPGs followed that still receive new games as of today. 

[thepixelchase]

Game Spotlight #1 - Faceball 2000

Platform: Nintendo Game Boy Publisher: Bulletproof Software Year published: 1991

Faceball 2000 is a technical marvel. First released on the Atari ST platform in 1987, its authors later ported it to a more restricted platform - the original Game Boy. Starting with Wolfenstein 3D in 1992 the first person shooter titles were used as an exhibit to show the ability of both its authors and the platform they were released on. The tricks of displaying 3D graphics, level design and control schemes were far more complex than the requirements of any other genre. But one of the most impressive titles came out before the genre was defined by Wolfenstein 3D. 

Game Boy had a 4.19 MHz processor and 16 kB of memory, 8 kB for the code and 8 kB for graphics. I’ll let you do the math comparing it to your smartphone yourself but to put it in perspective, mid-tier IBM-compatible PCs sold in that time were sold with 1 MB of RAM. Faceball 2000 not only ran on Game Boy, it was also a good game. As banal as it sounds, this is an important distinction nowadays, when we have Windows 95 running on Apple Watch and Half-Life 2 on Android devices. Proof on concept is nice but playing retro games on your phone with virtual keyboard can be a rather frustrating experience. Sure, you can semi-legally get thousands of games on your phone in a matter of minutes but do you want to? It's just not the same as playing with physical controls on Nintendo's Virtual Console service (compromise) or go all-in retro and ensure yourself the original experience. Nice for some, necessary for the growing group of people who study video games as socio-cultural phenomenon or their relation to the hardware platforms.  

Faceball 2000 in theory supports 16 people multiplayer. A 16-way link adapter was supposed to come out but never did. Passionate fans figured out that you can chain seven 4-way adapters and connect 16 Game Boys with 16 original copies of Faceball 2000. One person was last heard from when they collected enough hardware to connect 14 players. The dream lives on!

[robotsgohome]

Game Spotlight - Blood Bowl

[[ Huh. It's been a while. *blows dust off blog*  Recent events in my life have made updating...less of a priority...but hopefully things will get back to normal soon (for both me and this blog).  I'll probably post about this at some point (believe it or not, it is tangentially AI related). Until then, more content! ]]

I recently read this article on the BBC News website about the game Arimaa, deliberately designed to give (then) current AI techniques a hard time. Despite there being a hefty cash reward for the first bot to beat a human master, this has so far been unclaimed, despite considerable work.

This was the first time I'd heard about the game, and I've yet to play it or familiarise myself with the current research, so to comment further on it would be fairly pointless. As far as I can tell, the main difficulty with using standard techniques is the huge branching factor - the game superficially resembles Chess, except that every turn, the active player has four "action points" that can be divided among the pieces they control to move them in any of the four cardinal directions or to push other pieces around. Whereas Chess has an average branching factor of 35, Arimaa has around 17000, which limits the practical depth the game tree can be searched.  In addition, the starting arrangement of pieces isn't fixed, with a large number of options (64 million per player), which means an AI can't learn an "opening book" of good starting moves.

I am, however, familiar with another game that also has a variable opening state and massive branching factor - the Games Workshop classic Blood Bowl.

I'm too lazy to click all your links. What's Blood Bowl?

Blood Bowl is a two-player board game representation of American Football if played by the fantasy races from the Warhammer universe. In gameplay terms, it's a cross between the stochastic wargames that provide its flavour and more abstract strategic perfect-information games like (*sigh*) Chess. Though better than that sounds, because wargames and Chess are both awful.

It was originally released in 1987, and has been revised and re-released multiple times. The rulebook is now freely available online, and you can still buy boxed versions (or at least you could a couple of years ago). It's also spawned a successful video game adaptation (released in 2009), which is soon getting a sequel.

Each player controls a team of eleven units chosen from one of the Warhammer fantasy races (Humans, Orcs, High Elves etc.).  Each race has a variety of unit classes to choose from, each with different base stats (Movement, Strength, Agility, and Armor) and skills (Dodge, Pass, Block etc.).  Some races and classes are suited to the actions of passing and movement.  Others are more suited to the actions of hitting and maiming.  Either approach is valid, and the interaction between the various unit types is a significant part of the gameplay.

The game takes place on a rectangular grid (the "pitch"). Each team sets up their units in their half of the pitch mostly however they like (with a few restrictions). At the start of the game, the "football" piece is placed semi-randomly on the board. The aim of the game is to score the most "touchdowns" in a fixed number of turns, which is the act of transporting the single football into the opposing team's "end zone".  

Each turn is a lengthy affair for the active player only, which isn't the best design - but hey, this was 1987, and it's still better than the downtime in Warhammer where turns take half an hour.  The active player picks a unit, then performs one of the following actions with that unit:

Move The unit may move a number of squares equal to their Movement stat.  While usually safe, if moving out of squares adjacent to opposing units, they have a chance to get tackled and fall over, especially if they're clumsy (e.g. Dwarfs).  If moving over the ball, the unit may try to pick it up.

Block The unit may attempt to hit an adjacent opposing unit, with success depending on the difference between each unit's Strength stat and the number of nearby units who are able to "assist" (correctly managing assists is a key part of the game). If a unit is hit, it's at least stunned for a turn, and may suffer more grievous injuries depending on its Armor stat.  A unit cannot move and block.

Pass This is identical to a move action, except at the end of it the unit can pass the ball if they're holding it. Like all ball related actions, the success of this depends on the Agility stat, as well as nearby opposing units, distance to target, and so on.  If the ball is passed to an occupied square, that unit will attempt to catch the ball.  Only one pass action may be made per turn.

Blitz This is identical to a move action, except at the end of it the unit can block an adjacent opposing unit (so, "run up to someone and hit them").  Only one block action may be made per turn.

If the action is successful, the active player can then pick another unit that has yet to do anything this turn and perform another action.  If any part of a unit's action fails - say, by being tackled, or fumbling the ball - the turn immediately ends, and control is passed to the other player.

This is essentially the entire game - everything else is just detail.

So is it fun?

I think so.  Admittedly, I was introduced to this way back in the mid-90s when I was into wargaming (I was such a cool kid), and the simpler mechanics and quick turn time was a real breath of fresh air that other games didn't provide.  I have played it a couple of times in the last few years, though, and under a more critical eye I think it still holds up.

The main advantages are that it's a good two player game (which are relatively rare) with a considerable depth of strategy for a relatively simple rules cost (i.e. it has elegance).  The random elements to the game fuzz any skill gap between players, making it accessible.  And at the end of the day, you're playing American Football with Orcs, which is cool.

There are problems, however - the most significant of which being the fact that turns don't involve the other player and can take 5-10 minutes to resolve.  A more modern take would have more interleaved play to get around this.  Another problem is the sheer number of actions available to each player (or even each unit) can sometimes be overwhelming, especially to players who like obsessing over the "optimal actions".  These can both be (semi) fixed by imposing an arbitrary time limit on turns, however.

(Other problems with the physical boxed copy of the game include the fact that it is miniature based, which means there's a setup cost in making each model indentifiable and team-aligned (you have to paint them), and that you don't have access to the full range of races/classes straight out of the box, unless you use proxies).

Still, it's worth trying - though maybe not buying unless you're sure you like it.

What if I'm a robot who doesn't understand football? Can I still play?

Hmm.  The evidence so far is "no" - or at least, not well.  Despite my apparent enthusiasm for the game, I haven't yet managed to play the video game adaptation.  I have, however, read a number of reviews of it, where the AI is generally called out as being poor - using the old staple of manipulating dice rolls and using more powerful units to represent "difficulty".

Having said that, this is the internet, and if there's one thing I've learned in gamedev is that fans will often report speculation as fact, so I don't want to pass final judgement on either the quality or cheatiness of the existing AI without seeing source code (which will never happen, unless I trip and fall into a Cyanide dev position, and if so I wouldn't be allowed to talk about it).  For now, it seems best to ignore it, as the existence or nonexistence of good Blood Bowl AI shouldn't affect my thoughts on how I would write such a system.

(I'll also mention that like any popular game there are a number of homebrew AI attempts out there as well, which I haven't checked for quality. My approach is informed conjecture rather than the results of actual experimentation, so it's clearly possible someone out there has cracked this.  If so, they should probably publish - as demonstrated by Arimaa, this kind of AI problem is fairly open).

So.

The first thing to notice is that the number of composite actions (unit_a: move{N,N,NE,E,E,S}; unit_b: move{W,SW,S,S}; ...) available to a player in a turn is very, very large - and there are an even greater number of possible outcomes (thanks to all the randomness).  This is the branching factor alluded to above, and it blows Arimaa out of the water.  This means standard tree search techniques (and I'm including MCTS in this) almost certainly won't work when applied to the raw problem.

Thankfully, the randomness contained within the game comes to our aid here - we can't predict the future exactly, so it matters less how far we can see into the tree.  In fact, I don't think we need to consider the opponent's next turn at all, as long as we have a sufficiently accurate evaluation function to represent the worth of a given gamestate.

The correct way to approach such seemingly insurmountable problems is the good old divide and conquer strategy - break the mega-problem down into smaller problems, and break those down into even smaller mini-problems, ... and so on, until you reach components that you can solve.  Recombination of all the mini-solutions should give you a mega-solution - any large-scale strategies should emerge from this, rather than somehow concocting a large-scale strategy to dictate the individual mini-actions.

In the case of Blood Bowl, the immediate division that springs to mind is splitting the "team" problem into a problem for each "unit" - if this unit were next to move, what should it do?

This is known as a multi-agent approach - you're essentially delegating the overall problem for the "team agent" ("what should the player do next?") to a bunch of independent "unit agents" ("what should this unit do next?").  Once the unit agents come up with their best answers, the team agent then has the much simpler decision of choosing a unit agent's plan to execute, of which there will be at most eleven.  The problem has now been reduced*.

So what should a given unit do next? Unless a given unit can, without any risk, score a touchdown this turn, then it has to somehow consider the ramifications of its actions in relation to the actual goals of the game (scoring touchdowns).  There's less of a branching problem for individual units, but at the start of a given player's turn there's still a lot of unit actions/outcomes between now and the next touchdown, and it's still not going to be feasible to search them to this depth (let alone consideration of properties that persist between touchdowns, such as unit alive-ness).

For now, let us assume the existence of a magic evaluation function, that looks at a given board configuration and says how good it is for the active player - this will account for things like "opposing unit with ball near my end zone" as a bad thing, and "opposing units mostly unconscious" as a good thing.  At some point we'll need to implement it, but that's once again a separate problem (dividing, ready for the conquering).  For now, it works using some combination of pixies and quantum energy auras.  Just go with it.

A given unit, then, now has the much easier problem of "what should I do to maximise the magic evaluation function?".  It has a manageable amount of possible actions it can take, and should be able to search these with some clever forward pruning (for example, there's a lot of places a unit can move to, but only a few that actually matter).  For the sake of efficiency, it might be better to look at destinations for the move actions rather than building up a sequence of individual moves - the feasibility of each destination can be evaluated later.  Similarly, as failed actions result in the turn immediately ending, it'll likely be worth assuming all actions that can succeed will succeed, and associate an appropriate amount of risk (the score for the plan should be the weighted average of all possible outcomes of the plan).

Once each unit agent has solved this sub-problem (or has hit its computation budget and has to hand in what it's got so far, sheepishly), the team agent then picks the best unit plan, executes it, and if it's successful kicks the whole thinking process off again from the new board state with the remaining unit agents.

Problem solved! Fade in music, lower lights, ride off into the sunset...

Whoa there, cowboy!  What about this "magic evaluation function" of yours?  I AM A CONSTRUCTION OF STEEL AND SILICON, I DO NOT BELIEVE IN FAIRIES.

Aw, shoot.

This function is very, very important.  The above process replaces the problem of "how do I win at Blood Bowl?" with "how should a given unit behave to make my function happier?".  This has to encode every aspect of the bigger problem, in a way that's easily computable (i.e. not tree searching for the answer, because that's clearly intractable).

As this function is very, very important, I want to devote sufficient time to describing it, which unfortunately means a post of its own.  I'll try to write this in the next few days, but now it is late, and I am hungry.

*rides off into the sunset before the fictional blog robot can stop me*

You'll never get away with this! TO BE CONTINUED...

*credits*

--------------------------------------------------------------------------------

* [[ If you're feeling particularly ambitious (and have a suitably efficient unit-plan planner), instead of unit agents you could have multi-unit agents that consider plans from n units moving sequentially (e.g. unitsAB, unitsAC, unitsBC etc.).  This would more naturally allow for sequential strategies such as "move A here, then B pass to A", but a sufficiently clever evaluation function might make this unnecessary.

I should probably also elaborate on the difference between this model and that of a single agent who has a search horizon of the end of the first unit's action (that also results in an initial "pick a unit" split, then a search, which is suspiciously similar).  In the multi-agent model, the team agent arbitrates between the plans of the unit agents - it doesn't just have to look at raw evaluation score, but can also factor in other things like "risk of turnover" and dependencies between unit plans.  It's solving a different problem.  More generally, a multi-agent system could allow the unit agents to communicate with each other while planning, though I doubt we want that here as that would prevent efficient parallelisation for (I think) little gain - though it's easy to imagine: an example could be a unit requesting support to take down a critical opposing unit, which adjusts the priorities of the other unit agents and triggers a replan. ]]

[robotsgohome]

Game Spotlight - Dixit

In the wake of last week's gameless AI post, I figured I'd switch back to looking at games for a bit. Not only that, but I'm going to distance myself as far as I can from the heavily analytical tree-search style of game as well - by discussing the 2010 Spiel des Jahres winner, Dixit.

What am Dixit?

Dixit is a card-based game for 3-6 players, and is played over a series of rounds - players will accumulate points each round and the player with the most points at the end of the game will win.

What differs from other card-based board games is that each card consists solely of an abstract picture, like these:

Each player has a hand of six of these cards, replenished after every turn. At the start of each turn, the active player (referred to as the "storyteller") picks a card in their hand, places it face down in the middle of the table, and says a word or phrase (referred to as a "story") that ambiguously describes that card. The other players will then pick a card from their own hands that most closely corresponds with the chosen story, and will place them face down in the middle of the table as well. The cards are shuffled then revealed, and each non-storyteller player simultaneously chooses the card they believe to be the storyteller's.

The tension comes from the scoring system:

If everyone guesses the storyteller's card correctly, everyone apart from the storyteller scores 2 points.

If no-one guesses the storyteller's card correctly, everyone apart from the storyteller scores 2 points.

Otherwise, the storyteller and the players that guessed correctly score 3 points.

(Non-storyteller players also score 1 point every time someone guesses their card)

This incentivises the storyteller to not make their clue too obvious, nor too obscure - perhaps by tailoring the story to target specific players (drawing on shared knowledge). Non-storyteller players are incentivised to match the story as closely as possible (as they get points if people guess their card), and to guess the storyteller's card to the best of their ability (as they get the most points if they hit).

All in all, this is a fun, family game that doesn't require heavy analytical thinking or a learning a ton of rules, but nonetheless has surprising depth.

What if I'm a robot who doesn't understand love? Can I still play?

Good question, fictional blog robot! Dixit has strong similarities with trivia games such as Articulate or Trivial Pursuit, in that the physical components of the game are only half the story - the knowledge and experience each player brings to the game strongly affects their ability to do well and the overall game dynamics.

Unlike trivia games, however, Dixit requires you to model your opponent's knowledge as well - as storyteller, you are pitching your story to a subset of the remaining players; as non-storyteller, you are pitching your decoy to all the remaining players, while trying to match the clue given to the cards in front of you based on how you think the storyteller would act.

Robots are traditionally not great at this type of thinking, although relatively recent successes such as IBM's Watson prove that it is possible, just a lot of work.

If I were to write a Dixit-capable AI right now, it would work something like this:

Assume all cards are known. This saves us having to worry about object recognition which is currently a tremendously difficult AI problem in its own right, let alone object recognition applied to whimsical French art. It's not really cheating as every player who's looked at the deck or played the game once will have the same advantage.

For each card, associate it with a cloud of 20-30 semi-appropriate words. This is imparting our expert knowledge into the AI. For example, the top left card in the image above could be associated with "cello", "woman", "music", "butterflies", "beauty" etc. The list has to be finite and short for memory/computational reasons.

For each card-word, for each other player, attach a confidence score from [0, 1] representing how likely you think that player is to associate the card with that concept. As we have our finite list of card-words already, this process can be done somewhat efficiently once opponents are known - though it still requires human involvement (for now). If this is impossible due to time/effort constraints, a similar list could be generated for player "archetypes" (based on age and cultural background) and opponents could be quickly classified into one (or more) of these categories. These card-word-confidence tuples (e.g. "WomanCelloPic, 'music', 0.8") collectively form a profile for each opponent.

As storyteller, the AI has six card options, multiplied by 20-30 card-word options. Based on the opponent models, one of these card/word pairs will have an average opponent confidence close to our target value (determined empirically through testing). Choose this pair, and play it. This is also based on what cards we believe each opponent to have - there's no point playing the woman&cello card and stupidly saying "cello" if no other card would remotely match that, but if we said "beauty" then there are several other cards that could conceivably match this, and thus we're more likely to get a split of guesses.

As non-storyteller, the AI has been presented with a natural language word or phrase, and has six initial options to play as a decoy. Google the phrase, then compare the relative frequency of card-words (compared to an average language baseline) with the top n search results, weighted appropriately using the other non-storytellers' profiles. Choose the card that best matches the phrase using this metric, and play it. When you don't have the resources to construct a huge knowledge base of all human culture, borrow one.

When guessing an image, once again perform the Google-frequency test on all visible cards, this time using the storyteller's profile to weight each card-word. Choose the card that best matches the phrase, and vote for it. This is just the same as the previous strategy, but using a more appropriate weighting.

Each round is effectively distinct, so there's no need to look ahead further than the decision in front of you. (Excluding the fact that you can adjust your opponent profiles based on how they've been playing, or that you can adjust the likelihood of them holding certain cards based on which cards have already been played - both achievable using Bayesian updating techniques, but the exact mechanism of which is beyond the scope of this short post)

This falls firmly on the Wisdom end of the I/W spectrum, because that's what the game has been designed to test. However, that doesn't stop it being interesting, as the above discussion has hopefully demonstrated.

I have no idea how this will play, and while I'm tempted to implement it I really don't have the time (tinkering as I am with tree search problems FOR SCIENCE). Comments, as always, are very welcome.