Tic-Tac-Toe
What is the probability a game will end in a draw?
The program is pretty straigt forward:
The computer plays games, count the number of played games and count the number of games ending in a draw.
The solution strives towards 8/63.
(* to verify: probability of a draw == 8/63 (0,126984126984127) *)
forget wins
8 array wins
0 value gamecnt
0 value wincnt
// 0 1 2
// 3 4 5
// 6 7 8
: moves ( arr -- )
"000000000"
rot str$
concat$ 9 right$
cr
2dup 0 3 sub$ type cr
2dup 3 6 sub$ type cr
6 9 sub$ type cr
."–––"
;
: win ( n1 n2 n3 -- arr )
3 int-array arr
arr clone
swap over 0 !
swap over 1 !
swap over 2 !
;
0 1 2 win wins 0 ! (* all winning positions *)
3 4 5 win wins 1 !
6 7 8 win wins 2 !
0 3 6 win wins 3 !
1 4 7 win wins 4 !
2 5 8 win wins 5 !
0 4 8 win wins 6 !
2 4 6 win wins 7 !
9 char-array board (* the play field *)
0 int-array fields
: emptyFields
0 fields a:!
;
: won? ( -- boolean )
wins @ for
board forobj 0 @ @ dup ' ' != if
board forobj 0 @ @
board forobj 1 @ @ ==
swap board forobj 2 @ @ ==
and if
true
exit
then
else
drop
then
each
false
;
: game ( -- boolean )
switch x?
x? on
board 9 ' ' fill
emptyFields
9 0 do
i fields |<!
loop
0 10 do
x? @ if
x? off
'x'
else
x? on
'o'
then
board
fields i random <@
!
won? if
// board @ moves (* uncomment to see the moves *)
true
exit
then
-1 +loop
won?
;
: play
20000 0 do
game if
wincnt @ 1+ wincnt !
then
gamecnt @ 1+ gamecnt !
loop
;
clear
."May is running..." cr
: May
20 0 do
play
gamecnt @ wincnt @ - gamecnt @ / .
4 spaces
."(" 8 63 / . .")"
4 spaces
gamecnt @ wincnt @ - . space ."ties in " gamecnt @ . space ."games" cr
cr
loop
;
May
forget wins
8 array wins
0 value gamecnt
0 value wincnt
// 0 1 2
// 3 4 5
// 6 7 8
: moves ( arr -- )
"000000000"
rot str$
concat$ 9 right$
cr
2dup 0 3 sub$ type cr
2dup 3 6 sub$ type cr
6 9 sub$ type cr
."–––"
;
: win ( n1 n2 n3 -- arr )
3 int-array arr
arr clone
swap over 0 !
swap over 1 !
swap over 2 !
;
0 1 2 win wins 0 ! (* all winning positions *)
3 4 5 win wins 1 !
6 7 8 win wins 2 !
0 3 6 win wins 3 !
1 4 7 win wins 4 !
2 5 8 win wins 5 !
0 4 8 win wins 6 !
2 4 6 win wins 7 !
9 char-array board (* the play field *)
0 int-array fields
: emptyFields
0 fields a:!
;
: won? ( -- boolean )
wins @ for
board forobj 0 @ @ dup ' ' != if
board forobj 0 @ @
board forobj 1 @ @ ==
swap board forobj 2 @ @ ==
and if
true
exit
then
else
drop
then
each
false
;
: game ( -- boolean )
switch x?
x? on
board 9 ' ' fill
emptyFields
9 0 do
i fields |<!
loop
0 10 do
x? @ if
x? off
'x'
else
x? on
'o'
then
board
fields i random <@
!
won? if
// board @ moves (* uncomment to see the moves *)
true
exit
then
-1 +loop
won?
;
: play
20000 0 do
game if
wincnt @ 1+ wincnt !
then
gamecnt @ 1+ gamecnt !
loop
;
clear
."May is running..." cr
: May
20 0 do
play
gamecnt @ wincnt @ - gamecnt @ / .
4 spaces
."(" 8 63 / . .")"
4 spaces
gamecnt @ wincnt @ - . space ."ties in " gamecnt @ . space ."games" cr
cr
loop
;
May
The program output
0.12693571 (0.12698413) 17771 ties in 140000 games
0.126575 (0.12698413) 20252 ties in 160000 games
0.12668889 (0.12698413) 22804 ties in 180000 games
0.126625 (0.12698413) 25325 ties in 200000 games
0.12683182 (0.12698413) 27903 ties in 220000 games
0.12699167 (0.12698413) 30478 ties in 240000 games
0.12704615 (0.12698413) 33032 ties in 260000 games
0.12693929 (0.12698413) 35543 ties in 280000 games
0.12708667 (0.12698413) 38126 ties in 300000 games
0.1271375 (0.12698413) 40684 ties in 320000 games
0.12712059 (0.12698413) 43221 ties in 340000 games
0.12690833 (0.12698413) 45687 ties in 360000 games
0.12694474 (0.12698413) 48239 ties in 380000 games
0.12693 (0.12698413) 50772 ties in 400000 games
ok>