Pickomino AI

Pickomino is a dice game where each player takes turn rolling eight, six sided, dice. The player tries to build up a high enough total of dice to capture one of the available tiles from the board or from another player. To build up a die total, the player picks a set of dice all showing the same number to save. The player then re-rolls the remaining dice. Each number can only be saved once. If you can’t pick a new number after a roll, or don’t build up enough points to claim a tile, you scratch and have to return a tile. Full rules are here(PDF).

After playing the game a few times, I began to wonder if this game could be “solved” by a computer. Would it be possible to consider all the possible sets to save and all the possible rolls that would result for all the rounds in one player’s turn to determine their best choice.

I started by writing a fairly standard recursive function that looks like this:

choseBestFace()
{
  for each distinct number in the roll
  {
    if we can take a tile with this set
      score = value of the tile
    else
      score = -value of our last tile
    score = max ( score, valueOfRoll(remaining dice after taking this face) )
  }
  return the face with the highest score
}

valueOfRoll(remainingDice)
{
  if ( no remaining dice )
    return score of choseBestFace()
  else
  {
    value = 0;
    for each number of the first remaining die (1-6)
      value = value + valueOfRoll(firstDie, rest of remaining dice)/6
  }
  return value
}

Imagine that we only roll 2 dice and they come up different. Now there are only two options and each option needs to calculate all the possible rolls of 6 dice. There will be a total of 14 calls to these functions. If we have 3 dice that come up different, there would be three options and each would need to try 36 combinations. But lots of those combinations will have a third round of rolling with six more options. It ends up being 1179 function calls. Starting with four dice is 487,636 calls. While this seems like a huge amount, computers are really fast and the result comes back immediately  Five dice is 958,460,025. On my machine, this takes several minutes. The problem space is growing exponentially and there is no way this method will be able to reach six dice, let alone eight.

While debugging and stepping through this code, I was struck by how many times the same problem was being solved. There are lots of ways to get the same set of dice. So, instead of re-calculating the solution each time, the program calculates the result once and then saves it. The input to the valueOfRoll function is the combination of: the number of dice left to roll, the number of each die face that we have saved and the number of each die face in this roll. There ends up being 8*6^8*6^8 = 816 million different ways to call this function (for eight dice). Most of those combinations can’t really happen. After putting in this change, I was shocked by how well it worked. For the same five die problem that ended up calling the functions almost 1 billion times, I ended up with only 4270 unique combinations. It seemed unbelievable till I stepped through the code and realized that one  early cache hit can save thousands of later recursive calls.

With this improvement in, I kept increasing the number of dice to see if I could do all eight. Six dice was 14,574 combinations. Seven dice is 38717 and eight is 93454. On my machine it takes about a fifth of a second to determine the best play.

There are some subtleties of the game that this AI is not considering. It doesn’t consider stealing a tile from another player to be any better or worse than taking a new one from the table. It also doesn’t try to make any calculation about whether a play would cause the game to end sooner or later. Both of these could be added by changing the scoring function, but would involve my judgement about what is best and would not change the overall speed much.