{"id":730,"date":"2017-01-13T21:59:27","date_gmt":"2017-01-14T05:59:27","guid":{"rendered":"http:\/\/www.madpickles.org\/rokjoo\/?p=730"},"modified":"2017-01-13T21:59:27","modified_gmt":"2017-01-14T05:59:27","slug":"hi-ho-cherry-o","status":"publish","type":"post","link":"https:\/\/www.madpickles.org\/rokjoo\/2017\/01\/13\/hi-ho-cherry-o\/","title":{"rendered":"Hi Ho! Cherry-O"},"content":{"rendered":"<p>As our daughter approaches 3 years old she has begun to play some simple board games, one of which is <a href=\"https:\/\/en.wikipedia.org\/wiki\/Hi_Ho!_Cherry-O\" target=\"_blank\">Hi Ho! Cherry-O<\/a>. While playing it recently my wife lamented that the game was taking forever to end. The analysis in the Wikipedia page is for a single player, but the majority of the time 2-4 players are present. It wasn&#8217;t obvious to me how to easily extend the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Markov_chain\" target=\"_blank\">Markov chain<\/a> for a multi-player game. Does one add a 3rd dimension with 1 slice of the transition matrix per player? So instead I wrote a little Python program to play lots of games and compute the mean and standard deviation (it&#8217;s at the end of the post).<\/p>\n<p>I then ran 10,000 simulations each for games of 2-4 players with 10 fruits per tree:<\/p>\n<pre>\r\n$ for i in 2 3 4; do .\/hi-ho-cherry-o.py $i 10 10000; done\r\nplayers,spins,stddev\r\n2,18.619100,12.388267\r\n3,21.197900,12.418629\r\n4,24.335700,12.889896\r\n<\/pre>\n<p>It&#8217;s interesting that the minimum number of spins necessary to win with a single player is 3 and the number of additional spins necessary for a game to end when adding a player is ~3. Now we know 90% of the games we play with our daughter will take fewer than 40 spins, which is comforting. Though it&#8217;s scary to think that 1% of the time a game will take 70 or more!<\/p>\n<pre>\r\n#!\/usr\/bin\/python\r\n\r\nimport random\r\nimport sys\r\nfrom math import sqrt\r\n\r\n\r\ndef pick(num_fruit, max_num_fruit, player, players):\r\n  \"\"\"Execute a turn by picking fruit; modifies the game state.\r\n\r\n  Args:\r\n    num_fruit: If positive, it's as if the player is picking\r\n      fruit from their tree and placing it in their basket. If\r\n      negative, it's as if the player is putting fruit back\r\n      into their tree from their basket.\r\n    max_num_fruit: The maximum amount of fruit in a tree.\r\n    player: The index of the player who's picking.\r\n    players: The list of players in the game.\r\n\r\n  Returns: The amount of fruit left in the player's tree.\r\n  \"\"\"\r\n  new_num_fruit = players[player] - num_fruit\r\n\r\n  # Can't pick more fruit than exist in the tree.\r\n  new_num_fruit = max(new_num_fruit, 0)\r\n\r\n  # Can't put back more fruit than fits in the tree.\r\n  new_num_fruit = min(new_num_fruit, max_num_fruit)\r\n\r\n  players[player] = new_num_fruit\r\n  return new_num_fruit\r\n\r\n\r\ndef spin(max_num_fruit):\r\n  \"\"\"Execute a spin of the wheel.\r\n\r\n  There are 7 possibilities, each with equal probability:\r\n    Pick 1-4 fruit from a tree and place in a basket.\r\n    Put 2 fruit back in the tree (landed on bird or dog).\r\n    Put all fruit back in the tree (broken basket).\r\n\r\n  Args:\r\n    max_num_fruit: The maximum amount of fruit in a tree.\r\n\r\n  Returns: Number of fruit to move. Positive indicates pick\r\n    from the tree, negative indicates put back into the tree.\r\n  \"\"\"\r\n  temp = random.randint(1, 7)\r\n  if temp < 5:\r\n    return temp\r\n  elif temp < 7:\r\n    return -2\r\n  else:\r\n    return max_num_fruit * -1\r\n\r\n\r\ndef play(players, max_num_fruit):\r\n  \"\"\"Plays a complete game.\r\n\r\n  Args:\r\n    players: A list of players taking part in the game.\r\n    max_num_fruit: The maximum amount of fruit in a tree.\r\n\r\n  Returns: The number of spins needed to complete the game.\r\n  \"\"\"\r\n  num_spins = 0\r\n  keep_playing = True\r\n  num_players = len(players)\r\n  while keep_playing:\r\n    for i in xrange(num_players):\r\n      num_spins += 1\r\n      num_fruit_to_pick = spin(max_num_fruit)\r\n      new_num_fruit = pick(\r\n          num_fruit_to_pick, max_num_fruit, i, players)\r\n      if new_num_fruit == 0:\r\n        keep_playing = False\r\n        break\r\n  return num_spins\r\n\r\n\r\ndef mean(data):\r\n  \"\"\"Compute the mean of data.\"\"\"\r\n  n = len(data)\r\n  return sum(data) \/ float(n)\r\n\r\n\r\ndef stddev(data):\r\n  \"\"\"Compute the standard deviation of data.\"\"\"\r\n  c = mean(data)\r\n  ssd = sum((x - c) ** 2 for x in data)\r\n  v = ssd \/ (len(data) - 1)\r\n  return sqrt(v)\r\n\r\n\r\ndef trials(num_players, num_fruit, num_games):\r\n  \"\"\"Play games and compute basic statistics.\r\n  \r\n  Args:\r\n    num_players: The number of players playing the game.\r\n    num_fruit: The amount of fruit in each players tree.\r\n    num_games: The number of games to play.\r\n\r\n  Returns: Mean number and standard deviation of spins\r\n    needed to finish a game.\r\n  \"\"\"\r\n  spins_per_game = []\r\n  while num_games > 0:\r\n    players = [num_fruit] * num_players\r\n    spins_per_game.append(play(players, num_fruit))\r\n    num_games -= 1\r\n  return (mean(spins_per_game), stddev(spins_per_game))\r\n\r\n\r\nif __name__ == '__main__':\r\n  num_players, num_fruit, num_games = map(int, sys.argv[1:4])\r\n  mean_spins, stddev_spins = trials(\r\n      num_players, num_fruit, num_games)\r\n  print '%d,%f,%f' % (num_players, mean_spins, stddev_spins)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>As our daughter approaches 3 years old she has begun to play some simple board games, one of which is Hi Ho! Cherry-O. While playing it recently my wife lamented that the game was taking forever to end. The analysis in the Wikipedia page is for a single player, but the majority of the time [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[4,18,11,17],"_links":{"self":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/730"}],"collection":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/comments?post=730"}],"version-history":[{"count":8,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/730\/revisions"}],"predecessor-version":[{"id":738,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/posts\/730\/revisions\/738"}],"wp:attachment":[{"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/media?parent=730"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/categories?post=730"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madpickles.org\/rokjoo\/wp-json\/wp\/v2\/tags?post=730"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}