Tag: Strategist

More GKMinmaxStrategist

With WeGame Corp, I’m redoing a game I wrote under Cetuscript called Krok. Krok is my version of Crokinole, a Canadian favourite. The rules in Krok are basically the same as Crokinole with some, in my opinion, minor tweaks.

My original game allowed up to 4 players to play either by sharing a device or by connecting through Game Center. I’m not sure if this rewrite will have network play. The jury is still out on that and the deliberations might become an article on this blog. However, the upcoming version will have bots to play against. So, if you can’t find any friends to play Krok with, you’ll still have the bots.

Playing Krok requires the evaluation of a starting point for your puck, a target for your puck, the angle to hit the target, and how hard to hit your puck. And all that boils down determining a position and a vector — four floating point values.

I used the GKMinmaxStrategist for Hexin, a two player chess like game. It was pretty easy to use. When I was thinking about how to do the AI for Krok, I thought about using a GKStrategist. The GKMonte​Carlo​Strategist seemed like it would be good. It advertises to be able to search a large space of alternatives by taking a random samples. However, it seems to be only looking for the win. I still needed to assess each random sample for its value.

That brought me back to the GKMinmaxStrategist. Of the four characteristics listed in that link, Krok provides “Sequential”, “Adversarial”, and “Perfect Information”. The game isn’t “Deterministic.” 3 out of 4 is pretty good.

Because the game isn’t deterministic, in fact even the AI players will execute their moves with error, there isn’t any point in searching far ahead. The maxLookAheadDepth is set to 1. I also set the randomSource to GKARC4RandomSource().

The GKMinmaxStrategist relies on evaluating all the possible moves for a given game configuration. With Krok, the number possible shots (moves) is infinite, or as many as you can generate with 4 doubles. In the gameModelUpdates(for:) method, I generate a large number of random and specific shot samples and then evaluate the shot in apply(_:) and score(for:).

A number of starting points are picked at random. For each starting point, each possible target is considered. For each possible target, ending points are determined at random. For each pair of starting point and ending point, the velocity is also randomly assigned.

Starting/ending points are also filtered out by obstruction. If the puck can’t travel between the start and the end points without hitting another puck or one of the 8 pegs, that pair is discarded.

Thus we have a number of random starting points and velocity vectors to consider. For each set, the resting positions for the shot puck and the target puck are calculated. For this calculation, I make a number of assumptions and simplifications. What I want to get to is a good guess at where the pucks will end up. I didn’t go into exhaustive detail because I didn’t want to do the math and I didn’t think the gain in precision would be worth it. After all, the actual shot will have an error applied to it. A good guess is good enough.

Where the shot puck and the target puck end up determines the value of the shot. The shot puck’s value is further modified by an estimation on how easy the shot would be. The harder the shot, the less valuable the shot is. While the value for the target puck isn’t modified by how hard the shot would be, it is the difference between the value of the target’s original position and the value of the predicted resting position.

The Shot, or GKGameModelUpdate structure, contains the starting position, the velocity of the shot, the value for the shooter, and an optional value for the target. It is optional because sometimes there is no target to shoot at.

In apply(_:), the active player’s score is modified by the value for the shooter and the opponent who has the target puck gets their score modified by the optional value for the target. In score(for:), the board score is calculated and return for the value of the board for the particular player the method was called for.

I’m doing the physics in gameModelUpdates(for:) rather than apply(_:) mostly for convenience. The data needed to calculate the core of the shot, the position and velocity, are all found in generating the shot in gameModelUpdates(for:). By taking the calculations a step further, the work to be done in apply(_:) is very simple. However, if I feel the need to evaluate the results of a shot in greater detail, I will move the calculations to apply(_:).

The benefit of using GKMinmaxStrategist is that it provides an easy to use framework for evaluating a large number of randomly generated samples. My coding contributions are confined to what is model specific. The strategist takes care of the rest.

Using GKMinmaxStrategist

I wear many hats. One of those hats is writing games. You can find the games I’ve written as Cetuscript Systems or WeGame Corp.

Hexin is a space chess game and I wanted a reasonable computer opponent for the players. I written a chess/checkers like game previously (not currently available) and my quick and dirty AI was okay-ish but not very challenging. For Hexin, I wanted something better.

With Hexin too, I wanted to explore the new game frameworks from Apple. GameplayKit is one of those new frameworks and it supplies a number of strategists classes. The GKMinmaxStrategist looked like it fit my requirements.

Tweaking the model for GKMinmaxStrategist was interesting. For my chess-like game, it boiled down to figuring out how to calculate a score for a particular board.

At the beginning, I tried working out a score by the value of pieces in the game. Hexin has three areas of the game: hanger, deck, and board. Pieces move from the hanger to the deck to in play on the board. Where the piece is determines if it is in play or how soon it might be to be put in play. Pieces in the hanger are not as valuable as pieces on the board.

A simple value of a player’s current pieces worked but not very well. The Strategist would know to improve the value of the player’s position but it didn’t recognize disaster to the plan. The Strategist would send its pieces on suicide missions.

To adjust for this, I had to also account for the move after. I was a bit worried about this because I didn’t want to spend the time writing an AI for the game. The Strategist should give me a reasonable opponent without going Deep Blue.

But, in the end, it seemed that accounting for the move after was enough to give me a reasonable opponent.

func score(for player: GKGameModelPlayer) -> Int {
    guard let who = player as? ModelPlayer else { return GKGameModelMinScore }
    
    let disaster    = GKGameModelMaxScore * 2
    let foolish     = 0
    
    let friend = who.side
    let enemy = friend.opponent
    
    let friendReach = self.evaluateReach(side: friend)
    let enemyReach = self.evaluateReach(side: enemy)
    
    var friendTotal:Int = self.evaluateValue(friend: friend) - self.whosePlaying[friend.rawValue].value
    var enemyTotal:Int  = self.evaluateValue(friend: enemy) - self.whosePlaying[enemy.rawValue].value
    
    var friendScore:Int = 0
    var enemyScore:Int  = 0

The friendReach and enemyReach are the next moves. Based on the current game, what can a player reach.

The friendTotal and enemyTotal are initialized with the difference between the initial value for the player and the current configuration value for the player. This gives the sense of are we better or worse off than when we started to figure out our next move.

    for (coord,_) in enemyReach {
        if let unit = self.board.units[coord], unit.side == friend {
            if unit.flavour == .Station {
                enemyScore += disaster  // this is a bad move
            } else if unit.flavour == .Portal && self.clusters[friend.rawValue].station.inHanger {
                enemyScore += disaster  // this is a bad move
            } else {
                enemyScore += unit.flavour.value
            }
        }
    }

I then go through the enemy’s reach. In the game, Stations and Portals are critical to play. The object of the game is to take the opponent’s Station or prevent the opponent from getting their Station onto the board by taking their Portal. If the enemy can take your Station, it is a disaster.

    for (coord,result) in friendReach {
        if let unit = self.board.units[coord], unit.side == enemy {
            if let _ = enemyReach[coord] {
                // this is a location that the enemy can take. not the best move.
                friendScore -= foolish
            } else {
                if unit.flavour == .Station {
                    friendScore += GKGameModelMaxScore
                } else if unit.flavour == .Portal && self.clusters[enemy.rawValue].station.inHanger {
                    friendScore += GKGameModelMaxScore
                } else {
                    if result == .Power {
                        friendScore += ValueForFighterPowered
                    } else {
                        friendScore += unit.flavour.value
                    }
                }
            }
        }
    }

Foolish is putting your piece into harms way. But I found that giving foolish a non-zero value didn’t help much.

Taking the opponent’s Station or Portal wasn’t weighted the same as the disaster of losing your own. Over weighting the victory lead to suicide missions. Also, in the game, there are power-ups. Using a power-up needed to be accounted for.

    friendTotal += (friendScore * TakePowerValueFriendFactor)
    enemyTotal += (enemyScore * TakePowerValueEnemyFactor)

The TakePowerValueFriendFactor is slightly larger than TakePowerValueEnemyFactor. The friendScore is given a bit more weight than the enemyScore.

    let diff    = friendTotal - enemyTotal
    var value   = max( min( GKGameModelMaxScore - 1000, diff), GKGameModelMinScore)

There is a gap of 1000 in the pinning of the score. This allows for the move that wins the game to be detected.

    if self.isLossForSide(side: who.side) {
        value = GKGameModelMinScore
    }
    
    if self.isLossForSide(side: who.side.opponent) {
        value = GKGameModelMaxScore
    }
    
    return value
}

My goal in using the GKMinmaxStrategist was to present a computer opponent that wouldn’t be too easy to beat, that would give enough practice for a player so they could learn the game. The model that I’ve tweaked to, I think, does that.

Hexin is available for macOS and iOS. And it is free 🙂