{"id":1475,"date":"2023-09-26T20:53:28","date_gmt":"2023-09-26T18:53:28","guid":{"rendered":"http:\/\/blog.schmoigl-online.de\/?p=1475"},"modified":"2023-09-26T23:20:52","modified_gmt":"2023-09-26T21:20:52","slug":"preparations-tic-tac-toe-and-ai","status":"publish","type":"post","link":"http:\/\/blog.schmoigl-online.de\/?p=1475","title":{"rendered":"Preparations: Tic-Tac-Toe and AI (Part 1)"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">You might still remember the times when you played Tic-Tac-Toe (a.k.a. noughts and crosses) in your childhood:<\/p>\n\n\n\n<figure class=\"wp-block-image size-medium\"><a href=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-7.png\"><img loading=\"lazy\" decoding=\"async\" width=\"300\" height=\"252\" src=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-7-300x252.png\" alt=\"Tic-Tac-Toe board with X having won the game.\" class=\"wp-image-1476\" srcset=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-7-300x252.png 300w, http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-7.png 339w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">In a series of blog posts I want to apply neural networks on this well-known game. But before we may do that, we need to do some preparations.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Eventually, we want to teach a neural network to determine:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>if a board has a winner,<\/li>\n\n\n\n<li>who the winner is, and<\/li>\n\n\n\n<li>after which move the winner has won the board.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">To be able to properly describe such a board, we need to define an order on the board. I decided to take the order &#8220;top-left to bottom-right&#8221; like this:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><a href=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-8.png\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-8.png\" alt=\"\" class=\"wp-image-1478\" style=\"width:371px;height:309px\" width=\"371\" height=\"309\" srcset=\"http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-8.png 369w, http:\/\/blog.schmoigl-online.de\/wp-content\/uploads\/grafik-8-300x250.png 300w\" sizes=\"auto, (max-width: 371px) 100vw, 371px\" \/><\/a><\/figure>\n\n\n\n<p class=\"wp-block-paragraph\">You may also apply a different, more sophisticated scheme for defining the position, but let&#8217;s keep it simple.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">With this nomenclature, we now can describe the board mentioned initially using a set of integers: <code>1,6,9,5,4,7,3,8,2<\/code>. Even more interesting this become, if you consider this not being a set but a list (including order). That is important, because a board may have two &#8220;winners&#8221;, depending on which player came first. Note that<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>by definition, let us assume that X starts the game,<\/li>\n\n\n\n<li>every other round, it is the other&#8217;s player to move (even positions are &#8216;O&#8217; moves, odd positions are &#8216;X&#8217; moves), and<\/li>\n\n\n\n<li>that there are always exactly nine positions in total until the board is fully populated (also called an assignment). <\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Moreover, the list must not have any duplicates: <code>1,1,1,1,1,1,1,1,2<\/code> may also be a list of numbers, but this does not describe a proper Tic-Tac-Toe game, because the position 1 appears more than once. Therefore, the generation of the list represents a system of choosing without repetition. That brings us to another aspect: We first need to determine, if a list of integers is a valid board after all.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">[to be continued on the next page]<\/p>\n\n\n\n<!--more-->\n\n\n\n<p class=\"wp-block-paragraph\">Training neural networks means that you<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>need a lot of data, and<\/li>\n\n\n\n<li>you need to run a regression model applying backpropagation<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">To be able to do that, we need to generate all possible combinations and store them for training and evaluation later on. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Here is a Jupyter notebook with a data generator, which exactly does this:<\/p>\n\n\n<div class=\"wp-downloadmanager\"><p><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"wp-downloadmanager-sprite\" aria-hidden=\"true\" focusable=\"false\"><symbol id=\"wp-downloadmanager-icon-file\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-archive\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M11 3h2v2h-2zM11 6h2v2h-2zM11 9h2v2h-2zM10.5 13h3v3.5h-3z\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-audio\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M10 18.5v-5l5-1.5v5\" \/><circle cx=\"9\" cy=\"18.5\" r=\"1.4\" \/><circle cx=\"14\" cy=\"17\" r=\"1.4\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-code\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M10.5 12.5 8 15.5l2.5 3M13.5 12.5 16 15.5l-2.5 3\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-document\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M9 12.5h6M9 15.5h6M9 18.5h4\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-image\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><circle cx=\"10\" cy=\"13.5\" r=\"1.1\" \/><path d=\"M8 19.5l3-3 2 2 3-3.5 2 4.5z\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-presentation\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M9 19.5v-3M12 19.5v-5.5M15 19.5v-8\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-spreadsheet\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M8 12.5h8v7H8zM8 16h8M11.5 12.5v7\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-video\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><path d=\"M10.5 13.5l5 3-5 3z\" \/><\/symbol><symbol id=\"wp-downloadmanager-icon-application\" viewBox=\"0 0 24 24\" fill=\"none\" stroke=\"currentColor\" stroke-width=\"1.4\" stroke-linecap=\"round\" stroke-linejoin=\"round\"><path d=\"M6 2.5h7l5 5v14H6z\" \/><path d=\"M13 2.5v5h5\" \/><circle cx=\"12\" cy=\"16.5\" r=\"2\" \/><path d=\"M12 12.5V14M12 19v1.5M8.5 16.5H10M14 16.5h1.5\" \/><\/symbol><\/svg><svg class=\"wp-downloadmanager-icon\" aria-hidden=\"true\" focusable=\"false\"><use href=\"#wp-downloadmanager-icon-archive\" \/><\/svg>&nbsp;&nbsp;<strong><a href=\"http:\/\/blog.schmoigl-online.de\/?dl_id=11\">tic-tac-toe-datagenerator.zip<\/a><\/strong> (1.7 KiB, 1,031 hits)<\/p><\/div>\n\n\n\n<p class=\"wp-block-paragraph\">Essentially this notebook does:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>Generate all possible assignments of nine positions with values from the range [1..9] (with repetition),<\/li>\n\n\n\n<li>Determine which of those assignments are without repetition (then called &#8220;valid board&#8221;),<\/li>\n\n\n\n<li>Determine if there is a winner,<\/li>\n\n\n\n<li>Determine who is the winner,<\/li>\n\n\n\n<li>Determine after which move the winner was clear.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">The result is stored in a gzipped<sup data-fn=\"c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d\" class=\"fn\"><a href=\"#c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d\" id=\"c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d-link\">1<\/a><\/sup> text file called <code>tictactoe.txt.gz<\/code>, which will have an approximated size of 915MB (compressed!). Uncompressed, it yields a size of a little below 2GB. <\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Each line of the text file looks something like this:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">123456789 1104<\/pre>\n\n\n\n<p class=\"wp-block-paragraph\">whereas the first nine digits represent the list (here: <code>1,2,3,4,5,6,7,8,9<\/code>) of moves. The following block of four digits (separated with a space from the list) have the following meaning:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>The first &#8220;1&#8221; stands for &#8220;this is a valid board&#8221;. If the list was not a valid board, it would read &#8220;0&#8221; (and all subsequent digits would be irrelevant.<\/li>\n\n\n\n<li>The second &#8220;1&#8221; stands for &#8220;there is a winner&#8221;. If there was no winner (and the outcome of the game was a tie), this position would have a &#8220;0&#8221;.<\/li>\n\n\n\n<li>The third digits (&#8220;0&#8221;) represents the winner. In case &#8220;X&#8221; has won the game, &#8220;0&#8221; is provided. If &#8220;O&#8221; had won the game, &#8220;1&#8221; is provided.<\/li>\n\n\n\n<li>The last digit (&#8220;4&#8221;) specifies after which move (of both having done their part) the outcome of the game was clear; the value &#8220;4&#8221; here means that after the fourth move of the winner (here &#8220;X&#8221;), that is after having occupied position 7, the player has won.<br>If the board was a tie, we define this field to contain the digit &#8220;9&#8221; to indicate that even after the last position was filled.<\/li>\n<\/ol>\n\n\n\n<p class=\"wp-block-paragraph\">In total there are<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>9<sup>9<\/sup> lines in the file representing (=387,420,489) <sup data-fn=\"36b0a39d-4c62-44e3-83cb-0476907292b4\" class=\"fn\"><a href=\"#36b0a39d-4c62-44e3-83cb-0476907292b4\" id=\"36b0a39d-4c62-44e3-83cb-0476907292b4-link\">2<\/a><\/sup> assignments,<\/li>\n\n\n\n<li>out of these, 362,880 are valid boards (<code>=9!<\/code>)<sup data-fn=\"1f1fb2ce-1e43-4707-989f-f5d3b78000e2\" class=\"fn\"><a href=\"#1f1fb2ce-1e43-4707-989f-f5d3b78000e2\" id=\"1f1fb2ce-1e43-4707-989f-f5d3b78000e2-link\">3<\/a><\/sup>, that is roughly 0,1%,<\/li>\n\n\n\n<li>out of these, 127,872 are won by X <sup data-fn=\"f868bd5e-20db-47e1-8579-9714e2342d31\" class=\"fn\"><a href=\"#f868bd5e-20db-47e1-8579-9714e2342d31\" id=\"f868bd5e-20db-47e1-8579-9714e2342d31-link\">4<\/a><\/sup>. <\/li>\n\n\n\n<li>Another 34,560 are won by Y <sup data-fn=\"b7981349-f7c0-427c-a7bf-2827f549e63d\" class=\"fn\"><a href=\"#b7981349-f7c0-427c-a7bf-2827f549e63d\" id=\"b7981349-f7c0-427c-a7bf-2827f549e63d-link\">5<\/a><\/sup>.<\/li>\n\n\n\n<li>Therefore, there are 162,432 boards, which either party has won.<\/li>\n\n\n\n<li>There are 200,448 games ending in a tie <sup data-fn=\"7e1f093d-8e10-468c-89bc-ebac130fc974\" class=\"fn\"><a href=\"#7e1f093d-8e10-468c-89bc-ebac130fc974\" id=\"7e1f093d-8e10-468c-89bc-ebac130fc974-link\">6<\/a><\/sup>.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">Note that we do not have any duplicate games in the dataset.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">To simplify (and speed up processing), the jupyter notebook also generates a second file called <code>tictactoe_valid.txt<\/code> (without gzip compression), which only contains the valid boards. This file has a size of roughly 5.4MB.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">Equipped with these preparations, we can tackle our neural networks now.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Footnotes<\/h2>\n\n\n<ol class=\"wp-block-footnotes\"><li id=\"c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d\">The text is very repetitive. GZIP, even with &#8220;highest compression&#8221; mode has still some troubles to remove all redundancies. Therefore, other compression algorithms might be suited better. However, for the sake of brevity, this drawback is accepted here. <a href=\"#c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d-link\" aria-label=\"Jump to footnote reference 1\">\u21a9\ufe0e<\/a><\/li><li id=\"36b0a39d-4c62-44e3-83cb-0476907292b4\">You may verify this by running <code>zcat tictactoe.txt.gz | wc -l<\/code> <a href=\"#36b0a39d-4c62-44e3-83cb-0476907292b4-link\" aria-label=\"Jump to footnote reference 2\">\u21a9\ufe0e<\/a><\/li><li id=\"1f1fb2ce-1e43-4707-989f-f5d3b78000e2\">You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 1' | wc -l<\/code> <a href=\"#1f1fb2ce-1e43-4707-989f-f5d3b78000e2-link\" aria-label=\"Jump to footnote reference 3\">\u21a9\ufe0e<\/a><\/li><li id=\"f868bd5e-20db-47e1-8579-9714e2342d31\">You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 110' | wc -l<\/code> <a href=\"#f868bd5e-20db-47e1-8579-9714e2342d31-link\" aria-label=\"Jump to footnote reference 4\">\u21a9\ufe0e<\/a><\/li><li id=\"b7981349-f7c0-427c-a7bf-2827f549e63d\">You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 111' | wc -l<\/code> <a href=\"#b7981349-f7c0-427c-a7bf-2827f549e63d-link\" aria-label=\"Jump to footnote reference 5\">\u21a9\ufe0e<\/a><\/li><li id=\"7e1f093d-8e10-468c-89bc-ebac130fc974\">You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 10' | wc -l<\/code> <a href=\"#7e1f093d-8e10-468c-89bc-ebac130fc974-link\" aria-label=\"Jump to footnote reference 6\">\u21a9\ufe0e<\/a><\/li><\/ol>","protected":false},"excerpt":{"rendered":"<p>You might still remember the times when you played Tic-Tac-Toe (a.k.a. noughts and crosses) in your childhood: In a series of blog posts I want to apply neural networks on this well-known game. But before we may do that, we need to do some preparations. Eventually, we want to teach a neural network to determine: &#8230;<\/p>\n<p><a href=\"http:\/\/blog.schmoigl-online.de\/?p=1475\" class=\"more-link\">Continue reading &lsquo;Preparations: Tic-Tac-Toe and AI (Part 1)&rsquo; &raquo;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"[{\"content\":\"The text is very repetitive. GZIP, even with \\\"highest compression\\\" mode has still some troubles to remove all redundancies. Therefore, other compression algorithms might be suited better. However, for the sake of brevity, this drawback is accepted here.\",\"id\":\"c5cfcc7b-9360-47cf-8d69-5b0d6ea7394d\"},{\"content\":\"You may verify this by running <code>zcat tictactoe.txt.gz | wc -l<\/code>\",\"id\":\"36b0a39d-4c62-44e3-83cb-0476907292b4\"},{\"content\":\"You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 1' | wc -l<\/code>\",\"id\":\"1f1fb2ce-1e43-4707-989f-f5d3b78000e2\"},{\"content\":\"You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 110' | wc -l<\/code>\",\"id\":\"f868bd5e-20db-47e1-8579-9714e2342d31\"},{\"content\":\"You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 111' | wc -l<\/code>\",\"id\":\"b7981349-f7c0-427c-a7bf-2827f549e63d\"},{\"content\":\"You may verify this by running <code>zcat tictactoe.txt.gz | egrep ' 10' | wc -l<\/code>\",\"id\":\"7e1f093d-8e10-468c-89bc-ebac130fc974\"}]"},"categories":[38],"tags":[48,50],"class_list":["post-1475","post","type-post","status-publish","format-standard","hentry","category-machine-learning","tag-tensorflow","tag-tic-tac-toe"],"_links":{"self":[{"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/posts\/1475","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1475"}],"version-history":[{"count":18,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/posts\/1475\/revisions"}],"predecessor-version":[{"id":1580,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=\/wp\/v2\/posts\/1475\/revisions\/1580"}],"wp:attachment":[{"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1475"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1475"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.schmoigl-online.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}