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 tiecnt
// 0 1 2
// 3 4 5
// 6 7 8
: moves ( arr -- )
"000000000"
rot str$
concat$ 9 right$
2dup 0 3 sub$ type cr
2dup 3 6 sub$ type cr
6 9 sub$ type cr
."–––" 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
begin
fields size 0>
while
fields |<@ drop
repeat
;
: won? ( -- boolean )
wins @ for
board forobj 0 @ @ dup ' ' != if
board forobj 0 @ @
board forobj 1 @ @ ==
swap board forobj 2 @ @ ==
and if
true
exit
then
then
each
false
;
: game ( -- boolean )
switch x?
x? on
board 9 ' ' fill
emptyFields
9 0 do
i fields | loop
0 9 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
5000 0 do
game not if
tiecnt @ 1+ tiecnt !
then
gamecnt @ 1+ gamecnt !
loop
;
clear
."May is running..."
cr
cr
: May
20 0 do
play
tiecnt @ gamecnt @ / .
4 spaces
."(" 8 63 / . .")"
4 spaces
tiecnt @ . space ."ties in " gamecnt @ . space ."games"
cr
cr
loop
;
May
forget wins
8 array wins
0 value gamecnt
0 value tiecnt
// 0 1 2
// 3 4 5
// 6 7 8
: moves ( arr -- )
"000000000"
rot str$
concat$ 9 right$
2dup 0 3 sub$ type cr
2dup 3 6 sub$ type cr
6 9 sub$ type cr
."–––" 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
begin
fields size 0>
while
fields |<@ drop
repeat
;
: won? ( -- boolean )
wins @ for
board forobj 0 @ @ dup ' ' != if
board forobj 0 @ @
board forobj 1 @ @ ==
swap board forobj 2 @ @ ==
and if
true
exit
then
then
each
false
;
: game ( -- boolean )
switch x?
x? on
board 9 ' ' fill
emptyFields
9 0 do
i fields | loop
0 9 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
5000 0 do
game not if
tiecnt @ 1+ tiecnt !
then
gamecnt @ 1+ gamecnt !
loop
;
clear
."May is running..."
cr
cr
: May
20 0 do
play
tiecnt @ gamecnt @ / .
4 spaces
."(" 8 63 / . .")"
4 spaces
tiecnt @ . space ."ties in " gamecnt @ . space ."games"
cr
cr
loop
;
May
The program output
May is running...
0.1288 (0.12698413) 644 ties in 5000 games
0.1273 (0.12698413) 1273 ties in 10000 games
0.12486667 (0.12698413) 1873 ties in 15000 games
0.1264 (0.12698413) 2528 ties in 20000 games
0.12544 (0.12698413) 3136 ties in 25000 games
0.1242 (0.12698413) 3726 ties in 30000 games
0.12445714 (0.12698413) 4356 ties in 35000 games
0.1253 (0.12698413) 5012 ties in 40000 games
0.12544444 (0.12698413) 5645 ties in 45000 games
0.1264 (0.12698413) 6320 ties in 50000 games
0.12641818 (0.12698413) 6953 ties in 55000 games
0.12625 (0.12698413) 7575 ties in 60000 games
0.12687692 (0.12698413) 8247 ties in 65000 games
0.1272 (0.12698413) 8904 ties in 70000 games
0.12677333 (0.12698413) 9508 ties in 75000 games
0.127025 (0.12698413) 10162 ties in 80000 games
0.12698824 (0.12698413) 10794 ties in 85000 games
0.12687778 (0.12698413) 11419 ties in 90000 games
0.1266 (0.12698413) 12027 ties in 95000 games
0.12672 (0.12698413) 12672 ties in 100000 games
ok>
0.1288 (0.12698413) 644 ties in 5000 games
0.1273 (0.12698413) 1273 ties in 10000 games
0.12486667 (0.12698413) 1873 ties in 15000 games
0.1264 (0.12698413) 2528 ties in 20000 games
0.12544 (0.12698413) 3136 ties in 25000 games
0.1242 (0.12698413) 3726 ties in 30000 games
0.12445714 (0.12698413) 4356 ties in 35000 games
0.1253 (0.12698413) 5012 ties in 40000 games
0.12544444 (0.12698413) 5645 ties in 45000 games
0.1264 (0.12698413) 6320 ties in 50000 games
0.12641818 (0.12698413) 6953 ties in 55000 games
0.12625 (0.12698413) 7575 ties in 60000 games
0.12687692 (0.12698413) 8247 ties in 65000 games
0.1272 (0.12698413) 8904 ties in 70000 games
0.12677333 (0.12698413) 9508 ties in 75000 games
0.127025 (0.12698413) 10162 ties in 80000 games
0.12698824 (0.12698413) 10794 ties in 85000 games
0.12687778 (0.12698413) 11419 ties in 90000 games
0.1266 (0.12698413) 12027 ties in 95000 games
0.12672 (0.12698413) 12672 ties in 100000 games
ok>