Thread: stochastic process for a chess problem

1. 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

2. 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.

3. Re: stochastic process for a chess problem

How did you do the simulation? thanks

4. Re: stochastic process for a chess problem

Originally Posted by pupupanda
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.

5. 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.

6. 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!

7. 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$.

8. 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.

9. 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.

10. Re: stochastic process for a chess problem

Originally Posted by SlipEternal
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 發送

11. Re: stochastic process for a chess problem

Originally Posted by SlipEternal
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 發送

12. Re: stochastic process for a chess problem

Originally Posted by pupupanda
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.

13. Re: stochastic process for a chess problem

Originally Posted by pupupanda
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.

14. Re: stochastic process for a chess problem

Originally Posted by SlipEternal
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.

15. Re: stochastic process for a chess problem

could you please guide me how to do the simulation i R, thanks

Page 1 of 2 12 Last