NB. The latter portion of this code demonstrates
NB. various Markov chain computations.
Note 'code notes'
Use Raul Miller's easy, useful
NOUN Adverb Conjunction verb
name convention.
Data structure:
o Board is a vector tallying *:N. Apparently, I
have virtualized BOARD. It exists in thought
only.
o The state is vector of 2 boxed knight paths
with next to move at head.
program should work for N in [3,9]
The upper limit stems from the chess
algebraic display algorithm.
1 piece moves each ply
)
N=: 8
NB. convert array coordinates to vector index
index=: N&#.
GRID=: 2 ({@:# <@:i.) N
CELLS=: ,/@:> GRID
JUMPS=: (, |."1) 1 2 *"1 (1 1,_1 1,_1 _1,:1 _1)
LC=: 26 }. Alpha_j_ NB. lowercase
CD=: }. Num_j_ NB. counting digits
NAMES=: ((LC {~ {.) , (CD {~ {:))"1 CELLS
NB. T are the circle of moves from each square
T=: <"2 CELLS+"1/JUMPS
NB. VerifyRange Interval is (]
NB. 0 means in range, 1 for outside
VerifyRange=: &(1 ~: I.)
assert 1 1 0 0 0 0 1 1 1 1 -: 1 5 VerifyRange i.10
Note 'why adverb?'
I like adverbs. When I write in other languages I
hard-code constants, then I have to rewrite,
extracting and naming constants to generalize my
code. Adverbs will help me overcome this.
)
assert 0 -: 2 9 VerifyRange N NB. process check
none=: +:/ NB. works for a pair of numbers
MOVES2D=: (#~ none"1@:((_1+0,N)VerifyRange))&.> T
MOVES=: index&.> MOVES2D
NB. sorry, I like commuted hook
'WN BN'=: 2 ((A.~ ?)~ index) 1 1 ,: N - 2 2
choose=: {~ ?@:#
move=: choose@:>@:({&MOVES)
While=: conjunction def 'u^:v^:_'
position=: {:@:>
continue=: ~:&position/
assert 1 -: continue 2 3;4
assert 0 -: continue 2 3;4 2 3
ply=: {: , (, move@:position)&.>@:{.
NB. run the simulation
PATHS=: WN ply While continue@:;&, BN
NB. report
WN 4 : 0 PATHS
NB. algebraic notation for the moves
AN=. (('N' , [ , ' N' , ])/"2) NAMES {~ ,.&>/ y
NB. display the numbered moves
smoutput 'Move 0 shows setup.'
smoutput 'White plays first. Black wins.'
smoutput (,.~ '. ' ,"1~ ":@:,.@:i.@:#) AN
)
Note 'Markov chain'
Consider an (*:N) by (*:N) transition matrix.
Each row represents a square on the chess board,
so does each column. The row is the starting
square, the column is the index of end square.
The value at each row column cell is the
probability to move to the cell of the column
starting from the cell of the row. For example,
the first row represents the corner cell a1. From
a1 there are two legal moves, with equal
probability. Those two columns in top row will
have probability 1r2.
The probability that a knight is located at a
square is the matrix product of the current
location vector by the transition probability
matrix. Repeat the matrix multiplication for each
hop. Begin!
)
NB. transition probability matrix
NB. sorry, I like commuted hook
P=: ((%@:x:@:#@:[`[`]}~ >)~"0 1 (0 $~ ,~@:#)) MOVES
Note 'transition probability matrix'
4x4 symmetric corner of 8x8 chess board.
The display is chopped at right hand side for email.
Perhaps difficult to understand.
a1 a2 a3 a4..b1 b2 b3 b4..c1 c2 c3 c4..d
+--------------------------------------------------
a1| 0 0 0 0 0 0 1r2 0 0 1r2 0 0
a2| 0 0 0 0 0 0 0 1r3 1r3 0 1r3 0
a3| 0 0 0 0 1r4 0 0 0 0 1r4 0 1r4
a4| 0 0 0 0 0 1r4 0 0 0 0 1r4 0
.
b1| 0 0 1r3 0 0 0 0 0 0 0 1r3 0
b2| 0 0 0 1r4 0 0 0 0 0 0 0 1r4 1r
b3|1r6 0 0 0 0 0 0 0 1r6 0 0 0
b4| 0 1r6 0 0 0 0 0 0 0 1r6 0 0
.
c1| 0 1r4 0 0 0 0 1r4 0 0 0 0 0
c2|1r6 0 1r6 0 0 0 0 1r6 0 0 0 0
c3| 0 1r8 0 1r8 1r8 0 0 0 0 0 0 0 1r
c4| 0 0 1r8 0 0 1r8 0 0 0 0 0 0
.
d1| 0 0 0 0 0 1r4 0 0 0 0 1r4 0
d2| 0 0 0 0 1r6 0 1r6 0 0 0 0 1r6
d3| 0 0 0 0 0 1r8 0 1r8 1r8 0 0 0
d4| 0 0 0 0 0 0 1r8 0 0 1r8 0 0
)
start=: (i.@:# P)&=
mp=: +/ .*
Note 'various probabilities'
NB. percent probability to land on a square
NB. after 80 and 81 jumps.
NB. Observe the white-black alternation.
<.0.5+100*(_1 x: P)mp~^:80 81(start@:index 1 1)
1 0 2 0 2 0 2 0 0 2 0 4 0 4 0 2 2 0 5 0 5 0 4 0...
0 2 0 2 0 2 0 1 2 0 4 0 4 0 2 0 0 4 0 5 0 5 0 2...
NB. probability sum 1, knight still on board.
+/"1 (_1 x: P) mp~^:80 81 (start@:index 1 1)
1 1
NB. compute probability to be on same square
NB. after 6 hops. Different question from
NB. "The first time they meet is at move 6."
NB. locations after 6 hops
HOPS=: 6
P_CELL=: WN mp&(_1 x: P)^:HOPS@:,:&start BN
NB. show the probabilities (clipped at 50 colum
_ 50 {. 6j3 ": P_CELL
0.013 0.000 0.030 0.000 0.026 0.000 0.016 0.000 0
0.007 0.000 0.016 0.000 0.018 0.000 0.016 0.000 0
NB. Probability to share square at move 6
mp/ P_CELL
0.0349013
NB. Probability to share after
NB. 0, 2, ... , 22 plies.
NB. (display clipped!)
mp/"2 WN mp&(_1 x: P)^:(<12)@:,:&start BN
0 0 0.0117188 0.0226508 0.0313695 0.0322698 0.0349
NB. First capture can occur at move 2.
)
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
