Where to start with GKMinmaxStrategist?

Question

I was wondering if anyone here has had any luck using GKMinmaxStrategist. This class/feature was showed off at the WWDC, but most of the sample code was in Objective-C, which was a disappointment.

The WWDC videos for GameplayKit featured another game, Stone Flipper (Reversi/Othello), but they haven't published the code (yet?).

Has anyone had any luck with this? I was hoping to try this out with just a simple tic-tac-toe game, but am not at all sure how to start.

Peignoir

I'll look into GKMinMaxStrategist this and next week. Follow my blog for results: tilemapkit.com/blog or Twitter @gaminghorror. In the meantime check out this question which links to a TicTacToe example in Swift: #30970716 – Armenian

"the sample code that Apple published to ostensibly show off the class... did not implement GKMinmaxStrategist" — eh? I see a GKMinmaxStrategist in the view controller class in Apple's FourInARow sample – Gerrald

You're right. Edited. – Peignoir

TicTacToe GKMinmaxStrategist tutorial in Swift is now online: tilemapkit.com/2015/07/gkminmaxstrategist-build-tictactoe-ai – Armenian

Answer 1

I agree that it's a tricky framework to learn – I just finished writing a tutorial about GameplayKit and GKMinmaxStrategist and it was no mean feat. If you follow the tutorial it builds a complete game from scratch, explaining how it all fits together. You might find it useful as a starting point, at the very least.

I'm hopeful that Apple will improve its documentation before iOS 9 is final!

If you want to dive straight in, here's the least you need to know:

• Ensure your game model (data) and view (layouts) are kept separate.
• Make your model implement the NSCopying protocol, because it will be copied many times as the AI runs.
• You should also make it implement the GKGameModel protocol, which requires that you be able to enumerate the available moves, apply a move on a board copy (virtually, not for real), then judge the players scores afterwards.
• Each "move" (for whatever that means in your game) needs to conform to the GKGameModelUpdate protocol, so it'll be a class you create that defines a particular move. You'll be given this back when you the best move has been chosen, so it will contain something like "move the knight to E4".
• If your game does not have a score (in my tutorial I used Four in a Row, which has exactly this problem) then you need to come up with a heuristic estimating roughly how good a move was.
• Run the AI on a background thread to ensure your UI remains responsive, then push the result back to the foreground thread when you're ready to make UI changes.

If you find the AI is running slowly, either restrict the number of moves it can make or reduce its look ahead depth.

Plemmons

Not a bad tutorial. One point it glosses over: the choice of 7 moves for maxLookAheadDepth isn't arbitrary. Four In a Row, as the name suggests, is won in 4 moves—assuming perfect play, looking ahead for 4 of one's own moves (and thus also 3 intervening moves by the opponent) is enough to guarantee a win or draw. Of course, if your heuristic isn't that great (as is the case in both Apple's sample and your variation on it), looking that far ahead doesn't really help. But looking further ahead won't, either, no matter how good your heuristic is—it'll just eat CPU. – Gerrald

"Not a bad tutorial" isn't quite what I aim for, but I guess it still counts as positive – thank you! :) I intend to push the code to Github tonight or tomorrow, and I'll make sure to include Apple's original lookahead comment. – Plemmons

Thank you for this tutorial! I have it up and running now. It really helped me start to get my mind around this stuff. One question: The heuristic isn't good, sure. I expect it to miss "complex" stuff like a disjointed three-in-a-row [x-xx]. But why does it miss (that is, not block) simple things like a vertical three-in-a-row? Even a look-ahead depth of 1 should catch that...right? – Peignoir

a high lookAhead can also make the AI play dumber because it might start to trade near-term losses for (possible) long-term wins - however in games like TicTacToe any disadvantage you get yourself into can typically not be recovered from. – Armenian

@Gerrald Looking ahead further very much does help: since we do not have a perfect heuristic, we can only really be sure when judging winning positions. And the further we look ahead, the closer we get to potential end-game scenarios. – Stockpile

@Gerrald Let's say the AI could force a win after 9 moves. Such positions exist. If we only look ahead 7 moves, we may not pick the 'winning move'. – Stockpile

Answer 2

Here's the GKMinmaxStrategist TicTacToe tutorial in Swift.

This should explain how things work and gives some pointers on how to make a good AI. The strategist surely isn't a template to create any kind of board game AI, it just provides a framework. 95% of the work still rests on your shoulders. ;)

The code is available here. Note that it not only requires Xcode 7 but also OS X 10.11. Though it should be straightforward to adapt to iOS 9.

Armenian

that is a great tutorial of yours. How can we save the strategist knowledge, so it will perform better on next app run? – Accompanyist

Great tutorial with explanation of scores concept for strategist. The only thing that I don't understand is why we can't set the score to move itself (GKGameModelUpdate). – Nightclub

I meant move value. Few minutes later I got that I can add score property to our move... I'm in command:) Thanks again – Nightclub