Tic-tac-toe in Erlang — smart game space

This is part of an Erlang tutorial built around a tic-tac-toe program. The program is stuffed into one file, called tic.erl and available here.

There are also smaller Erlang modules for analyzing game-spaces called tic_count.erl and tic_game_space.erl.

The tutorial is organized as follows:

Smart game space

In the previous post we talk about the full tic-tac-toe game space and all possible board arrangements. The tic_game_space:report0() function from tic_game_space.erl tells us there are 255,168 possible tic-tac-toe games and 5478 distinct tic-tac-toe board arrangements. Or if we treat all rotations and reflections of a board as equal, those counts are reduced to 26,830 games and 765 boards.

But some of these games are very unlikely, and require one or both players to pass up obvious wins and make other mistakes. Most players are unlikely to ever encounter many of these boards without perverse effort. So the question arises, how big is tic-tac-toe if you assume the players are rational.

There is code in tic_game_space.erl to answer that question. Starting from the full game space, the function smart_game_space(..) is able to strip out all the unwise moves and leave us with only the “smart” game paths. The number of boards for each ply in the smart game space is given in the following table.

Number of marks on board Number of boards treating rotations and reflections as unique Number of boards treating rotations and reflections as equal
0 (0+0) 1 1
1 (1+0) 9 3
2 (1+1) 24 5
3 (2+1) 102 16
4 (2+2) 136 18
5 (3+2) 176 23
6 (3+3) 180 24
7 (4+3) 164 22
8 (4+4) 76 10
9 (5+4) 16 3
Totals 884 125

All smart games end after 9 moves in a tie so there are no winning boards in this game space. You can only win in tic-tac-toe if the other player makes a mistake.

The number of boards is reduced from 5478 in the full game space to 884 in the smart game space. In the modulo all-reflections-rotations game space the board count is reduced from 765 to 125.

The reports from tic_game_space.erl provide more details. For example, we learn there are only 3584 games in the smart game space, reduced from 255,168 in the full space. Here are the reports that treat rotated and reflected boards as unique.

Eshell V5.6.5  (abort with ^G)
1> c( 'c:/src/erlang/tic_game_space',
1>   {d, no_rotation_relection_collapse}).
{ok,tic_game_space}
2> tic_game_space:report1( ).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Total number of game paths: 3584

  Total number of boards: 884
    Player 1 winning boards : 0
    Player 2 winning boards : 0
    Player 1 must respond to: 417
    Player 2 must respond to: 451
    Tie boards              : 16

  Total number of boards can also be broken down as:
    Initial board count        : 1
    Boards produced by player 1: 467
    Boards produced by player 2: 416

ok
3> tic_game_space:report1( ply_overview).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Player 1 moves, leading to ply 1
    9 boards (all continue to ties)
  Player 2 moves, leading to ply 2
    24 boards (all continue to ties)
  Player 1 moves, leading to ply 3
    102 boards (all continue to ties)
  Player 2 moves, leading to ply 4
    136 boards (all continue to ties)
  Player 1 moves, leading to ply 5
    176 boards (all continue to ties)
  Player 2 moves, leading to ply 6
    180 boards (all continue to ties)
  Player 1 moves, leading to ply 7
    164 boards (all continue to ties)
  Player 2 moves, leading to ply 8
    76 boards (all continue to ties)
  Player 1 moves (last move)
    16 tie boards
ok

Here are the reports that treat rotated and reflected boards as equal. The boards in the first three plys are also listed. Notice there are only 336 games in the game space, down from 26,830 in the full game space.

Eshell V5.6.5  (abort with ^G)
1> c( 'c:/src/erlang/tic_game_space').
{ok,tic_game_space}
2> tic_game_space:report1( ).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Total number of game paths: 336

  Total number of boards: 125
    Player 1 winning boards : 0
    Player 2 winning boards : 0
    Player 1 must respond to: 58
    Player 2 must respond to: 64
    Tie boards              : 3

  Total number of boards can also be broken down as:
    Initial board count        : 1
    Boards produced by player 1: 67
    Boards produced by player 2: 57

ok
3> tic_game_space:report1( ply_overview).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Player 1 moves, leading to ply 1
    3 boards (all continue to ties)
  Player 2 moves, leading to ply 2
    5 boards (all continue to ties)
  Player 1 moves, leading to ply 3
    16 boards (all continue to ties)
  Player 2 moves, leading to ply 4
    18 boards (all continue to ties)
  Player 1 moves, leading to ply 5
    23 boards (all continue to ties)
  Player 2 moves, leading to ply 6
    24 boards (all continue to ties)
  Player 1 moves, leading to ply 7
    22 boards (all continue to ties)
  Player 2 moves, leading to ply 8
    10 boards (all continue to ties)
  Player 1 moves (last move)
    3 tie boards
ok
4> tic_game_space:report1( 0).           
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Boards in ply 0
    ...    X..  .X.  ...  
    ... -> ...  ...  .X.  
    ...    ...  ...  ...  

ok
5> tic_game_space:report1( 1).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Boards in ply 1
    X..    X..  
    ... -> .O.  
    ...    ...  

    .X.    OX.  .X.  .X.  
    ... -> ...  .O.  ...  
    ...    ...  ...  .O.  

    ...    O..  
    .X. -> .X.  
    ...    ...  

ok
6> tic_game_space:report1( 2).
Smart tic-tac-toe game space:
  Player 1: all smart moves
  Player 2: all smart moves

  Boards in ply 2
    X..    XX.  X.X  X..  X..  
    .O. -> .O.  .O.  .OX  .O.  
    ...    ...  ...  ...  ..X  

    OX.    X.O  X..  OX.  OX.  
    ... -> ..X  ..X  X..  .X.  
    ...    ...  ..O  ...  ...  

    O..    X.O  X..  OX.  O..  
    .X. -> .X.  .X.  .X.  .XX  
    ...    ...  ..O  ...  ...  

    .X.    XX.  X..  .X.  
    .O. -> .O.  .OX  XO.  
    ...    ...  ...  ...  

    .X.    XX.  XO.  .X.  .X.  
    ... -> ...  ...  X.O  .X.  
    .O.    .O.  .X.  ...  .O.  

ok

It’s interesting to see that the first player can start anywhere, but the 2nd player’s first move is constrained. If the first player starts in the middle, the 2nd player must play a corner to avoid losing. If the 1st player starts in the corner the 2nd player must respond by marking the middle. And if the first player starts on the side, the 2nd player must play a corner next to the first player’s mark, or play the middle, or play the side directly opposite.

The listing of the boards for ply 8 (which isn’t shown here) also includes one board where the middle is the one space not filled in. I didn’t expect to see this — I assumed the middle would always be marked after the first 3 or 4 ply. Even tic-tac-toe can hold surprises.

Hmmm, the Wikipedia entry for tic-tac-toe mentions some people also treat a Y-shaped arrangement of marks as a win. I wonder how that affects the game space?

Comments

46 Responses to “Tic-tac-toe in Erlang — smart game space”

  1. http://criminalbackgroundchecked.com/ on July 4th, 2012 12:20 pm

    Im really enjoying that the design and layout of your
    site. It can be a very easy on that the eyes which makes it much
    more pleasant for me to come here and visit more often. Did you hire out a designer
    to create your theme Great work!

  2. ourmidland website on July 7th, 2012 8:57 am

    Only desire to say your article is because astounding.
    That the clearness in your post is only spectacular and i can assume you
    are an expert on this subject. Well with your permission
    let me to grab your feed to keep updated with forthcoming post.
    Thanks a million and please keep up that the gratifying
    work.

  3. scholarships for single mothers on July 8th, 2012 3:41 am

    when using hair dryers, it would be better to use those low wattage types because they are not very damaging
    to the hair.

  4. scholarships for college students|scholarships for college students in texas|2011 scholarships for college students|scholarships for college students in california|scholarships for college students 2011|easy scholarships for college students|grants and sc on July 8th, 2012 2:21 pm

    With havin so much content and articles do you ever run into any other problems of plagorism or copyright
    infringement My site has a lot of exclusive content
    Ive either authored myself or outsourced in spite of this it seems lots of it is popping it up
    all over the web without my authorization. Do you recognize
    any ways to help protect against content from being stolen Id certainly appreciate it.

  5. education grants for single mothers on July 8th, 2012 3:35 pm

    This is certainly my initial stop by and I actually such as
    what Im seeing. Your weblog is so much fun to look over,
    quite compelling as well as informative. Ill undoubtedly recommend it to
    my friends. Nevertheless, I did have some
    question with the commenting. It kept giving me an question whenever I clicked on publish
    comment. I hope, that can be fixed. A lot of thanks

  6. free assistance for single mothers on July 8th, 2012 4:27 pm

    Spot up for this writeup, I honestly think this fabulous website wants a large amount more consideration.
    Ill likely to end up again you just read a great
    deal more, thanks for the information.

  7. scholarships grants for single mothers on July 8th, 2012 5:05 pm

    Thanks, I enjoyed Gulvafslibning Kurt Gulvmand.
    It was good. View my blog sometime, it all about Altamonte Springs, FL Real Estate.

  8. reverse phone lookup on July 9th, 2012 4:38 pm

    hello!,I love your writing vastly! percentage we keep in touch more about your article on
    AOL I need a specialist on this space to resolve my
    query. May be thats you! Searching forward to see you.

  9. 411 reverse cell phone lookup on July 10th, 2012 4:26 am

    This is very interesting! Great information and it is also very well written.
    I will bookmark and comeback soon.

  10. scholarships for mothers on July 11th, 2012 4:33 am

    You need to take part from a contest for just one of that the finest online resources over
    the internet. Ill recommend this website!

  11. number lookup on July 16th, 2012 12:50 pm

    Wohh just what I was seeking for, thankyou for putting up.

  12. http://www.prlog.org/11734629-phone-number-search-reverse-number-lookup.html on July 16th, 2012 1:06 pm

    Hey I know this is off topic but I was wondering if you knew of any
    widgets I could add to my blog that automatically tweet my
    newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this. Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates.

  13. http://www.prlog.org/11161236-cell-phone-number-lookup-free-can-you-really-get-one-for-free.html on July 16th, 2012 2:12 pm

    Howdy sir, you have a really nice blog layout “

  14. reverse phone on July 16th, 2012 2:29 pm

    Greetings! I recognize this is kinda off topic then again Id figured Id ask.

    Would you be interested in trading links or maybe guest authoring a blog
    article or viceversa My site addresses lots of the same subjects because yours and I believe we could greatly
    benefit from each other. Whenever you have been interested feel free to send me
    an email. I look forward to hearing from you! Wonderful blog by that the means!

  15. criminal background check on July 16th, 2012 3:29 pm

    you might have an amazing blog right here! would
    you for instance to make some invite posts on my weblog

  16. reverse phone lookup on July 16th, 2012 3:35 pm

    You actually make it seem really easy together with your presentation however I to find this matter to be really one thing which
    I believe I might never understand. It kind of feels too complex and extremely broad for me.
    I’m taking a look forward to your next post, I’ll attempt to get the hold of it!

  17. reverse phone lookup on July 16th, 2012 4:59 pm

    all we want is of course a firm skin which is very smooth.
    great skin comes with great genetics and proper maintennance

  18. phone number lookup on July 16th, 2012 6:11 pm

    Its laborious to locate knowledgeable folks on this matter, on that
    the other hand you sound something like you
    realize what youre speaking about! Thanks

  19. http://www.prlog.org/11734625-reverse-cell-phone-directory-finds-anyone-with-telephone-number.html on July 16th, 2012 8:25 pm

    This design is wicked! You definitely know how to keep a reader entertained.
    Between your wit and your videos, I was almost moved to start my own
    blog (well, almost…HaHa!) Wonderful job. I really enjoyed what you had to say, and more
    than that, how you presented it. Too cool!

  20. phone number on July 16th, 2012 8:26 pm

    There is noticeably lots of dough to know about this.

    I suppose youve made particular nice points in functions
    also.

  21. http://ezinearticles.com/?Reverse-Address-Lookup---Get-the-Information-You-Need-the-Easy-Way&id=5909554 on July 16th, 2012 8:56 pm

    I think you have remarked some very interesting
    points , thanks for the post.

  22. reverse phone lookup on July 16th, 2012 9:14 pm

    Hi there I am so delighted I found your site, I really found you
    by mistake, while I was researching on Bing for something else, Regardless I am here now and would just
    like to say many thanks for a marvelous post and a
    all round entertaining blog (I also love the theme/design),
    I don?t have time to read it all at the moment but I have bookmarked it
    and also added your RSS feeds, so when I have time I
    will be back to read a lot more, Please do keep up the superb b.

  23. http://www.prlog.org/11684341-reverse-cell-phone-lookup-number.html on July 16th, 2012 10:30 pm

    I have read so many content on the topic of
    the blogger lovers except this post is genuinely a nice piece of writing, keep it up.

  24. reverse phone on July 17th, 2012 2:12 am

    What your saying is absolutely genuine. I recognize that everybody must
    say the same matter, but I just think that you
    set it in the technique that everybody can understand. I also enjoy that the images
    you set in right here. They fit so nicely with what youre attempting to say.
    Im certain youll get to so many individuals with what youve received
    to say.

  25. people search on July 17th, 2012 2:38 am

    Wonderful site. I hope you write more informative articles, as i will check back often to read your posts.

  26. http://ezinearticles.com/?Phone-Number-Search---Stopping-a-Cheater-the-Easy-Way&id=5909547 on July 17th, 2012 2:39 am

    Super information it’s really. My friend has been hunting for this information.

  27. reverse phone number lookup on July 17th, 2012 2:43 am

    somtimes i also sell stuffs on craigslists as there are many users in it

  28. http://www.cellphonelookuped.com/ on July 17th, 2012 11:43 pm

    Im not that much of an internet reader to be honest however your websites actually nice,
    keep it up! Ill go ahead and bookmark your website to come back later on.
    All that the best Miss Herbal Vitamins

  29. http://www.prlog.org/11261550-phone-number-lookup-catch-cheater-quickly.html on July 25th, 2012 2:03 am

    When visiting web pages, i always look for a very nice content like
    yours ,

  30. how to make money online on July 27th, 2012 6:40 am

    There is noticeably a lot of dollar comprehend this.
    I assume youve made specific nice points in functions also.

  31. Marcus on July 30th, 2012 10:29 pm

    It was very well authored and easy to seek out the picture.
    Unlike additional website pages I have read which are actually not excellent.
    I also found your posts very interesting.

  32. Lily28Hill on August 3rd, 2012 3:00 am

    It’s perfect that people can receive the loans moreover, this opens up completely new possibilities.

  33. http://www.reversephonelookuped.com/ on August 5th, 2012 3:44 pm

    I loved because much as you will receive carried out right here.
    The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command find out got an impatience over you to wish be delivering that the following.
    unwell unquestionably come more formerly again as exactly the same nearly a ton often inside case you
    shield this increase.

  34. reverse phone lookup on August 11th, 2012 5:34 am

    There a few interesting points soon enough on this page conversely
    I do not determine if all of themcenter to heart.
    There is some validity on the other hand I will take hold opinion until I check into it further.
    Great post , thanks and that we want a large amount
    more! Put into FeedBurner at that the same time

  35. reverse phone lookup on August 11th, 2012 5:49 am

    Thank you for the excellent writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you! Conversely, how
    can we communicate

  36. reverse phone lookup on August 11th, 2012 6:01 am

    Perhaps you’ll want to update that the php server on your webhost, WordPress is kinda slow.

  37. cell phone lookup on August 11th, 2012 6:01 am

    Youre so cool! I dont suppose Ive read anything in this line
    of attack just before. So nice to lookup for somebody by
    original ideas on this subject. realy thank you for beginning this up.
    this site have been some things which can
    be required via the internet, someone after some originality.
    useful query for bringing an additional challenge to the web!

  38. reverse phone lookup on August 11th, 2012 6:06 am

    This is the precise blog for anyone who wants to get out about this topic.

    You realize a ton it is almost tough to argue with you not that I actually would wantHaHa.
    You positively put a different spin on a subject thats been written about for years.

    Great stuff, just great!

  39. reverse phone on August 11th, 2012 6:41 am

    Do you write more It merely required a few moments
    to see your entry and so have an awareness that
    I identify most people miss out on. Getting more people to join that the discussion is generally a great thing.

  40. reverse lookup on August 11th, 2012 6:58 am

    Fantastic post in spite of this , I was wondering if you could write a litte more on this subject Id be
    very thankful if you could elaborate a little bit more. Cheers!

  41. Kevin on August 13th, 2012 11:43 am

    When I originally commented I clicked that the
    Notify me when new surveys have been added checkbox and these
    days whenever a comment is added I receive four emails using
    that the same comment. Possibly there is in spite of this
    you’ll be able to eliminate me from that service Thanks!

  42. Anonymous on August 13th, 2012 1:15 pm

    Magnificent goods from you, man. I have understand your stuff
    prior to and youre just too wonderful. I really just like what you have acquired here,
    really just like what youre saying and the way in which you say it.
    You make it entertaining and you still take care of to keep it wise.

    I cant wait to read much more out of you. This is really
    a terrific site.

  43. Stella on August 16th, 2012 12:22 pm

    very nice publish, i definitely love this web site, carry on it

  44. cell phone lookup on August 16th, 2012 4:12 pm

    I want to express appreciation to you just for bailing me out of this particular difficulty.

    Because a result of seeking out throughout the internet and seeing notions that were not beneficial, I was
    thinking my entire life was over. Being alive devoid of that the advice
    to that the issues you have solved by tactic of the
    guide is often a serious case, as well as those
    that might have badly damaged my career if I hadnt noticed that the blog.
    That the knowhow and kindness in controlling all the things was very helpful.
    I am not sure what I wouldve done if I had not discovered such a subject for instance this.
    It can be probable to at this time look forward to my future.
    Thanks for your time vastly for the professional and sensible guide.
    I wont think twice to propose your web blog
    to any other individual who requires counselling about this subject.
    visit here alternative medicine

  45. cell phone lookup on August 19th, 2012 11:02 pm

    my grandmother is always into herbal stuffs and she always say
    that ayurvedic medicines are that the best
    stuff

  46. reverse phone lookup cell on August 23rd, 2012 7:53 pm

    I would actually for example that you become a guest poster on my blog.