Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2009-05-18 14:40:05

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Chutes and Ladders

An interesting problem that occured to me..

In the classic game of chutes and ladders, what is the average number of dice rolls to win? cool


A logarithm is just a misspelled algorithm.

Offline

#2 2009-05-18 16:48:52

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Chutes and Ladders

We could write the game, then simulate it many times.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#3 2009-05-18 17:05:00

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Chutes and Ladders

we just need to write a truly random number generator first! ;]

that sounds like fun though, i think i'm going to do it! thanks for the suggestion, i'll post my results later.

Last edited by mikau (2009-05-18 17:06:13)


A logarithm is just a misspelled algorithm.

Offline

#4 2009-05-18 18:29:55

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

Using a Markov chain for a 1 player game:

Minimum game length: 7
Expected game length: 39.59
Maximum game length: Unbounded
25% chance game ends in 21 spins or less
50% chance game ends in 32 spins or less
75% chance game ends in 49 spins or less
95% chance game ends in 89 spins or less

Last edited by bobbym (2009-05-18 19:11:09)


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#5 2009-05-18 18:52:58

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Chutes and Ladders

39.59? Are you sure?

I wrote a simple simulation, and ran it twice, playing 1 million games each time. The average was about 35.8 with the 4th significant digit varying. Then I ran it twice, playing ten million games each time, and it also produced 35.8 with a varying 4th digit. The consistency seems pretty convincing..

Anyway, here is my program for anyone who is curious. The real meat of the program is the first two functions. Its written in Java, and pretty easy to read.

public class ChutesAndLadders
{
   // a program to simulate chutes and ladders games
   // and measure the average number of rolls to win

public static int playGame()
{
  // simulates a game, returns the number of rolls

  int location=0;
  int diceRolls=0;
  boolean gameover=false;


  while (!gameover)
  {

      location+=diceRoll();
      diceRolls++;
      location=additionalJumps(location); // jump forward if necessary


      if (location >= 100)
      gameover=true;

   }

   return diceRolls;

}

public static void main(String[] args)
{

	// play this many games
	int numGames=10000000; // ten million

	long totalRolls=0;

	for (int i = 0; i < numGames; i++)
	{
		totalRolls+=playGame();
	}

	double average=totalRolls/(double)(numGames);
	System.out.println("Finished! average number of rolls: " + average);
}

public static int diceRoll()
{
	// simulates a dice roll
	return 1 + (int)(6*Math.random());
}

public static int additionalJumps(int location)
{
	/* returns the location of the other end of a slide or ladder
	// if 'location' falls on one,
	// Returns the original location otherwise*/

	switch(location)
	{

	case 1: location=38; break;
	case 4: location= 14; break;
	case 9: location= 31; break;
	case 16: location= 6; break;
	case 21: location= 42; break;
	case 28: location= 84; break;
	case 36: location= 44; break;
	case 47: location=26; break;
	case 49: location= 11; break;
	case 51: location= 67; break;
	case 56: location= 53; break;
	case 62: location= 19; break;
	case 64: location= 60; break;
	case 71: location=91; break;
	case 80: location= 100; break;
	case 87: location= 24; break;
	case 93: location= 73; break;
	case 95: location= 75; break;
	case 98: location= 78; break;


	}


	return location;
}



}

output:

Finished! average number of rolls: 35.8300908
Press any key to continue . . .

Last edited by mikau (2009-05-18 18:57:00)


A logarithm is just a misspelled algorithm.

Offline

#6 2009-05-18 18:58:06

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

Hi Mikau;

Sorry, I got called away and couldn't complete the post. I didn't mean to make the post sound so authoritative. I got the information here:
http://www.math.byu.edu/~jeffh/mathematics/games/chutes/index.htm
He could have made a mistake. Another site claims the expected number of throws is ≈ 42. He used a C++ program that he ran 10000 times. But I think this is too high.

Last edited by bobbym (2009-05-18 19:37:05)


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#7 2009-05-18 19:14:38

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

One possible problem with your code is that you cannot go over 100 to end the game, I think you have to equal 100 to end it.


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#8 2009-05-18 19:57:19

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Chutes and Ladders

good point.. but is that an official rule?

well if you consider that it takes approximately 36 moves to cross the board, according to my program, and it should take on average, 6 more rolls to land exactly on the finish line, that comes out to be 42. A hasty and imperfect analysis but the 42 answer would make sense.

I'll modify my program tomorrow to prevent it from going beyond 100.


A logarithm is just a misspelled algorithm.

Offline

#9 2009-05-18 20:01:34

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

Hi mikau,

  I don't know if that is an official rule. He says it is. It should take less than 6 more rolls because 36 would sometimes be sufficient to get to 100.

Please provide me with the new answers you get as I am away from my machine and cannot run any program myself.

Last edited by bobbym (2009-05-18 20:02:58)


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#10 2009-05-19 03:18:04

integer
Member
Registered: 2008-02-21
Posts: 79

Re: Chutes and Ladders

I will ask someone who actually plays the game.

Offline

#11 2009-05-19 08:05:35

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Chutes and Ladders

here we go, a quick modification to the playGame function:

public static int playGame()
{
  // simulates a game, returns the number of rolls

  int location=0;
  int diceRolls=0;
  boolean gameover=false;
  int roll=0;

  while (!gameover)
  {

      roll=diceRoll();
      diceRolls++;

      if (roll + location <= 100)
      {
		  location+=roll;
      	  location=additionalJumps(location); // jump forward if necessary


      	  if (location == 100)
      	  gameover=true;
       }

   }

   return diceRolls;

}

result of 10 million games:

Finished! average number of rolls: 39.2347894
Press any key to continue . . .

Looks like 39 rolls was correct after all!

Last edited by mikau (2009-05-19 08:05:52)


A logarithm is just a misspelled algorithm.

Offline

#12 2009-05-19 08:12:34

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

Hi mikau;

Thanks for the work, would have been more fun if you could have found him wrong.

Last edited by bobbym (2009-05-19 08:14:09)


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#13 2009-05-19 09:38:24

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,711

Re: Chutes and Ladders

Love It!


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#14 2009-05-21 08:44:22

integer
Member
Registered: 2008-02-21
Posts: 79

Re: Chutes and Ladders

The person I talked to who actually plays Chutes-&-Ladders (BTW he is four years old ) said that you roll the dice "until I win."
That removes a little bit of the randomness from the game.

A google search turned up an interesting article written by Dr. David L. Morgan (http://www.math.niu.edu/~rusin/uses-math/games/chutes/) then states that the math average is 2.35 spaces per turn or 42.5 turns per game.  He includes a C source code program to simulate the game.  After a run of 10000 (ten thou) game the average number of turns per game was 35.7534

Actually that is more than I need to know about the game, if I'm going to lose when I play the game.

Last edited by integer (2009-05-21 08:44:44)

Offline

#15 2009-05-21 09:01:33

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Chutes and Ladders

Hi integer;

  I found that site too, see post #6, we think he is too high. Think that Mikau and the the guy from BYU (post # 4) are giving the correct answers.

  That kid sounds like me when I was 4. Very commendable.

Last edited by bobbym (2009-05-21 09:21:01)


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB