Category Archives: Game Development

Permute Update: Now available in Ai Ai!

Since my first post on my game Permute, there’s been a very exciting development.  Thanks to the efforts of Stephen Tavener — thank you, Stephen! — Permute is now playable in his wonderful abstract-gaming mega-package Ai Ai!

Ai Ai is a fantastic, and free, collection of many dozens of excellent abstract games, all playable online or against various strong AI opponents.  I’ve talked about it in my Connection Games series a few times, but I can’t emphasise enough how essential it is if you have any interest in this category of games at all.  Ai Ai includes everything from classics like Go, Chess and Draughts, to modern legends like Amazons, Havannah, Symple, and Catchup.

Ai Ai is particularly great if you like to experiment with games.  The platform is incredibly robust, and with some simple modifications to the MGL files that define the parameters of each included game, you can try out ludicrous variants of your favourite games and Ai Ai takes it all in stride.  As you can see in my post on Symple, you can play games on ludicrously large boards if you like, or modify starting positions, and so on.

Even better, Ai Ai is festooned with super-interesting analysis functions that you can use to investigate all the included games.  You can generate opening books and endgame puzzles, produce detailed statistics on game complexity, create detailed reports on branching factors throughout a typical game, and much, much more.  I used Ai Ai to generate a full report on Permute, which Stephen has uploaded to the Ai Ai website here.

A big part of the reason I was so excited to have Permute in Ai Ai is because of these analysis functions.  While my initial testing of Permute showed that the game is fun and allows interesting strategies to develop, there were a couple of lingering questions:

  1. Draws are theoretically possible on the recommended even-length board sizes (12×12 and 16×16).  How likely are draws in typical play?  Is it possible that high-level Permute play could become infested with draws?
  2. Permute does not use a balancing protocol like the swap rule we use in many other games like Hex or Havannah.  Is the game balanced enough as-is, or does the first or second player have an advantage?  Should I add a balancing protocol?
  3. Is it possible that symmetric playing strategies might break the game?

The Ai Ai report helped alleviate my concerns on these three aspects.  While of course these results shouldn’t be taken as gospel, I’m comforted by the fact that in 88,891 games played by the AI, not a single one was drawn!  On top of that, the winning chances for each side across all those games was 49.99% for Orange and 50.01% for Yellow — nearly perfectly balanced.  Finally, Ai Ai attempted to win with various mirroring strategies, but lost every game in those instances.  Permute might still prove to have issues on these fronts when attacked with superhuman neural-net AI, or super-strong humans, but at least I can rest assured that the game doesn’t break too easily.

Playing Permute in Ai Ai

When you load up Ai Ai, you can find Permute in the ‘Combinatorial 2020’ category, which you can find in a folder if you go to the File menu and click ‘Choose Game…’.  Once it loads up you’ll be presented with a dialog box to choose a few options:

  • Resign when hopeless?  This means that the AI will determine when it has no chance to win, and will resign at that point rather than playing on.  This is a very convenient feature, though for new players it might be worth playing a few games without it on, so that you see games all the way through to the finish.
  • Alternate setup?  This allows you to choose the alternate starting position with a 2×1 chequerboard pattern rather than the standard chequerboard.
  • Board size:  Here you can choose the size of the board, ranging from 8×8 to 24×24.  The default is 12×12, which is a good size to start playing on.  When you want a deeper, longer game, I’d go for 16×16.

After choosing your options, you’ll see something like this:

permute-screenshot1

Here I’ve loaded up a 16×16 game with the standard chequerboard setup.  If this is your first time starting Ai Ai, you may find the default will be for you, the human player, to play as Orange and the AI to play as Yellow, but you can change this to Human vs Human or AI vs Human or AI vs AI using the AI menu.

Stephen has implemented a very handy system for making moves in Ai Ai that uses mouse-dragging to determine which direction your twists will go.  To make a clockwise twist, locate the 2×2 face you want to twist, and click and drag from the top-left of that face to the bottom-right; to make a counterclockwise twist, drag from the bottom-right to the top-left.  After that, just click on one of your just-twisted pieces to bandage it, and there you go — your first Permute move!  If at any time you need a reminder of how the moves work, just click the Rules tab on the right side of your Ai Ai window.

Once you get used to the input method you’ll find Ai Ai is an incredibly convenient and flexible way to play the game.  By changing the AI thinking time in the AI menu, you can tailor your opponent to your skill level.  Beware, Ai Ai can be very strong if you give it lots of time!  To give you an idea of what Ai Ai plays like on higher thinking times, here’s a sample AI vs AI game played with ten seconds of thinking time per move:

This game was quite a good one, a close back-and-forth battle.  As is typical from the AI, the game was fought initially in the corners, and once territories took shape there, both sides extended into the centre to battle for dominance there.  This seems a good way to open a game of Permute in general — territory is easier to secure along the corners and edges with fewer bandaged pieces required, and once some gains have been made in those areas the protected groups can be used as a base to stake a claim on the centre of the board.

Just for kicks, here’s another sample game played on a 24×24 board, this time with 5 seconds of thinking time per move:

As readers of this blog will know, I generally love playing abstract games on larger boards anyway, but I particularly love playing Permute on big boards.  There’s something extremely satisfying about seeing these huge chequerboard patterns gradually coalescing into interestingly-shaped blocks of colour.  On the larger boards there are tantalising hints of fascinating strategies lurking in the distance; as you’ll see in the game above, the AI battled itself across the whole board, and intriguing local battles eventually linked together into larger contests as the game evolved.  Playing on a physical board this size might be a bit challenging, not just in terms of space but also in terms of keeping track of group sizes, but since Ai Ai takes care of both those problems, I highly recommend trying some bigger boards when you have time!  In truth 16×16 will stay my recommendation for tournament play, but I can say for sure that 20×20 and 24×24 have real potential, and the resulting games still take less turns than a game of 19×19 Go to play out, given that each move affects a decent-sized chunk of the board.

What’s next?

I hope the info above might convince you to give Permute a try using Ai Ai.  This program is essential for any fan of strategic games regardless, and the implementation of Permute is just perfect.  The AI plays a tough game, and you can easily experiment with larger board sizes and the alternate start position.  As you can probably tell, I’m hugely excited to have Permute available on Ai Ai, and I’m enormously thankful to Stephen Tavener for taking the time to implement it!

Hopefully this won’t be the end of exciting news for Permute.  I’ve been speaking with some very talented designers about the game, and earlier today I received a beautiful concept for a purpose-built physical game set for Permute that just blew me away.  Abstract games are a bit of a risk for publishers compared to more accessible, flashier board games with fancy bits, but nonetheless I do intend to keep investigating if this game could be realisable physically.  In the worst-case scenario, perhaps we could offer 3D-printed game sets for fans to purchase, if publishers don’t want to take a chance on it.

In any case, I hope you’ll download Ai Ai and give Permute a shot!  Let me know how you get on with it.  Keep an eye on these pages for more updates on the game, and hopefully some strategic tips and tricks as I gradually become less awful at it 🙂

Tagged , , , , ,

Permute: A Game About Twisting Things

As some of you are aware, one of my hobbies besides games is solving twisty puzzles, also known as 3D rotational puzzles.  The most famous example is the legendary 3x3x3 Rubik’s Cube, but since that set the world alight some decades ago a fascinating community of twisty-puzzle designers has emerged, producing some truly outrageous puzzles.  Here’s a few examples from my collection: 

So, as challenging as the Rubik’s Cube is, these days you can get puzzles that quite simply put it to shame.  I love the challenges presented by these amazing puzzles, and in recent months I’ve been trying to develop a way to bring the joy of twisty-puzzling into the world of abstract strategy gaming.

A new core behaviour: the twist

The key properties of twisty puzzles that makes them so challenging is the way in which the twistable faces of the puzzle interact with one another.  Any time you twist a face on the Rubik’s Cube, or any of the monstrosities above, you are forced to disrupt some of the work you’ve already done.  This creates a feeling of tension and danger when you’re first learning to solve a new puzzle; you’re acutely aware that at any moment, a wrong move or two could re-scramble the puzzle and essentially send you back to the beginning of the solve.

I wanted to capture this feel in the form of a two-player abstract game, so I began to cast about for examples of games that used twisting mechanics to shuffle pieces around.  Probably the most famous example in abstract games is Pentago:

Pentago Game from Mindtwister USA, Black-Natural/Solid Birch: Amazon.co.uk:  Toys & Games

In Pentago, players place marbles on the board and rotate the clever 3×3 sub-boards in an attempt to build a line of five of their pieces before the opponent.  The board rotation does create an enjoyable feeling of chaos in the game, but I had to immediately dismiss this idea for my game.  In a Pentago-type game with rotatable sub-boards, the sub-boards don’t actually disrupt one another; the relationships between stones can shift as they rotate around, but the sub-boards can’t actually scramble each other, as the faces do on a Rubik’s Cube.

I soon realised that the best way to replicate the behaviour I wanted would be to allow the players themselves to define the axes of rotation.  This wouldn’t really be possible with a physical board, though — how could you build a board where any sub-board of a certain size on it could twist?  

Instead, players would select an area on the board — a 2×2 or 3×3 subsection — and rotate the pieces within it, as if the board section below them had rotated like the face of a Rubik’s Cube.  This would capture exactly what I wanted: rotations could overlap with one another, allowing pieces to get twisted around and then re-twisted and scrambled up in other newly-created ‘faces’!

Then I embarked on a series of experiments to work out how best to implement these face-twists.  My first impulse was to allow players to rotate 3×3 sections of pieces, since the 3×3 Rubik’s Cube is so iconic.  However, I soon found that, while it was definitely fun, for a serious game 3×3 twists were simply too confusing.  The board state changed so much on each turn that trying to build strategic plans felt a bit fruitless.

I finally decided on 2×2 faces as the sweet spot — four pieces were still moving every turn, creating interesting situations on the board, but there wasn’t so much disruption that calculating future moves became impossible.  The core twisting behaviour of Permute was born:

Permute-twist-demo

Here Yellow selects a 2×2 ‘face’ of pieces and twists them 90 degrees clockwise.  At the start of the move, neither player had orthogonally-connected groups on the board; at the end of the twist, both players have two groups of three.

This behaviour would allow for the possibility of disrupting groups with further twists, which was another key concept of the game for me:

Permute-twist-demo response-01

After the move above, Orange strikes back by twisting a face just to the south of Yellow’s last move.  By twisting that face clockwise, Orange wrecks Yellow’s bottom-right group and boosts his own upper-right group from three connected pieces to six!

From here the overall shape of the game fell into place in my head almost automatically:

  • I wanted the players to focus on permuting pieces around the board, without additives like placing additional pieces or removing them through capture.  That meant the board should start already full of pieces.
  • The most interesting task to do with 2×2 twists would be to connect groups, and this would also mirror the act of ‘solving’ coloured pieces on a Rubik’s Cube.  I could keep the game tactically spicy by restricting connectivity to only horizontal or vertical; this would ensure that players could slice groups in two with twists that changed connectivity to diagonal only.
  • If the goal of the game is to build the largest orthogonally-connected group of pieces, then the fairest start position would be one where not a single piece of either side is connected orthogonally — a chequerboard pattern.
  • To ensure that players had to keep the whole board in mind and not just fight over the biggest chunk of pieces, the Catchup scoring mechanism — where if the largest groups are tied, then the player with the biggest second-largest group would win; and if those are tied, then check the third-largest, etc. — would be perfect.  That would ensure players would also need to build and preserve secondary groups, in case scoring went to the wire, and would prevent the game descending into a non-stop back-and-forth slap-fight over the largest group without opportunities to play distant strategic moves.

The game already felt nearly done!  I tested out the chequerboard starting position and twisting mechanics on my Go board with some colourful plastic pieces, and I found it was easy enough to play even with physical components.  Everything felt right so far, but I still had a problem:  how to get players to stop twisting?

Bandaging

A clear issue with the game at this point was a lack of termination.  Players could endlessly twist pieces back out of position, preventing their opponents from making any serious headway.  I needed a way for moves to have some finality, and create permanent changes in board state.  That’s when I decided to take a break and play some Slyde:

slyde16-10s-1

In Slyde, players take it in turns to swap one of their pieces with a horizontally or vertically adjacent neighbour of their opponent’s colour.  After the swap, the active player’s piece becomes pinned in place and can’t move for the rest of the game (and the opponent can’t swap with it). 

This was exactly the kind of thing I need for Permute!  Since a twist moves four pieces, and up to three of them could be of the active player’s colour (twisting four would be meaningless so I excluded that as a possibility), then a player’s move could consist of two parts: a twist in either direction, followed by fixing one of their pieces in place permanently.

That would accomplish what I needed — each move would have some finality, but since only one piece would be fixed in place, groups would still be in constant danger of disruption without further moves to shore them up.  Giving players a choice of which pieces to fix in place added an additional strategic element to the game, enabling players to try to optimise their twist/fix combo to achieve the best result in terms of securing territory and/or denying territory to their opponent.

With this final element now in place, I had a complete game — the initial position, goal, end condition and moves were all set.  I decided to call the piece-fixing ‘bandaging’, a term derived from twisty puzzles.  Bandaged puzzles have certain pieces glued together so that in some positions certain moves would be blocked; the term also refers to states in some puzzles where twists in certain directions are blocked.  The term comes from the fact that bandaged puzzles were made in the early days by using Band-Aids to stick pieces together on the Rubik’s Cube.

Playtesting

Now that the rules were set, I started playtesting the game, first with trial matches against myself.  The game seemed roughly balanced in my tests on 9×9, 10×10 and 12×12 board setups.  The core twist/bandage dynamic was enjoyable and gave each player’s turn a couple of interesting decisions to make, and each move felt like a tradeoff between securing territory and sacrificing future mobility, which was just the kind of feel I wanted.

The final test was a playtest match against Phil, which we did via a convoluted setup involving sharing my Adobe Illustrator screen over Google Meets.  Phil is quite good at most games he tries, so I felt confident he’d be able to tell if the game was obviously broken pretty quickly.  We had an enjoyable match, and true to form, Phil took a convincing win:

Phil told me that while it took a bit to get used to the twisting aspect, he could see that there was room for interesting strategies to develop, and he felt engaged by the action throughout the game.  At that point I felt it was an appropriate time to share the game with the wider world and get some more feedback, so I typed up the final rules and put together a thread on the BoardGameGeek Abstract Strategy forum.

The Rules

Here are the final rules, as presented on BoardGameGeek (well, tided up a bit):

The basics: Permute is a game about twisting things, inspired by twisty puzzles like the Rubik’s Cube. The name comes from one of the two main things we can do with pieces in a twisty puzzle: permute them (shuffle their positions); or orient them (change their facing). In this game players take it in turns to rotate 2×2 sets of pieces (‘faces’) on the board, in an attempt to bring pieces of their colour together in larger groups. Once a face has been twisted, part of it is locked in place (‘bandaged’) and can’t be twisted again. When no more twists are possible, the game is over and the players’ largest groups of pieces are scored. To win the game, you must permute your pieces so that they form the largest connected group, and deny your opponent the chance to do the same!

The rules: Play proceeds on a square board with a 9×9 grid (or larger). At the start of the game, all squares are filled with alternating Yellow and Orange stones in a chequerboard pattern.

Definitions:

Face: a 2×2 subset of the board surface. A face may not extend off the board.

Bandaged Stone: a stone with a token, sticker, or other marker on it that indicates it may not be twisted again.

Bandaged Face: a face containing one or more bandaged stones. A bandaged face cannot be twisted.

Twist: a move in which all the pieces in a face are translated around that face simultaneously 90 degrees in either a clockwise or counterclockwise direction, as if rotating the face of a 2×2 Rubik’s Cube.

Group: a group is a set of same-coloured stones connected orthogonally. The value of a group is the number of same-coloured stones it contains.

Orange plays first. The swap rule can be used – after Orange’s first move, Yellow may choose either to play their first move or change their colour to Orange.

Players then take it in turns to twist one non-bandaged 2×2 face containing at least one of their colour stones 90 degrees clockwise or anticlockwise. Once a face has been twisted, the player who twisted it must select one of their stones in that face and place a token on it, thereby bandaging it.  Faces containing a bandaged stone cannot be twisted.  Faces consisting entirely of one colour cannot be twisted either, so this is not a way to pass a turn (but mono-colour faces can be disrupted by twists of neighbouring faces, of course).

The game ends when no more twists can be made. At this point scores are compared. The player with the highest-valued group wins; if both players’ largest groups are equal in size, then compare the second-largest, then the third-largest, and so on until a winner is determined.  If the board is even-sided and the scores are somehow equal all the way down, then the game is a draw, but this should be very unlikely (and outright impossible on odd-length boards).

Translation for non-gamers

That looks like a lot of rules, but really it’s a pretty simple game!  There are two players, Orange and Yellow; Orange plays first.  Each turn, the active player must select a 2×2 sub-section of the board (a ‘face’) and rotate the pieces in it 90 degrees clockwise or counterclockwise, just as if they were rotating the face of a 2×2 Rubik’s Cube.  Once the twist is done, they must choose one piece of their colour in that face and bandage it; once a piece is bandaged, it can’t ever be twisted again.  

As the players make more and more twists and bandaging moves, gradually the board will get more and more constricted.  Since faces with bandaged pieces in them can’t be twisted, moves will be blocked and players will start to have secure territories built up.  Once no more moves are possible at all, players count up their largest groups of pieces of their colour; a group is a set of pieces that are connected horizontally or vertically, diagonal connections don’t count!  See the pictures from the game between Phil and myself for a scoring example.

The player who built up the largest group of their colour wins the game.  If both players’ largest groups are the same size, then compare the second-largest groups of each player, and the largest of those two groups wins.  If those are still tied, then check the third-largest, and so on.  

So, winning a game of Permute means you have to bring your pieces together into connected groups, but because twists can disrupt so much of the board, you have to work hard to protect them!  That means bandaging pieces strategically, to hopefully prevent your opponent from tearing apart everything you’ve worked so hard to build.  Once you play for a bit, you’ll start to see ways to build your groups while simultaneously blocking or disrupting your opponent, and that’s when you’ll start to really enjoy what Permute has to offer.

Alternate starting positions

The default chequerboard starting position works well, which is why I chose that as the ‘official’ starting position in the rules.  However, during testing, Phil had suggested the possibility of an alternate starting position that might be easier on the eyes.  We worked out that a chequerboard pattern of 2×1 blocks could work well, and had another advantage in that early-game twists would immediately create some bigger connections, which could be helpful for new players who may have more trouble seeing groups right away:

In the discussion on BGG, Steven Metzger pointed out that playing on a 13×13 board would forbid the possibility of draws, and would also mitigate a possible first-mover advantage by giving the second player a stone advantage:

F2L-13x13 -- NEW start position --Orange-Yellow-01

Ultimately I’m not sure that draws will be much of a problem anyway, as maintaining precise parity across every group down the size order would be pretty unlikely, but it’s good to have the option.  Plus in a matchup between two players of uneven strength, giving the weaker player the side with extra stones on the board in this setup could help them be competitive.

However, it’s not immediately clear how to replicate the alternative 2×1-chequered start position on an odd-length board; Phil had some ideas about this which could work, but the setup would be more awkward on a physical board.  We’ll keep trying though, eventually we’ll find a good alternative.

Permute on MindSports

I was generally pleased by the reaction on the BGG forums; most posters seem interested in the game, and had some good suggestions about the visuals.

Most exciting for me was that Christian Freeling, a designer I’ve spoken about quite a bit in these pages, was immediately positive about the game.  This meant a lot to me, not just because I’m a fan of several of his games, but also because he’s got a very strong intuitive sense about whether a game will work or not; for him to say that he felt “it is immediately obvious that it works (without endless modifications)” gave me a big boost in confidence.  

Christian is also the proprietor of MindSports, a website that hosts all of his games for online and AI play, as well as some games from outside contributors.  Lucky for me, Christian and Ed van Zon decided to implement Permute on MindSports, so now anyone can play Permute against the AI or against other people (via the MindSports Players Section)!

This was tremendously exciting for me — not only is Permute now playable easily in a digital format, but it’s sat in the MindSports website right below Catchup and Slyde!  As I described above, these two games gave me inspiration I needed to get Permute to its final form, and both are really excellent games, so I feel privileged to be sharing a page with them.

I’ve spent the weekend making some YouTube videos about Permute and writing this post, so I haven’t yet dived into online play, but I did have a couple of matches against the AI.  The AI isn’t super strong but it’s still a fun time and a great way to learn the game:

Now that my first promotional push for the game is completed, I’m happy to accept challenges for games on MindSports, so please let me know if you fancy a game 🙂

Where next?

I’m really happy with how Permute turned out, and as people are playing it here and there I’ve had some great feedback on it.  That being the case I’m not planning to make any further changes to it, beyond perhaps adjusting the starting position if computer analysis finds a strong advantage for either player or something.

However, the core twisting mechanism does have lots of potential for future development.  I have two new twisty experiments I’m working on right now: a four-colour twisty game on a hexagonal grid; and a square-grid game where players only twist, and no bandaging happens.  The latter is a difficult design challenge, so if you have thoughts about it feel free to air them in the BGG discussion thread on the topic!

Twisty experiment -- game 1-01

The initial test of the idea in that thread (shown above) has some potential, but definitely needs some work.  In this game, players only twist 2×2 faces, and pieces become fixed in place (‘solved’) when they join a group of pieces connected to three or more neutral edge pieces.  There are some other ideas in the thread that I think are worth investigating too, and ultimately I think some synthesis of these concepts will produce a good game.  However I’m going to let all this simmer in the back of my head for awhile, and keep most of my attention on enjoying Permute for now.

In the meantime, I hope some of you out there will give Permute a try!  Go check out MindSports, have some games against the AI, and get in touch if you want to have a game with me.  I hope that some more strong players will have a go at the game, and that soon we may see some interesting tactical and strategic concepts develop.

I’ll do some follow-up posts on Permute in the future and show off some sample games with interesting play, so please look forward to that.  At some point too I’ll reveal Permute’s other twisty siblings once they’re in good shape 🙂 

If you’re dying for more Permute content, please do check out my YouTube videos: I have a short intro to Permute with some sample moves; a longer intro with a full sample game against the AI; and finally a video introducing Catchup and Slyde alongside the wonderful Ai Ai game-playing platform.

So, give the game a shot and let me know what you think!  Perhaps I’ll see you on MindSports.  Before I go, I wanted to say another heartfelt thanks to Christian and Ed for putting Permute up on MindSports, and to Nick Bentley and Mike Zapawa for creating Catchup and Slyde respectively, without which Permute might have just stayed as a weird twisty concept in my head and never become a playable game.  

Tagged , , , , , ,

(Re-)Learning C Via Computer Chess

In recent months I haven’t had much time to do a lot of programming, what with the demands of my work. One thing I’d been meaning to do, whether it factors into my research directly or not, was to re-acquaint myself with the C programming language. I used it way back in the day, but then as time went on I fell in love with Python, which despite being ridiculously slow in comparison, is extremely fun to use. But the fact remains that it’s very useful to be able to write compact, speedy code from time to time, either for writing simulations for work or for passion projects.

So, I decided to find myself just such a passion project to rediscover the joy of programming in C, and given that I’ve been playing and studying a hell of a lot of chess and shogi in my spare time of late, I decided to learn how to program a fast and relatively powerful chess engine in C. A traditional chess engine uses brute force to search a very large number of possible moves on its turn, evaluating each one in turn until it chooses what it thinks is the best move for the situation. Given how much computing power is available these days, even a half-decent smartphone can now play chess at a level greater than any human, including Grandmaster-level professionals.

In order to do this I followed a great series of videos on YouTube called ‘Programming a Chess Engine in C’, which is 95 videos long (!), but covers a ton of stuff, helping you build a fully-functional chess engine in C which uses the standard techniques in chess programming — alpha-beta search with null-move pruning and some other optimisations. The engine is capable of playing a game of chess via text commands with the user, or by communicating with graphical chess software using the UCI or WinBoard/CECP protocols to let you play a game with mouse control and lovely graphics for the pieces.

After watching all that and feeling my way around C again, I’ve now produced a chess engine of my own, which I’ve named SpaceDog, in honour of my dog who is from space.  At the moment it’s basically the same as the VICE engine which comes from the videos above, but has a few small additions in the evaluation function to make it a little stronger (hopefully), as well as a few quality-of-life improvements here and there.  It works great, and plays a mean game of chess already — which perhaps isn’t surprising since it searches and evaluates about 3.5 million chess positions per second!  In comparison a master-level human player might evaluate perhaps 3 or 4 positions per second.

Here’s a screenshot of SpaceDog playing in text mode:

Screen Shot 2018-10-14 at 03.23.34As you can see, it prints out a nice little text-based board for you (white pieces are capital letters, black pieces are lowercase).  Moves are entered in long algebraic notation — so to move white’s queen at the bottom of the board to the square above white’s king, you’d enter d1e2.  SpaceDog also prints out its search results and position evaluations on each move, so here you can see at the bottom that it searched nine moves ahead (depth:9) and spent 2.9 seconds evaluating 11.9 million moves before choosing the move e7e4 (taking my pawn with its queen) based on what it thinks of the resulting position and its future prospects.

Every searched position is evaluated quite simply, with a score calculated on the basis of material balance, the position of the pieces, and things like whether there are isolated pawns and other key features.  Right now I’m adding some additional evaluation terms that better capture how the relative value of certain pieces, and their ideal placement on the board, changes as you proceed from the opening to the endgame.  Hopefully this will make SpaceDog a bit more shrewd at finding checkmate!

The engine can also use opening books — these are files generated by processing millions of opening moves from many hundreds of thousands of professional chess games, choosing a repertoire of openings based on what moves proved to be most successful.  This means SpaceDog essentially has a huge file of opening moves already catalogued in the book, with an enormous selection of replies and counter-replies for all the best possible responses from the opponent.  These moves then don’t need to be searched, meaning that SpaceDog saves tons of time for searching much deeper in difficult middlegame and endgame positions.

At this point SpaceDog probably plays well enough to beat anyone I know, but would likely still lose to players above Master level.  That would probably change at fast time controls — i.e., quick game setups like blitz (5 or 10 minute time limit for each player) or bullet (1 minute each!).  At these time controls, humans simply can’t make much use out of our superior long-term strategic planning abilities, so even SpaceDog’s rudimentary but tactically sound play should be tough to beat when us human meat-bags are sweating over the clock and feeling the pressure.

Anyway, it’s been a lot of fun so I plan to keep it going!  Next steps are to continue to enhance the evaluation function to better account for things like keeping the king safe and setting up outposts for bishops and knights.  I’ll also work on some more technical enhancements like multi-PV search (searching multiple lines of play on multiple CPU cores simultaneously) and adding support for endgame tablebases to allow SpaceDog to achieve perfect endgame play.

Most importantly though, I want to add a mode so SpaceDog can play Crazyhouse and Chessgi, variants of chess in which captured pieces become yours and can be dropped back onto the board as part of your army.  This is a feature taken directly from shogi which is a game I also love, so I’m looking forward to implementing these.  Eventually I may try to build on that foundation and add a shogi mode as well.

‘What’s the point of all this?’ you’re probably asking at this point — after all, SpaceDog will never be as good as current strongest engine Stockfish, and plenty of other engines play Crazyhouse and lots of other variants besides (such as this version of the mighty Stockfish).  There are even innovative neural-network-based engines coming out now like LCZero that are challenging for the throne of toughest computer opponent.  But nevertheless writing SpaceDog has been satisfying and fun, and it’s given me another way to learn more about chess and enjoy the game from a different angle.  I’d also forgotten how satisfying coding in C can be — the final SpaceDog program takes up only 74KB (!), yet it effortlessly plays chess better than I can.

Anyway, I thought I’d post this up just on the off chance anyone else might get something out of learning a bit about chess programming.  I highly recommend the tutorial videos I linked above from Bluefever Software — they’re really easy to follow and provide excellent explanations of the key concepts you’ll need to know to write a chess engine.

Someday I’ll post up the code for SpaceDog too, once I add a few more additional features in!

Tagged , , ,

Paper submitted to ECAL 17

Just submitted a new paper to ECAL 17, the European Conference on Artificial Life.  I wrote this together with Richard Shaw, Mark McCann and Laurence Moore in the MRC/CSO Social and Public Health Sciences Unit at the University of Glasgow.

The goal here is to get some of the Alife community interested in some key problems in population health to which we think Alife can make a strong contribution.  The paper describes the current state of computational modelling in population health, the reasons behind the growing popularity of ABMs/complex-systems-based approaches, and describes in detail some specific key problems where complex social and environmental determinants play important roles.

And before anyone asks, yes we’re already working on stuff like this, we just want more people joining the fun!

A little preview snapshot below:

ecal17cap

In other news:

Major projects: We’re still working on some significant attempts at gaining funding for longer-term projects in agent-based modelling for population health.  Watch this space.

Game development: Somewhat predictably, development on my game has been stalled since spring semester started and teaching took up all my energy and most of my research time.  I’m making an effort to read up on design principles, both for roguelikes specifically and in general, to improve the gameplay whenever I have the time to get back to it.

Music: I discovered recently that some old DJ mixes I had online for years now that I never promoted in any way actually attracted a decent number of listens and some very positive comments in my inbox, so I’ve dug my DJ kit out of the closet and am getting caught up on new DnB and hardcore releases.  I’ll put something new up on MixCloud or somewhere when I’m back in the groove.

On a side note, I’m so out of touch that I only just found out that Vestax, makers of my beloved DCI-300 DJ controller and my turntables before that, went out of business in 2015.  RIP Vestax, you made great gear that lasted forever and I loved you for that, although in retrospect maybe that’s why you had trouble keeping sales up!

Tagged , , , ,

Game Dev Update: Twisty little passages, all alike

A quick update this time — I’ve been working here and there on implementing some maze generation code for the game, so that I could have a few different types of dungeon levels to generate.  At last I’ve got it working, and can now generate some intimidating mazes using the ‘growing tree’ algorithm:

maze16

By altering the likelihood of new branches in the path, I can change the feel of the maze significantly.  The maze above has a high likelihood of producing new branches; the one below produces much longer hallways:

maze19

 

Tonight I’ve just added a variation of this algorithm which mimics another well-known maze generation method, the ‘recursive backtracker’.  This one needs some fine-tuning, though, as currently it produces very long, meandering corridors that can be a little annoying to navigate:

maze20

The next step is to make the maze generator a bit more flexible.  Ultimately what I’d like to do is allow the normal dungeon generator to create maze rooms which can be integrated into the rest of the dungeon.  This will add some more variety in the dungeon without forcing the player to navigate an entire level-spanning maze every time the dungeon generator decides to mix things up.

I do think I want to have one dungeon level that’s entirely a maze, though, and encourage exploration by sticking a powerful artifact somewhere within and dropping some hints that the player might find it if they have a look around.  I’ll also scatter some Scrolls of Clairvoyance about, which will reveal the location of the level exit and make navigating the maze less directionless.

As you might’ve guessed, in these screenshots I’ve switched off the ‘fog of war’ for the player so that I could observe and test the results of the maze generator.  In actual play things look more like this:

maze17

By way of comparison, here’s how a maze level looks in the famous(ly difficult) roguelike Nethack:

Image result for nethack gehennom

More to come next time, when hopefully I’ll have maze rooms working.

 

Tagged , , ,

Game Dev Update: Upping the Challenge

So it’s been a little bit since the last update on my hobbyist game development efforts, but a lot’s been going on whenever I can snatch some time in between the constant, endless presentations I’ve had to prepare for recently on the academic side of my life.

My focus in the last few weeks has been on some core gameplay systems.  Originally I was going to work on the dungeon environment, but I figured that fancy dungeons wouldn’t be that useful if the player couldn’t do interesting stuff in them, so I went for under-the-hood gameplay systems instead:

Hunger system

Hunger systems are a classic feature of roguelikes — since the original Rogue, in fact!  The idea is that the player needs to seek out food within the dungeon and eat it regularly, otherwise they gradually begin to starve to death.  Since food is limited and can only be found within the dungeon and not created by the player, it serves as a time pressure mechanism; the player has to keep moving further down the dungeon to find food in order to stay alive.  Currently my system is very basic: the player starts with three rations, and can find two different types of food items within the dungeon that refills their hunger meter.  If at any point your Satiety stat dips below 50, you start getting warnings, and at 0 begin taking damage every turn.  At -50 you’ll die of starvation.  I’ve added an indicator to the interface that shows this stat directly, unlike Rogue and some other games that keep it hidden and only warn you shortly before death:

satiety7

Turn Scheduling:

In order to make monster fighting more interesting, I wanted to add a system for variable attack and movement speeds between different creatures.  This is kind of a weird thing to implement in a turn-based game, and I wasn’t sure of the best way to go about it at first.  Eventually I settled on a central turn scheduling system in which all monsters (and the player) schedule their next turn each time they take an action.  The number of turns they have to wait until they can move or attack again depends on their Speed stat.

It sounds simple, but it turned out to be a big pain to get right!  I had a lot of weird bugs where certain monster turns didn’t register, or the game would suddenly stop running in turn-based mode and let monsters run rampant while the player was unable to move, and all sorts of other problems.  Eventually I got all that ironed out, and finally had fast-moving wolves and bats, slow-moving zombies, etc… only to find that in certain circumstances the player would encounter invisible and invincible enemies after moving to a new dungeon level.

After a few days of annoyance I worked out the problem — monsters were dying in combat, but a reference to them was remaining in the turn schedule, meaning that memory was still being allocated for their monster data by the program.  In certain situations that meant the scheduler would find that reference, say to itself ‘hey this here says there should be an orc doing something’ and the player would end up fighting a ghostly remnant of a previously defeated enemy!

I was able to fix that relatively easily once I figured it out — this is why we keep backups, kids.  Also it was a useful reminder to be more careful about my coding practices in some parts of the game, so I did quite a few bits of refactoring of the code to prevent anything like that happening again.

Combat System Changes:

Again in service of making combat more interesting I made some significant changes to the combat system to better differentiate enemies.  My favourite series of Japanese RPG games is the Shin Megami Tensei series, which are known for being set in a dark demon-infested version of Tokyo and for being really difficult.  What I love most about these games is that the combat system encourages tactical thinking by having weapons and spells deal a number of different types of damage, which demons can be weak to, immune to, or resistant to depending on their nature.

I implemented something similar to this, where each monster has weaknesses to certain types of physical damage (in this game they’re called Phys for general slashing attacks, Blunt for hammers/clubs, Pierce for arrows and spears, alongside numerous magical damage types like Fire, Ice, Thunder, etc.).  Hitting a monster’s weakness will do double damage to it, while hitting if it’s resistant you’ll deal only half damage.  Some monsters are immune to certain types of damage entirely — Skeleton Warriors, for example, aren’t bothered at all about being poked by arrows given their total lack of fleshy bits.

The idea is that this will push the player to experiment with different weapons, spells and items in order to dispatch enemies more quickly — particularly when they reach later dungeon levels, where monsters start appearing in large swarms and have powerful attacks.  I want damage types to be a major focus for the player, and for good attack choices to have significant rewards (and for bad choices to have a big impact!).

To make things a little easier for the player, I’ve added a Look command so that you can see some details about monsters in visual range:

look-command

Other than these big changes, mostly I’ve been squashing bugs and adding bits and pieces of content.  At this point, the player can face about 300 different monsters, collect 50 different weapons and items, and visit 15 different dungeon levels.  As time goes on I’ll keep adding new monster types, then randomly-generated weapons and items, and finally some super-tough boss monsters including a final boss.  At that point I think I’ll be ready for a playable alpha release to get some gameplay feedback.

This week has marked the official start of the academic year, so there’s been a ton of things to do at the university — which means there hasn’t been much time for game development!  I’ve been keeping careful track of all my additions and to-do lists and such, so when I have time to get back to things I’ll remember what I’d planned to do next.

All in all it’s a hell of a lot of fun so far, even when I’m getting frustrated by weird bugs.  I’m definitely gaining some major Python proficiency thanks to all this, and it’s forced me to tighten up my coding practices and embrace proper version control.

After some more work on damage types and attack variety I’ll be modifying the game UI and sprucing up the general look of things, so hopefully I’ll have some more interesting screenshots next time 🙂

I’ll leave you now with some game recommendations:

SDL Rogue: a well-done Windows port of the original Rogue, with some nice additional options (including a graphical tile option).  Type ‘?’ to see all the commands (there’s a lot of them!).  The same site also has similar ports of other classic roguelikes, including Hack (the predecessor to Nethack), Larn, and Moria (predecessor to Angband).  Check ’em out.

DoomRL:  This is a fantastic free game that combines two of my favourite things — the original Doom (in my opinion the greatest computer game of all time, and one I still play regularly), and roguelikes.  It masterfully combines frantic Doom-style demon-blasting with turn-based roguelike gameplay and character progression, and to top it off has the original Doom music and sound effects, and some fantastic 2D graphical tiles.  Download it!

Some enterprising fan has developed a server for DoomRL, too, so you can see how you stack up against other players and even play in your browser (or via a Telnet client).  ASCII text mode only though!

Crypt of the NecroDancer:  This game kicks my butt all over town, but it’s incredibly creative and fun.  It’s a turn-based roguelike with a twist: the entire game world is tied to the rhythm of the music for the level, and making your moves along with the beat gives you various bonuses (and moving out of time leaves you open to attack!).  All the items and monsters play on this theme.  The graphics are incredibly charming, the music is by Danny Baranowsky (of Binding of Isaac and Super Meat Boy fame) and is absolutely fantastic, and it’s packed to the brim with cool features and secrets to unlock.

It’s also 50% off on Steam right now, so now’s a great time to take the plunge!

Tagged , ,

Diversions: Game Dev Update

-WARNING: MORE GAME NERD STUFF-

So in my evening hours I’ve been working away on the roguelike game development project.  For the most part I’ve been really pleased with how well it’s trucking along — I’ve seen a number of other roguelike projects out there using Libtcod that fizzled out way before adding this amount of content, so I feel confident I can finish this project.

Having said that, it’s requiring a ton of changes in my coding practices.  Even in just a couple of weeks of development time, my game has expanded to the point where every addition has a large number of potential interactions with all the other game components, so I’ve had to give in and embrace version control.  Every change is archived on my own machine, then on Google Drive, and finally uploaded, checked, and merged into the master code branch on GitHub.  I’ve never bothered to do this before, but with this project (where just adding a new potion can cause weird stuff like making monsters stop moving completely until I find some minor malfunction) I’ve found I need to make it as simple as possible to back up a step when something goes strange.

I’ve added a few major gameplay additions since my last post.  One of them appears right at the start of the game — you can now choose a character role when you start the game.  Fighters are focused on close-range combat, Knights carry a shield which gives them great survivability, Archers are great at long-distance but weak up close, and finally Wizards are incredibly fragile but start with powerful spells.  Here’s a wizard who’s just managed to turn a wolf to stone:

update5

You might notice that I’ve been experimenting with the ASCII visual presentation too — the plan is to have some colour schemes for each set of dungeon levels, and each set will have particular characteristics and terrain hazards too.  I’ve also changed the lighting slightly, heightening the contrast between explored and unexplored squares, and I’ve changed the font to a 16×16 version of Terminal that I think is a bit easier on the eyes.

Since I’ve introduced Wizards, I’ve also introduced the beginnings of a magic system — although there’s a lot left to do in this area.  I’ve followed the lead of other roguelikes and developed a system of wand items — these drop randomly in the dungeon or from certain enemies, and give you a limited number of uses of a specific spell.  I’ve added eight wands, each with two varieties, as a first test of the magic system and how it affects play.  Later I’ll be adding a system for Wizards to learn spells permanently, a resource system to restrict usage, and more detailed stats for players and monsters to make certain spells more effective against particular opponents.

I particularly enjoyed making the Petrification effect — it turns the monster into stone, of course, which then blocks visibility and movement.  So you can use it tactically to block off other monsters and restrict their movement or vision.  When you tire of it you can destroy the statue and it crumbles into rocks (which you’ll be able to use as ammo for a sling, once I make that).

As for monsters, I’ve added a few of those, but more importantly I’ve added a random mutation system for monster creation.  When a monster is generated, there’s a small chance that the monster will be mutated either one or two times, and each mutation will add statistical bonuses and special abilities, as well as alter the monster’s name and display colour.  I’ve only added six mutators so far, but that’s already enough to significantly increase the game variety.  Honestly I probably spend more time play-testing than I really should when I have coding time — but I think that’s a good sign if I’m already finding it fun to play!  The mutators will be even better once I add more monster types — these are taking time as each monster type has it’s own AI function which takes a lot of testing to get right.

Here’s a Fighter who’s run into a Hellfire Troll, a significantly stronger mutation of the already difficult Troll:

update1

All told it’s been a productive week.  My goal for the weekend is to jazz up the dungeon environment significantly, first by setting up the visual themes and names for each level subset, then developing a system for adding terrain features, some of which will be interactive (think stuff like lakes, lava flows, grass, fungus, rock pillars, etc.).

After that there’s some major tasks in my development plan:

  • Flesh out the magic system (which will need a bunch of interrelated items and systems to go with it)
  • AI and game systems for allied characters (in some circumstances players will be able to raise some troops, by resurrecting dead monsters or brainwashing living ones)
  • Methods for random generation of items

Again none of these are new ideas — my design goal here is simply to make a complete roguelike in the classic style, with just a bit more playability and transparency.  Once it’s done I’ve got some ideas for game #2 — but I’m not allowing myself to think much about that now!

Speaking of roguelikes in the classic style, thanks to some dedicated roguelike fans out there you can actually still play the original Rogue on modern computers.  It’s still quite playable, albeit mercilessly hard — winning Rogue is a real accomplishment.

You can also still play Moria — the seminal early roguelike based on Tolkien which later spawned Angband.  Really though I’d recommend trying Angband if you want to try a classic roguelike — it’s much more user-friendly, has lots more content, and has a graphical mode.

Tagged ,

A Diversion: A First Attempt at Game Development

–WARNING:  LOTS OF WORDS INCOMING–

As my friends and colleagues are aware, my favourite hobby outside the academic sphere is gaming.  In particular I have a fondness for very difficult games that require some tactical thinking to survive — so I’m a big fan of roguelikes.

For those of you who don’t know what a roguelike is, I’ll share with you a too-lengthy post I made on Facebook by way of explanation:

My game is a ‘roguelike’, a genre named for a very popular game in this style from 1980 called Rogue. There’s some debate about how to define roguelikes precisely, but generally they’re characterised by:


1) Turn-based gameplay — you take a turn, then the enemies. You can take as long as you like to think about each action and its consequences.


2) Randomly-generated levels — often you dive into a very long, multi-level dungeon full of monsters, items and fiendish traps, and every level is randomly generated each time you play, meaning you never run out of levels to play and no play-through is ever the same. In my game dungeons are generated using BSP trees which is a pretty common method.


3) Permanent death — if your character dies, that’s it, you have to start over from the beginning! What’s more, most games (including mine) automatically save the entire game state after every move, and overwrite your saved game when you reload a save, meaning that you can’t ever go back to a previous turn. Every action has permanent consequences.


4) Text-based graphics are usually a feature of every roguelike in the classic style, even today in 2016. Graphical modes are normally an option nowadays too, but many people prefer text mode (including me) because once you get used to it the text actually makes it much easier to determine exactly what’s in front of you at any given time, which is important because…


5) …while the graphics are often simple, the gameplay is normally quite complicated. Hundreds of items, monsters, and environmental features are in these games, all of which can interact in tons of different ways — not needing to make fancy animations for everything means developers can go nuts with the gameplay systems.

Anyway those are the main features you see in the genre — most of the major games in the genre are completely free, so I recommend trying them. The site RogueBasin has links to the five ‘major roguelikes’ right on the front page — ADOM, Angband, Crawl, NetHack and ToME. In my opinion Crawl or ToME are probably the easiest places to start, given they have pretty nice visuals and decent tutorials for new players. Angband is a long-time classic and has a decent graphical mode included as well. NetHack is famous for having insanely detailed game systems and item interactions, but is a bit overwhelming for newcomers.

My game is very early in development, although the core gameplay systems are all functional (random dungeons, character progression, combat, item and magic systems) and it’s fully playable. Not bad IMO given I only started making it five days ago, but there’s a long way to go yet. My goal is to add at least one new gameplay feature, monster, item, etc. every day for the next couple months so I can gradually build up a complex but balanced gameplay experience.

Given that this is my first-ever foray into making a complete game — I don’t count my failed attempts to write code for the GameBoy Advance back in 2005 — I’m pretty pleased with my progress, and it’s certainly been an enjoyable and challenging way to spend a few days of my summer holiday.

I started off by following the Complete Roguelike Tutorial using Python 2.7 with Libtcod — this gets you a complete, playable prototype (albeit very simple).  Since then I’ve added quite a few major features, each of which has required learning a bunch of new algorithms or techniques:

  • A* pathfinding for monsters
  • Random dungeon generation via BSP trees
  • A graphical version (using free 16×16 tiles made for Angband)
  • A more complex combat system including dicerolls and critical hits
  • Damage-over-time (poison attacks)
  • A complete ranged combat system including ammo tracking and relevant attributes for the player and enemies
  • Several new AI routines designed for specific enemies, i.e.:
    • Wolves that call for their pack mates when in trouble
    • Snakes that stay at a distance and spit poison
    • Enemy archers who try to get the drop on you

Now that the core gameplay systems are mostly there, and the return to academic life is looming, I’ll be slowing down significantly from here.  My goal is to build on this foundation bit by bit over the coming weeks and months, until I have a cohesive 20-floor dungeon-crawl experience with quite a few dozen monsters, items and weapons to discover.  This is a bit of an experiment for me, and I may not release this game to the larger world and instead bank this experience for a better follow-up project.  Having said that, once it’s in a more complete state I’d welcome any interested play-testers!

I should note that if I do end up releasing this it’ll be completely free, and probably open-source, assuming my code isn’t too embarrassing.

Since this is ostensibly an academic blog I should say that part of what pushed me to finally take the plunge and try to make something like this was actually some of the students I advised last academic year.  A large proportion of my advisees were game development students, and I wished I’d had more domain-specific knowledge to help them through certain problems.  Now at least I can tell them where to look when I hear from students who are stuck on pathfinding, AI issues, etc.!

Before I leave you, a screenshot of the fabulous ASCII graphics I’ve been staring at for hours on end:

poison_screenshot9-cropped

And for the ASCII-shy, a screenshot of the graphical version:

tiles_screenshot6_cropped

More to come later — the graphical version is very much a side-project at the moment, so expect that to be spruced up as time goes on.  I’m planning to switch to the stylishly lo-fi tiles of Oryx Design Lab — they’re simple, visually clear, and as they’re uncoloured I can tint them a million ways to represent the requisite dozens of variations of every imaginable monster that roguelikes generally have.

If you think I’m exaggerating — NetHack variant Slash ‘Em Extended boasts 12,221 monster species.  I think I’ll stop long before the 12,000 mark though.

That’s enough out of me for today — I’ll post updates on here every so often, if I find any particularly interesting techniques or come up with a version polished enough to distribute.

 

 

Tagged , ,