Tic-tac-toe in Erlang — game space search

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. The source file and this tutorial are organized as follows:

Game space search

If you look at the code in the next move calculations and predictions section, you’ll see the functions chain like this.

This is how the program searches the game space. It searches exhaustively, all the way down to finished games. It does not prune the search tree, or estimate the value of intermediate boards, or look for symmetries. It evaluates the same board layout many times over.

So how inefficient is this brute-force solution?

The recursion is not deep since all games are over in 9 moves or less, but it is wide. If you ignored collisions and games that ended early you’d end up looking at 387,420,489 (9 to the 9th power) leaf states, each representing a path thru the game space. Getting rid of collisions reduces that number to 362,880 (9 factorial), assuming you start with a blank board. Still a big number, but more than 1000 times smaller than the original.

But 362,880 still looks pretty big compared to all the possible full boards. There are only (9 choose 5) ((9! / (5!)(4!)) -> 126) ways to arrange 5 Xs and 4 Os on a tic-tac-toe board.

If you also trim back game paths that are won or lost before 9 moves, you end up with 255,168 leaf states (paths through the game space), 209,088 winning games and 46,080 ties. Again, this assumes you start with an empty board and calculate outcomes for each of the 9 starting spots.

Another measure of the search space is to count the nodes of the search space instead of just the leaves. We can do that by counting how many times given_move_predict_outcome(..) is evaluated. Starting with an empty board, calling predict_outcomes(..) will visit 2,653,002 nodes in the search tree, although most of them are collisions. 549,945 are not collisions, including 255,168 won/lost/tied boards and games that are not yet decided.

These numbers all assume we are predicting the outcome for all 9 positions on an empty board. The numbers drop quickly after you X a single spot. The following table shows how putting a single mark on the tic-tac-toe board reduces the game search space dramatically.

Empty board Board with single corner X Board with single side X Board with center X
All nodes in game-space
search tree
2,653,002 287,757 308,817 266,697
All boards in
search tree
(nodes excluding collisions)
549,945 59,704 63,904 55,504
Undecided boards 294,777 31,972 34,312 29,632
Decided boards
(won, lost, or tied)
255,168 27,732 29,592 25,872
Winning and
losing boards
209,088 22,548 24,408 21,264
Tied boards
(cat games)
46,080 5,184 5,184 4,608

When you search the game space tree for an empty board, you end up with tie-game predictions for starting moves in each of the 9 open spaces. So I coded that into tic.erl (the tic-tac-toe program in Erlang). At first I wasn’t going to include even that simple optimization (optimization was not the goal), but without it the program pauses for a couple seconds when you start a new game. Apparently calling a couple functions 2,653,002 times isn’t instantaneous.

But any way you slice it, you have admit we’re doing an awful lot of work for a game with only 126 final board positions. And that’s not even counting rotation and reflection redundancies and games that end before the board is full. There’s no way you could call this efficient.

But in this case it doesn’t really matter. It’s efficient enough for a sample program.

Comments

33 Responses to “Tic-tac-toe in Erlang — game space search”

  1. Blank Board Game. | 7Wins.eu on June 28th, 2009 8:39 am

    […] Tic-tac-toe in Erlang — game space search : Code Obscurata […]

  2. http://criminalbackgroundchecked.com/ on July 4th, 2012 12:16 pm

    Keep it up! I think you will probably not care if I browse around your blog a bit more.
    “We must laugh at man, to avoid crying for him. by Napoleon Bonaparte.

  3. visit their website ourmidland on July 7th, 2012 8:55 am

    Its first-class site, I was looking for something like this

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

    I have been exploring for a bit for any highquality
    articles or weblog posts in this kind of area . Exploring in Yahoo I eventually stumbled upon this website.
    Studying this info So im satisfied to exhibit that Ive an incredibly
    just right uncanny feeling I found out exactly what I needed.

    I most indubitably will make certain to dont fail to
    remember this website and provides it a look a continuing.

  5. 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 sm on July 8th, 2012 2:17 pm

    I wish to express my appreciation to you just for bailing
    me from this setting. Just after researching through
    the internet and seeing basics which were not pleasant, I thought my entire life was done.
    Living minus that the answers to the problems youve fixed through your entire short post is usually a serious case,
    as well as ones that might have in a wrong manner damaged my entire career if
    I hadnt come across your web page. That the training and kindness in maneuvering every item was very
    helpful. I am not sure what I would have done if I hadnt encountered such a point such
    as this. I can at this point relish my future. Thanks so
    much for the high quality and result oriented help. I wont hesitate to suggest your site to any person who requires guide on this subject.

  6. business grants for single mothers on July 8th, 2012 3:27 pm

    senior living can be costly if you have not found a very good corporation or that offers a great deal,

  7. loans for single mothers on July 8th, 2012 4:22 pm

    you possess a great blog here! would something like to
    have invite posts on my tiny blog

  8. cell phone lookup on July 8th, 2012 4:45 pm

    Hello there! This is my first comment here so I just wanted to hand over a quick shout
    out and say I really enjoy reading through your blog posts.
    Can you recommend any other web sites/internet sites/forums that
    cover that the same subjects Thank you!

  9. scholarships for children of single mothers on July 8th, 2012 5:00 pm

    you possess a great blog here! wish to have invite posts on my tiny
    blog

  10. reverse phone lookup on July 9th, 2012 4:36 pm

    I made blue cupcakes with chocolate frosting to announce to my in
    laws. That they loved that the idea. that they had to peel the paper off to reveal the color.

  11. cell phone lookup on July 10th, 2012 4:20 am

    My favorite town from all Ive been to, has to be Zurich Switzerland.

    Switzerland is one of the best skiing areas. Something I absolutely love, it
    is peacefull and comforting.

  12. http://www.prlog.org/11306717-phone-number-lookup-is-your-partner-cheating-on-you.html on July 16th, 2012 12:45 pm

    First-class post. I had been looking at constantly
    this blog site that im influenced! Very helpful info particularly that the
    remaining period I sustain such info a lot. I had been seeking this kind of info to obtain a prolonged moment.
    Thank you and greatest of excellent fortune.

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

    naturally like your web site however you have to test the spelling on several of your posts.

    Many of them are rife with spelling issues and I find it very troublesome to tell
    the reality however I will definitely come again again.

  14. cell phone number lookup on July 16th, 2012 2:09 pm

    fapturbo review Hello! I just want to make a large thumbs up for the fantastic info youve here on this
    post. Ill be returning to your site to find more detailed soon.

  15. reverse phone lookup on July 16th, 2012 2:26 pm

    I located your own entry intriguing do Ive additional the Trackback
    into it on my website

  16. http://www.prlog.org/11734648-criminal-background-check-public-records.html on July 16th, 2012 3:21 pm

    Spot on with this writeup, I really assume this website wants much more consideration.
    in all probability be again to read approach more, thanks for the info.

  17. http://www.prlog.org/11674605-reverse-phone-lookup-finders.html on July 16th, 2012 3:31 pm

    If some one desires to be updated with latest technologies then he must be pay
    a quick visit this web site and be up to date everyday.

  18. http://www.youtube.com/watch?v=c3-A_ZxBlSQ on July 16th, 2012 4:57 pm

    It is easy to get a hold of visibly a pack to discover about this particular.
    I actually suppose you made certain excellent factors in functions also.

  19. http://www.prlog.org/11306749-phone-number-lookup-got-cheating-wife-on-your-hands.html on July 16th, 2012 6:04 pm

    I was wondering when you ever considered changing that the layout of your blog
    It’s very well written I love what youve got to say. However maybe you could a tiny more in the means of content so people could connect with it better. Youve got an awful lot of text for merely having one or two images. Maybe you could space it out better

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

    I?m not that much of a online reader to be honest but
    your blogs really nice, keep it up! I’ll go ahead and bookmark your website to come back down the road. Cheers

  21. http://ezinearticles.com/?Cell-Phone-Number-Directories---Can-You-Use-It-to-Catch-a-Cheating-Partner?&id=5985845 on July 16th, 2012 8:22 pm

    Hiya, have you ever in your life thought about to create
    about Nintendo or PS handheld

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

    i would love to search for some free of charge calendars via that the
    internet, are there have been websites or company that gives
    one,.

  23. http://officialreversephonelookup.com/ on July 16th, 2012 9:02 pm

    Your means of explaining everything in this article is truly pleasant,
    all be capable of effortlessly know it, Thanks a lot.

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

    Hmm it appears like your blog ate my first comment (it
    was super long) so I guess I’ll just sum it up what I wrote and say, I’m thoroughly enjoying your blog. I too am an aspiring blog blogger but I’m still new to the whole thing. Do you have any helpful hints for first-time blog writers? I’d certainly appreciate it.

  25. http://ezinearticles.com/?Reverse-Phone-Lookup---Easy-Way-to-Know-the-Truth&id=5909597 on July 17th, 2012 2:08 am

    Heya i am for the first time here. I found this board and I get a hold of It truly useful & it helped me out much.

    Im hoping to offer one thing back and aid others for example you helped me.

  26. people search on July 17th, 2012 2:36 am

    I was wondering if you ever considered changing that the layout of your
    blog Its very well written I love what youve got
    to say. However maybe you could a minor more in that the means of
    content so people could connect with it better. Youve got an awful lot of text
    for merely having one or two images. Maybe you could space it
    out better

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

    I simply wanted to thank you vastly all over again. I am not sure that the things I
    might have accomplished without those aspects shown by you on such problem.
    It had been a real distressing condition in my view, nevertheless taking note of an specialized manner you resolved that the issue forced me
    to jump with happiness. Im just happy for this assistance as well because hope you really be acquainted with
    what a powerful job that you have been carrying
    out instructing most people thru a blog. Im certain you have never come across
    all of us.

  28. make money online on July 27th, 2012 6:36 am

    Can I simply say exactly what a relief to obtain somebody who truly knows what theyre speaking about on the web.

    You definitely get how to bring a difficulty to light and work out it critical.
    The diet should see this and can see this side of your
    story. I cant believe youre less wellliked since you absolutely present the gift.

  29. http://officialreversephonelookup.com/ on August 1st, 2012 3:37 am

    I think other web site proprietors should take this
    web site as an model, very clean and wonderful
    user genial style and design, let alone that the content.
    You

  30. make money online review image source on August 3rd, 2012 3:45 pm

    You require to seek out involved in the tournament personally of the best online pages via internet.
    I most certainly will recommend this web site!

  31. best reverse cell phone lookup on August 20th, 2012 8:39 am

    Have you ever considered about including a little bit more than just your articles I mean, what you say is fundamental
    and all. Nevertheless just imagine whenever you added some great graphics or videos
    to give away your posts more, “pop! Your content is fine in spite of this with images and clips, this site
    could certainly be one of the greatest in it’s field. Great blog!

  32. Tic-tac-toe in Erlang — alternative rules (Y pattern) : Code Obscurata on August 24th, 2012 6:20 pm

    […] Game space search […]

  33. Tic-tac-toe in Erlang — parallel processing : Code Obscurata on August 24th, 2012 6:27 pm

    […] Game space search […]