You are here:

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

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>
The NSA May puzzle: