Comment by scrollaway | Hacker News Reader

Comment by scrollaway | Hacker News Reader

Small nitpick regarding Hearthstone: Its branching factor is really not that high. Higher than Chess, but not in the same category as Civilization, which gives you thousands to tens of thousands of potential inputs every turn.

In Hearthstone, you have a specific amount of options you can play (anywhere between 0 and 10-ish), and each option may have one or more targets (usually again between 0-10 ish). This sounds high, but you're able to discard a lot of those options much more easily than you would in Go/Chess (eg. damaging yourself is seldom a good idea).

There's often multiple options you can play per turn, but each option has to be evaluated under the current state of the board since playing a single option can radically alter the game state. So a much fairer approach is to look at a branching factor of about 15, with multiple successive "turns" (eg. each option is a single "turn", and you can play multiple turns before ceding control to the opponent).

I think the branching factor is somewhat higher given that the order of actions makes a big difference. Also remember that when playing a card you have to choose where to place it, which can multiply the branching factor by up to 7.

If both of you have 3 minions on the board, each of your minions has a choice of 4 targets, which is already up to 4^3=64 choices. Then considering each order of attacks, and the fact that you can play any card of your hand before or after attacks, and the branching factor has the potential to explode.

For nearly all cases (except some you can specify manually and/or discover through deep learning), you can throw away positioning which is why I didn't mention it.

As for the order of actions, I did mention that. The basis of my argument is that you shouldn't consider an entire player's turn as a "turn"; instead, consider each action as a turn.

Part of the search space though should also consider the global state of the game, which includes things like your own deck, which adds a further complication for forecasting branching.

And if you want to get truly smart, you also have to consider what the opponent might do, which, as viewed by the player, opens up the search space to a lot more cards both in their hand and in their deck.

So yes, each turn the branching options to play is relatively small compared to the other examples. However, the evaluation of future moves and the "true" board state is much, much harder and has a huge branching factor.

I think that's basically what their algorithm does:

> We use an evolutionary algorithm to evolve sequences of actions that could make up a single turn. The fitness function is the quality of the board state of the end of the turn, as measured by some straightforward metrics.

My interpretation of this (and your suggestion) is that they take the number of possible actions in one turn, and prune them according to how they affect the board state. That seems to be what you're describing.

Evaluating those pruned action sets across multiple turns seems like the next logical state.

They claim the pruned branches based on potential actions is a novel approach, but it seems common sense to me and I'd be surprised that several other games aren't already implementing this in some fashion.

Reply on news.ycombinator.com