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

We respect Your privacy and we neither track You nor use cookies…
7th and the 7th logo are trademarks of 7th Stone Software GmbH. All other product or service names are the property of their respective owners.