<story><title>A way to deal with enormous branching factors in strategy games</title><url>http://togelius.blogspot.com/2016/03/a-way-to-deal-with-enormous-branching.html</url></story><parent_chain></parent_chain><comment><author>dripton</author><text>Link to the actual paper: &lt;a href=&quot;http:&amp;#x2F;&amp;#x2F;julian.togelius.com&amp;#x2F;Justesen2016Online.pdf&quot; rel=&quot;nofollow&quot;&gt;http:&amp;#x2F;&amp;#x2F;julian.togelius.com&amp;#x2F;Justesen2016Online.pdf&lt;/a&gt;&lt;p&gt;I&amp;#x27;ve written an AI for a similar game, where you can&amp;#x27;t always even iterate over all your moves for this turn, let alone do a multi-ply tree search.&lt;p&gt;Using their terminology of Action and Turn, my method was to first evaluate individual Actions using a simpler evaluation function, and apply a cutoff so that only a reasonably number of Actions had to evaluated, then combine that reduced group of Actions together to make a reasonable subset of full Turn moves, then use the full evaluation function to find the best Turn.&lt;p&gt;Writing a good evaluation function for a complex game is hard, so I picked a whole bunch of inputs and then used a genetic algorithm to find weights for them.  (Let the various AIs play entire games, and let the winners breed.)&lt;p&gt;Works okay, but still can&amp;#x27;t beat a decent human player very often.  (There&amp;#x27;s enough randomness in the game that the better player doesn&amp;#x27;t always win.)&lt;p&gt;In this paper, their Online Evolution beat the other four computer strategies, but they don&amp;#x27;t mention whether it can beat good human players.  If it can&amp;#x27;t, it&amp;#x27;s not clear to me whether Online Evolution is a good algorithm.  Beating their other four algorithms doesn&amp;#x27;t seem to be a very high bar.</text></comment>
<story><title>A way to deal with enormous branching factors in strategy games</title><url>http://togelius.blogspot.com/2016/03/a-way-to-deal-with-enormous-branching.html</url></story><parent_chain></parent_chain><comment><author>scrollaway</author><text>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.&lt;p&gt;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&amp;#x27;re able to discard a lot of those options &lt;i&gt;much&lt;/i&gt; more easily than you would in Go&amp;#x2F;Chess (eg. damaging yourself is seldom a good idea).&lt;p&gt;There&amp;#x27;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 &lt;i&gt;radically&lt;/i&gt; alter the game state. So a much fairer approach is to look at a branching factor of about 15, with multiple successive &amp;quot;turns&amp;quot; (eg. each option is a single &amp;quot;turn&amp;quot;, and you can play multiple turns before ceding control to the opponent).</text></comment>