Page 1 of 2 12 LastLast
Results 1 to 15 of 19
Like Tree3Thanks

Thread: stochastic process for a chess problem

  1. #1
    Newbie pupupanda's Avatar
    Joined
    Mar 2017
    From
    new zealand
    Posts
    19

    stochastic process for a chess problem

    In chess, if the rook can move either horizontally or vertically with any distance, with 50/50 chance to move vertical or horizontal. how can I calculate the expected time that the rook move from the lower left corner to the upper right corner? thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,605
    Thanks
    2367

    Re: stochastic process for a chess problem

    Solving this in closed form seems very complicated.

    Simulation shows it takes 5.7 moves on average.

    This assumes choosing direction from a (1/2,1/2) distribution and the number of moves to a uniform distribution of 8 choices.

    If the resulting movement goes off the board the movement is restricted to stay on the board.

    One could modify this to alter the number of moves to be uniform over the number of valid moves possible to stay on the board.

    This results in an average of 10.79 moves.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie pupupanda's Avatar
    Joined
    Mar 2017
    From
    new zealand
    Posts
    19

    Re: stochastic process for a chess problem

    How did you do the simulation? thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    5,605
    Thanks
    2367

    Re: stochastic process for a chess problem

    Quote Originally Posted by pupupanda View Post
    How did you do the simulation? thanks
    actually I have to redo the whole thing. I didn't take into account moving left or down.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    Break the board up into types of squares. You have the starting square where you can only move up or right. You have the end, and you have two more corners (where the end position is possible. Then you have the left wall and the bottom wall (by symmetry, these are similar) and the top wall and right wall (again, similar). Finally, you have the 36 cells in the middle (all similar).

    Let's name the cell types. Starting cell is $A_1$. Top left and bottom right squares are $A_2$. The twelve squares of the left wall and bottom wall that are not corners: $A_3$. The twelve squares of the top and right walls that are not corners: $A_4$. The 36 middle squares: $A_5$. The finish line: $A_6$.

    From $A_1$, there is a two in 14 chance of going from $A_1$ to $A_2$ and a 12 out of 14 chance to go from $A_1$ to $A_3$.

    Figure out probabilities from $A_2$ to every group it could wind up in. Basically, you want to know the probabilities of the rook changing state. This basically turns into a Markov chain (or is it a semi-Markov chain?) I'm not quite sure what the difference is.
    Thanks from pupupanda
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    Better solution.
    Only 3 types of squares: squares that are minimum 2 squares away (bottom left 49 squares)
    Squares that are min one move away (14 of the remaining squares)
    The one square that is 0 away.

    $E(2,0)$ is the expected number of moves to get from the first group of squares to the finish. $E(1,0)$ is the expected number of moves to get from a square one away to the finish. Now you just need a system of two equations to solve for both!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    Ok, I have a little more time now. To answer more clearly, if the rook is in $A_2$ (any of the 49 squares with a minimum of 2 moves to get to the top right square), the rook 12 possible moves that will keep it in $A_2$, and 2 possible moves that will put it in $A_1$ (the 14 squares on the top rank or the rightmost file that do not include the top right square). If the rook is in one of the squares in $A_1$, then there are 6 possible moves that will keep it in $A_1$, one move that will bring it to $A_0$, which is just the top-right square (the finish line, so to speak), and 7 moves that will bring it to $A_2$.

    To make notation a little easier, let's use $E_2$ as the expected number of moves to get from $A_2$ to $A_0$ and $E_1$ as the expected number of moves to get from $A_1$ to $A_0$. These expected values should satisfy the following equations:

    $E_2 = \dfrac{12}{14}\left(1+E_2\right) + \dfrac{2}{14}\left(1+E_1\right)$
    $E_1 = \dfrac{7}{14}\left(1+E_2\right) + \dfrac{6}{14}\left(1+E_1\right) + \dfrac{1}{14}\left(1\right)$

    This gives $E_2 = 70$ and $E_1 = 63$.
    Last edited by SlipEternal; May 11th 2017 at 05:25 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    I just ran an Excel simulation to test out my results. In cell A1, I put the number 2.
    In cell A2, I put the formula:
    =IF(A1=2,CHOOSE(INT(RAND()*14+1),2,2,2,2,2,2,2,2,2 ,2,2,2,1,1),IF(A1=1,CHOOSE(INT(RAND()*14+1),2,2,2, 2,2,2,2,1,1,1,1,1,1,0),0))
    I copied that formula to cells A2:A5000
    In cell A5001, I put the formula:
    =COUNTIF(A1:A5000,">0")
    I then copied column A to columns A:SF (that's 500 columns).
    In cell A5002, I put the formula:
    =AVERAGE(A5001:SF5001)
    Every time I run this simulation, I get very close to 70.
    Last edited by SlipEternal; May 11th 2017 at 05:40 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    If the rook may only move up and to the right, then this changes things. It starts off as being $(7,7)$ squares away (meaning it needs to move up 7 and right 7 to get to its target).
    The first move has a uniform distribution of odds for which move the rook will make (a $\dfrac{1}{14}$ chance for each move).
    The second move will not have a uniform distribution of odds for which move the rook will make.
    Suppose the rook moves exactly one square on the first move. Then it is either at $(6,7)$ or $(7,6)$. By symmetry, we the probabilities will be the same, so $E_{(6,7)} = E_{(7,6)}$ and similarly for $E_{(a,b)} = E_{(b,a)}$. Now, there is a $\dfrac{1}{12}$ chance for any of the six positions in the same direction it has already moved, but a $\dfrac{1}{14}$ chance for any position in the direction it has not moved.

    So, $E_{(7,7)} = \dfrac{2}{14}\left(7+E_{(6,7)}+E_{(5,7)}+E_{(4,7)} +E_{(3,7)}+E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)$
    $E_{(6,7)} = \dfrac{1}{12}\left(6+E_{(5,7)}+E_{(4,7)}+E_{(3,7)} +E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)+\dfrac{1}{14 }\left(7+E_{(6,6)}+E_{(5,6)}+E_{(4,6)}+E_{(3,6)}+E _{(2,6)}+E_{(1,6)}+E_{(0,6)}\right)$
    $\displaystyle E_{(a,b)} = \dfrac{1}{2\cdot a}\sum_{i=0}^{a-1}\left(1+E_{(i,b)}\right) + \dfrac{1}{2\cdot b}\sum_{j=0}^{b-1}\left(1+E_{(a,j)}\right)$

    To calculate $E_{(7,7)}$, again I used Excel.
    In cell A1, I put 0.
    In cell B1, I put the formula:
    =1+SUM($\$$A1:A1)/(COLUMN()-1)
    I copied that formula to B1:H1
    In cell A2, I put the formula:
    =1+SUM(A$\$$1:A1)/(ROW()-1)
    I copied that formula to A2:A8
    In cell B2, I put the formula:
    =1+SUM(B$\$$1:B1)/(2*(ROW()-1))+SUM($\$$A2:A2)/(2*(COLUMN()-1))
    I copied that formula to B2:H8

    In cell H8, I should have $E_{(7,7)} = 5.185714$.
    If you do it in Mathematica, you can get an exact result instead of Excel's approximation.
    Last edited by SlipEternal; May 11th 2017 at 07:38 AM.
    Thanks from pupupanda
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie pupupanda's Avatar
    Joined
    Mar 2017
    From
    new zealand
    Posts
    19

    Re: stochastic process for a chess problem

    Quote Originally Posted by SlipEternal View Post
    If the rook may only move up and to the right, then this changes things. It starts off as being $(7,7)$ squares away (meaning it needs to move up 7 and right 7 to get to its target).
    The first move has a uniform distribution of odds for which move the rook will make (a $\dfrac{1}{14}$ chance for each move).
    The second move will not have a uniform distribution of odds for which move the rook will make.
    Suppose the rook moves exactly one square on the first move. Then it is either at $(6,7)$ or $(7,6)$. By symmetry, we the probabilities will be the same, so $E_{(6,7)} = E_{(7,6)}$ and similarly for $E_{(a,b)} = E_{(b,a)}$. Now, there is a $\dfrac{1}{12}$ chance for any of the six positions in the same direction it has already moved, but a $\dfrac{1}{14}$ chance for any position in the direction it has not moved.

    So, $E_{(7,7)} = \dfrac{2}{14}\left(7+E_{(6,7)}+E_{(5,7)}+E_{(4,7)} +E_{(3,7)}+E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)$
    $E_{(6,7)} = \dfrac{1}{12}\left(6+E_{(5,7)}+E_{(4,7)}+E_{(3,7)} +E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)+\dfrac{1}{14 }\left(7+E_{(6,6)}+E_{(5,6)}+E_{(4,6)}+E_{(3,6)}+E _{(2,6)}+E_{(1,6)}+E_{(0,6)}\right)$
    $\displaystyle E_{(a,b)} = \dfrac{1}{2\cdot a}\sum_{i=0}^{a-1}\left(1+E_{(i,b)}\right) + \dfrac{1}{2\cdot b}\sum_{j=0}^{b-1}\left(1+E_{(a,j)}\right)$

    To calculate $E_{(7,7)}$, again I used Excel.
    In cell A1, I put 0.
    In cell B1, I put the formula:
    =1+SUM($\$$A1:A1)/(COLUMN()-1)
    I copied that formula to B1:H1
    In cell A2, I put the formula:
    =1+SUM(A$\$$1:A1)/(ROW()-1)
    I copied that formula to A2:A8
    In cell B2, I put the formula:
    =1+SUM(B$\$$1:B1)/(2*(ROW()-1))+SUM($\$$A2:A2)/(2*(COLUMN()-1))
    I copied that formula to B2:H8

    In cell H8, I should have $E_{(7,7)} = 5.185714$.
    If you do it in Mathematica, you can get an exact result instead of Excel's approximation.
    Thank you so much!!!



    從我的iPhone使用Tapatalk 發送
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie pupupanda's Avatar
    Joined
    Mar 2017
    From
    new zealand
    Posts
    19

    Re: stochastic process for a chess problem

    Quote Originally Posted by SlipEternal View Post
    If the rook may only move up and to the right, then this changes things. It starts off as being $(7,7)$ squares away (meaning it needs to move up 7 and right 7 to get to its target).
    The first move has a uniform distribution of odds for which move the rook will make (a $\dfrac{1}{14}$ chance for each move).
    The second move will not have a uniform distribution of odds for which move the rook will make.
    Suppose the rook moves exactly one square on the first move. Then it is either at $(6,7)$ or $(7,6)$. By symmetry, we the probabilities will be the same, so $E_{(6,7)} = E_{(7,6)}$ and similarly for $E_{(a,b)} = E_{(b,a)}$. Now, there is a $\dfrac{1}{12}$ chance for any of the six positions in the same direction it has already moved, but a $\dfrac{1}{14}$ chance for any position in the direction it has not moved.

    So, $E_{(7,7)} = \dfrac{2}{14}\left(7+E_{(6,7)}+E_{(5,7)}+E_{(4,7)} +E_{(3,7)}+E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)$
    $E_{(6,7)} = \dfrac{1}{12}\left(6+E_{(5,7)}+E_{(4,7)}+E_{(3,7)} +E_{(2,7)}+E_{(1,7)}+E_{(0,7)}\right)+\dfrac{1}{14 }\left(7+E_{(6,6)}+E_{(5,6)}+E_{(4,6)}+E_{(3,6)}+E _{(2,6)}+E_{(1,6)}+E_{(0,6)}\right)$
    $\displaystyle E_{(a,b)} = \dfrac{1}{2\cdot a}\sum_{i=0}^{a-1}\left(1+E_{(i,b)}\right) + \dfrac{1}{2\cdot b}\sum_{j=0}^{b-1}\left(1+E_{(a,j)}\right)$

    To calculate $E_{(7,7)}$, again I used Excel.
    In cell A1, I put 0.
    In cell B1, I put the formula:
    =1+SUM($\$$A1:A1)/(COLUMN()-1)
    I copied that formula to B1:H1
    In cell A2, I put the formula:
    =1+SUM(A$\$$1:A1)/(ROW()-1)
    I copied that formula to A2:A8
    In cell B2, I put the formula:
    =1+SUM(B$\$$1:B1)/(2*(ROW()-1))+SUM($\$$A2:A2)/(2*(COLUMN()-1))
    I copied that formula to B2:H8

    In cell H8, I should have $E_{(7,7)} = 5.185714$.
    If you do it in Mathematica, you can get an exact result instead of Excel's approximation.
    Will you be able to help me to do the simulation in R? I never learned how to do things in Excel so couldn't quiet figure out how to do it in Excel. Thank you


    從我的iPhone使用Tapatalk 發送
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,194
    Thanks
    2624
    Awards
    1

    Re: stochastic process for a chess problem

    Quote Originally Posted by pupupanda View Post
    Will you be able to help me to do the simulation in R? I never learned how to do things in Excel so couldn't quiet figure out how to do it in Excel. Thank you
    從我的iPhone使用Tapatalk 發送
    I must tell you that the set up of the question is not at all clear.
    Keeping with Slip's notation $A_{1,1}$ is lower left & $A_{8,8}$ is upper right.
    I first assumed that the rules of chess apply.
    Starting lower left, two choices:
    1. go up OR go right.
    2. then how many squares, from one to seven.


    Suppose you go Up five squares and land on $A_{6,1}$. Now there are more choices to make:
    1. Up or Down OR go Right
    2. how many squares?

    Suppose you go Right two squares and land on $A_{6,3}$.

    From $A_{6,3}$ we can go Up or Down OR go Right or Left. Each of those has a restriction on the number of squares.


    This is a variation on the classic random walk problems.
    Now I know you may never have considered this or more likely this is not what the setup is at all.
    Please reply and clarify the question.
    Last edited by Plato; May 11th 2017 at 12:02 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    Quote Originally Posted by pupupanda View Post
    Will you be able to help me to do the simulation in R? I never learned how to do things in Excel so couldn't quiet figure out how to do it in Excel. Thank you


    從我的iPhone使用Tapatalk 發送
    romsek would be better able to do the simulation. I set it up to calculate the actual Expected Value rather than the simulated one. The Excel formulas I gave were how I structured my calculations (basically, a table). This should be easy enough to do in R, as well. Maybe if I have some free time this weekend, I could work on it. But, simulations are really not my specialty.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,596
    Thanks
    989

    Re: stochastic process for a chess problem

    Quote Originally Posted by SlipEternal View Post
    Ok, I have a little more time now. To answer more clearly, if the rook is in $A_2$ (any of the 49 squares with a minimum of 2 moves to get to the top right square), the rook 12 possible moves that will keep it in $A_2$, and 2 possible moves that will put it in $A_1$ (the 14 squares on the top rank or the rightmost file that do not include the top right square). If the rook is in one of the squares in $A_1$, then there are 6 possible moves that will keep it in $A_1$, one move that will bring it to $A_0$, which is just the top-right square (the finish line, so to speak), and 7 moves that will bring it to $A_2$.

    To make notation a little easier, let's use $E_2$ as the expected number of moves to get from $A_2$ to $A_0$ and $E_1$ as the expected number of moves to get from $A_1$ to $A_0$. These expected values should satisfy the following equations:

    $E_2 = \dfrac{12}{14}\left(1+E_2\right) + \dfrac{2}{14}\left(1+E_1\right)$
    $E_1 = \dfrac{7}{14}\left(1+E_2\right) + \dfrac{6}{14}\left(1+E_1\right) + \dfrac{1}{14}\left(1\right)$

    This gives $E_2 = 70$ and $E_1 = 63$.
    I think this is the solution I like the best. This allows the rook to move in any direction. My second solution only allows the rook to move up and to the right.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie pupupanda's Avatar
    Joined
    Mar 2017
    From
    new zealand
    Posts
    19

    Re: stochastic process for a chess problem

    could you please guide me how to do the simulation i R, thanks
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Stochastic Process and net gain help
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: Nov 6th 2012, 09:35 AM
  2. ACF of stochastic process
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Sep 11th 2011, 12:23 AM
  3. predictable stochastic process
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Apr 16th 2011, 05:16 AM
  4. stochastic process ???
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Mar 11th 2008, 03:23 AM
  5. Stochastic Process
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Apr 19th 2007, 06:56 PM

Search Tags


/mathhelpforum @mathhelpforum