$N~``d2Fz{Ǐ `4#G K&RBǓ\Ɠ=$jw[-)9F_S& --)*ɓ$ͪլVl?/Uc#r 4<'OƤ^Vez`;zjȆ}@PrߵkyXݿFٵk^NaJ6n頩IP[ E8 ?3كq'Mq?Ӄ;vcsY<`PTVtHg7IZځ%?L ObH]w)Ofr,=]f0 (/LqItAgᆹ.<#CL py1jE}R@TA&c-dI|z}SX~Sh4玏&آHwaUfqt+W28mB(r{X~_e'%J'B~{~_Uy~ĉ !_Zh&{~qO$f\VKŋb,e|ű_!6GxN|I]?9mTCCʼ<2!eJQ$"DE,Ú5H@˲b'5s=Xh=Dl8gdDWl 7`SM"7W|2| cEQ!hjQdgiz@!r믷Ԑdiip7TSc1.t1ӟ"1j gP(ZPpUW}SHWTTTWWwvvq/WFU[ߜIp%%?0n`N74q%Kd"$w8[@ Vk?5zp2CU㸫yJ߰ī$i#tqllܘa \ ˀOױP_~*ڵ6AWg/bF+-?:|JZ,qZ`Q<ƸK3~ZL7Xvp8祗V3vd1O` kצ]{elBhC(<0 >RExllVWV"Zv/C\4rcǎBzªTz-Bq?<H@>01vwZ-/qկ@"丢?/)NE۷WQRmyĚ57F}+c܍d55W D]. 9tS9څ'?<jp-ݲhQ\!J]La^ x~syab"}'7l8R(réAo _`( BI bEH9%KOǒ9FEvhvǂon,I'8uW h[-xp=я/L$dg`ggӜ9h4X2$-'I :E!rϋ>+M$uZ-;#]'N4ϟ?EqfAq]8<::kWFQ(3ܟ|I۔ۧMͦMt:72$͌F#nKA ŤU1*cxy8B!. nw$ԡO3z}0b8Ƥ()U 5bIĜVE4EWIK)~3nU>RgvRXSuIݎDO|~l9ܟ~iKLLLdddH%,X}lla<ٳBXd%6_)eF^}Ut)lYb AFEaen%LT?1y2_Poo$'T*!ԊSz]~dDptz}t7L@#trÆD3I7R!f$2z}$C KMSJ i~ѣ~[occeG>XH%3gZ-75 5alP.Y%[ڳgϖ-[}ё{[nٹsx]]<YR[,^{M:HΎUJNKJ<{Zk_z KeDeK\h""_$CQXUV %j15!jv'˶ 1 V(cwVDysuq8 կcH]ρuz|s]wI/eRyGt5#tX <牗!J1ӟIr3ϐDSee]Ā_LUBҵ(#{ BZNP.n,\H7xĉ{k0::j4ov~ ]]]ShIEIbEen=V!FF%RkHL<m*Adjxahj(5YT*QFf4Z6m4w?}ajxx77Ǚ EO&J"Ӭ0՛LuZmN% uB!*q 7!#0՛uZmcYY]wU(W1N ܔ{III0\`A^xA.lÑB̙3[nG70*U$_|ǎH6:%jȿ7jo]X !ݒ%I+fc O7N gUyƄqZs_}8Ȍx~H}L67amWj !^( 5[%pM:u#x |~#Ng jAJLs/_/;FlDq:deM|KB- -#"`?fa~DO3ػtK2P-}R]VM`uti]:6n$ۏ1R*U$+"Uh8L{mB8~w᪪Ϛ5kI*cχ:bS[OB~*\ļNrubQ;áӧH.ڈ\b77_]]y3&w#:%'u_}}ڹ|Fz";؛ *$AqGqNN~1z܍۶Qo%H=}F/T 3xBtsza7q0s%b87'&ΏFc[*wʥt333=F/~DP(4F (>x5 -C_J2˖!1T$ DbKkYH4EW%v:D HN#!QYA)+B &&<_@$q\Bk:Ruy䎁Tp +V].b$bEڕyy?61))*/r<+ᎎA+(q\\Jb`$2V<џMK+mjdՑ艉emm?n(hZ]U48%8@ju#Lg,=Li fI"Mi %˧ql3E q2Kn?eVkZG\LK;W]] 8A222v$ibY`]g10k4j"Mt"Rjg@ii(0ekH"ol"\H&cu`(صK-?ghsmW'\V[LrzqEIZO/Ir++c%1MVRxpn̙ĖHzݒ%?a|!$k@EO,3nb"1r<#"!rp[NNNooxW__{}}}Dw͛фGSU9h噿eR檪@g'R+N:7m8 ~~Qvv)g,Ai Bj-ܽ{7z%ޓQwp¦ՑLdgd 1.eâQa,80b)K}O=5s+$)pL>s^{2m+WO vw#dV2'P~ R̜20Wўz}X,H[֊ݻw^رc@!t:kkkKKKjd.XQTQ3cƌo9yR,++ŗFzn04{;4rq!3SKQdJOO1>ujj%%%vƥKNLLrԓX4bѣU'w#Db";3Bѹ=e`qVLIX@||RiR\RHNTxQc~OvDzIb|ht1)'+Kyⳍ4Y:1a ˥T* B854=وtرٳgϚ5h'N~~(sh1^DUrr>dS.q~?rزqXNʲ1Ln3gǃ BHVXVvT(ʌAc6YVZj[`0fdd t:]SS{WW B!$1m6[}ZmPd2BP6gNe^^ΌY۷?EB$)@ZZZ &)?֭nBItx endstream endobj 15 0 obj << /Type /Annot /Subtype /Link /A 16 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 716.1516 507.3660 736.9416 ] >> endobj 16 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 17 0 obj << /Type /Annot /Subtype /Link /A 18 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 691.2036 195.2430 711.9936 ] >> endobj 18 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 19 0 obj << /Type /Annot /Subtype /Link /A 20 0 R /Border [0 0 0] /H /I /Rect [ 102.4673 652.1721 152.8358 661.8246 ] >> endobj 20 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article_category/maths/) >> endobj 21 0 obj << /Type /Annot /Subtype /Link /A 22 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 640.3073 118.3485 650.2279 ] >> endobj 22 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/cormaclarkin/) >> endobj 23 0 obj << /Type /Annot /Subtype /Link /A 24 0 R /Border [0 0 0] /H /I /Rect [ 128.5882 640.3073 196.8674 650.2279 ] >> endobj 24 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/bernardstromaingmail-com/) >> endobj 25 0 obj << /Type /Annot /Subtype /Link /A 26 0 R /Border [0 0 0] /H /I /Rect [ 202.2884 640.3073 274.3507 650.2279 ] >> endobj 26 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/conmck/) >> endobj 27 0 obj << /Type /Annot /Subtype /Link /A 28 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 716.1516 507.3660 736.9416 ] >> endobj 28 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 29 0 obj << /Type /Annot /Subtype /Link /A 30 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 691.2036 195.2430 711.9936 ] >> endobj 30 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 31 0 obj << /Type /Annot /Subtype /Link /A 32 0 R /Border [0 0 0] /H /I /Rect [ 102.4673 652.1721 152.8358 661.8246 ] >> endobj 32 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article_category/maths/) >> endobj 33 0 obj << /Type /Annot /Subtype /Link /A 34 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 640.3073 118.3485 650.2279 ] >> endobj 34 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/cormaclarkin/) >> endobj 35 0 obj << /Type /Annot /Subtype /Link /A 36 0 R /Border [0 0 0] /H /I /Rect [ 128.5882 640.3073 196.8674 650.2279 ] >> endobj 36 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/bernardstromaingmail-com/) >> endobj 37 0 obj << /Type /Annot /Subtype /Link /A 38 0 R /Border [0 0 0] /H /I /Rect [ 202.2884 640.3073 274.3507 650.2279 ] >> endobj 38 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/conmck/) >> endobj 39 0 obj << /Type /Annot /Subtype /Link /A 40 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 716.1516 507.3660 736.9416 ] >> endobj 40 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 41 0 obj << /Type /Annot /Subtype /Link /A 42 0 R /Border [0 0 0] /H /I /Rect [ 15.0000 691.2036 195.2430 711.9936 ] >> endobj 42 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article/an-investigation-of-ericksons-square-game-using-the-minimax-algorithm/) >> endobj 43 0 obj << /Type /Annot /Subtype /Link /A 44 0 R /Border [0 0 0] /H /I /Rect [ 102.4673 652.1721 152.8358 661.8246 ] >> endobj 44 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/article_category/maths/) >> endobj 45 0 obj << /Type /Annot /Subtype /Link /A 46 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 640.3073 118.3485 650.2279 ] >> endobj 46 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/cormaclarkin/) >> endobj 47 0 obj << /Type /Annot /Subtype /Link /A 48 0 R /Border [0 0 0] /H /I /Rect [ 128.5882 640.3073 196.8674 650.2279 ] >> endobj 48 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/bernardstromaingmail-com/) >> endobj 49 0 obj << /Type /Annot /Subtype /Link /A 50 0 R /Border [0 0 0] /H /I /Rect [ 202.2884 640.3073 274.3507 650.2279 ] >> endobj 50 0 obj << /Type /Action /S /URI /URI (http://archive.ysjournal.com/author/conmck/) >> endobj 51 0 obj << /Type /Page /Parent 3 0 R /Annots [ 53 0 R 55 0 R 57 0 R 59 0 R 61 0 R 63 0 R ] /Contents 52 0 R >> endobj 52 0 obj << /Length 19613 >> stream 0.271 0.267 0.267 rg q 15.000 37.825 577.500 739.175 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Prior to our investigation we checked to see if any previous work had been done on this topic and found two particularly relevant )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(papers on the arXiv tool.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(First Paper)] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(The first paper, titled Guaranteed successful strategies for a square achievement game on an n x n grid )] TJ ET 0.267 0.267 0.267 rg BT 481.458 718.269 Td /F4 8.7 Tf [(1)] TJ ET 0.271 0.267 0.267 rg BT 486.277 716.762 Td /F1 9.8 Tf [( was written by )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(Thomas Jenrich of Trier University in Germany. It deals with the formulation of the problem into a workable code and talks about )] TJ ET BT 26.250 692.952 Td /F1 9.8 Tf [(guaranteed strategies for a small n.)] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(One notable thing that we had identified before reading this paper is that only of all possibilities need to be computed as all )] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(other situations are a multiple of a 90 rotation of a previously computed permutation. That idea is discussed here and we )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(decided to try to incorporate this into our work in order to optimise our computation so as to achieve results in the most efficient )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(and timely manner.)] TJ ET BT 26.250 618.429 Td /F1 9.8 Tf [(Another thing that we gleaned from this paper is that, if played optimally, when n=3, where n is the number determining the size )] TJ ET BT 26.250 606.524 Td /F1 9.8 Tf [(in units of the play area square, the game will be a draw. This gave us a reference point so that we could check if our program )] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(played optimally by comparing our generated results to this certain outcome.)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(The same goes for n=4, where Jenrich established that Player 1 will always win. This is also true for n=5. These valuable )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(benchmarks aided us greatly when the time came to run our program. These were vital when we moved to n=>5 as we would )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(have no way of knowing if our gameplay was necessarily optimal as nothing had been proven before.)] TJ ET BT 26.250 532.000 Td /F1 9.8 Tf [(The second part of Jenrichs paper gave us the suggestion that coordinate Euclidean geometry would be a good way to )] TJ ET BT 26.250 520.095 Td /F1 9.8 Tf [(represent our problem in code, since these coordinates can be easily converted to numerical values later on. This made )] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(computing the outcomes easier later on and also gives us an input method we are already quite familiar with from the school )] TJ ET BT 26.250 496.286 Td /F1 9.8 Tf [(Mathematics curriculum.)] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(We also found a formula which we managed to tweak to improve it. Jenrichs paper has a formula for showing complete )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(squares. However, we are interested in the playing process and therefore needed a formula for partially completed squares. We )] TJ ET BT 26.250 453.072 Td /F1 9.8 Tf [(adapted Jenrichs formula to get a formula that would give us a partially completed square.)] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(Second Paper)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Moving on from Jenrichs paper, which was of great use to us in establishing a foundation for our investigation, we now looked )] TJ ET BT 26.250 402.357 Td /F1 9.8 Tf [(at another arXiv paper, titled Extremal binary matrices without constant 2-squares, )] TJ ET 0.267 0.267 0.267 rg BT 389.847 403.865 Td /F4 8.7 Tf [(2)] TJ ET 0.271 0.267 0.267 rg BT 394.666 402.357 Td /F1 9.8 Tf [( which was written by Roland Bacher and )] TJ ET BT 26.250 390.453 Td /F1 9.8 Tf [(Shalom Eliahou, of Universit Joseph Fourier Grenoble and Universit Cte dOpale Littoral respectively.)] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(This paper proved that for n=15 the end result prevents a draw result and that therefore no matter what moves are made by )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(either player that a win results for one of the two players. This told us that in some cases we test, we may only have one type of )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(outcome \(win for either player or draw\) regardless of moves made, demonstrable by computational means irrespective of )] TJ ET BT 26.250 335.334 Td /F1 9.8 Tf [(optimal play or not.)] TJ ET BT 26.250 298.731 Td /F4 12.0 Tf [(Method)] TJ ET BT 26.250 278.777 Td /F1 9.8 Tf [(We began to look at how we would tackle the problem. Firstly, we decided to try to generate a Tic-Tac-Toe game based on the )] TJ ET BT 26.250 266.872 Td /F1 9.8 Tf [(Minimax algorithm and base the rest of our work on that. Then we would try to adapt that program to play the Square Game.)] TJ ET BT 26.250 247.467 Td /F1 9.8 Tf [(Minimax Algorithm Basics)] TJ ET BT 26.250 228.063 Td /F1 9.8 Tf [(The Minimax algorithm attempts to \(min\)imise a loss in a \(max\)imum loss scenario. The following is an explanation of the )] TJ ET BT 26.250 216.158 Td /F1 9.8 Tf [(Minimax algorithm:)] TJ ET BT 26.250 196.753 Td /F1 9.8 Tf [(the Minimax algorithm is a decision rule used in decision and game theory for minimizing the possible loss for a worst case )] TJ ET BT 26.250 184.848 Td /F1 9.8 Tf [(\(maximum loss\) scenario. It was originally created for two player games such as ours, covering both the cases where players )] TJ ET BT 26.250 172.944 Td /F1 9.8 Tf [(take alternate moves and those where they make simultaneous moves.)] TJ ET BT 26.250 153.539 Td /F1 9.8 Tf [(Minimax Algorithm Value)] TJ ET BT 26.250 134.134 Td /F1 9.8 Tf [(The Minimax algorithm value is the value used to make the decisions. This is a numerical representation of how likely a given )] TJ ET BT 26.250 122.229 Td /F1 9.8 Tf [(string of moves will result in a maximum loss for a given player. Depending on the player, the lower or higher the value, the )] TJ ET BT 26.250 110.325 Td /F1 9.8 Tf [(better that string of moves is to play.)] TJ ET BT 26.250 90.920 Td /F1 9.8 Tf [(In our case there are only three states; a win for P1, a win for P2 or a draw. This means our Minimax values are 1, -1 or 0.)] TJ ET Q q 15.000 37.825 577.500 739.175 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Prior to our investigation we checked to see if any previous work had been done on this topic and found two particularly relevant )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(papers on the arXiv tool.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(First Paper)] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(The first paper, titled Guaranteed successful strategies for a square achievement game on an n x n grid )] TJ ET 0.267 0.267 0.267 rg BT 481.458 718.269 Td /F4 8.7 Tf [(1)] TJ ET 0.271 0.267 0.267 rg BT 486.277 716.762 Td /F1 9.8 Tf [( was written by )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(Thomas Jenrich of Trier University in Germany. It deals with the formulation of the problem into a workable code and talks about )] TJ ET BT 26.250 692.952 Td /F1 9.8 Tf [(guaranteed strategies for a small n.)] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(One notable thing that we had identified before reading this paper is that only of all possibilities need to be computed as all )] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(other situations are a multiple of a 90 rotation of a previously computed permutation. That idea is discussed here and we )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(decided to try to incorporate this into our work in order to optimise our computation so as to achieve results in the most efficient )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(and timely manner.)] TJ ET BT 26.250 618.429 Td /F1 9.8 Tf [(Another thing that we gleaned from this paper is that, if played optimally, when n=3, where n is the number determining the size )] TJ ET BT 26.250 606.524 Td /F1 9.8 Tf [(in units of the play area square, the game will be a draw. This gave us a reference point so that we could check if our program )] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(played optimally by comparing our generated results to this certain outcome.)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(The same goes for n=4, where Jenrich established that Player 1 will always win. This is also true for n=5. These valuable )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(benchmarks aided us greatly when the time came to run our program. These were vital when we moved to n=>5 as we would )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(have no way of knowing if our gameplay was necessarily optimal as nothing had been proven before.)] TJ ET BT 26.250 532.000 Td /F1 9.8 Tf [(The second part of Jenrichs paper gave us the suggestion that coordinate Euclidean geometry would be a good way to )] TJ ET BT 26.250 520.095 Td /F1 9.8 Tf [(represent our problem in code, since these coordinates can be easily converted to numerical values later on. This made )] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(computing the outcomes easier later on and also gives us an input method we are already quite familiar with from the school )] TJ ET BT 26.250 496.286 Td /F1 9.8 Tf [(Mathematics curriculum.)] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(We also found a formula which we managed to tweak to improve it. Jenrichs paper has a formula for showing complete )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(squares. However, we are interested in the playing process and therefore needed a formula for partially completed squares. We )] TJ ET BT 26.250 453.072 Td /F1 9.8 Tf [(adapted Jenrichs formula to get a formula that would give us a partially completed square.)] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(Second Paper)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Moving on from Jenrichs paper, which was of great use to us in establishing a foundation for our investigation, we now looked )] TJ ET BT 26.250 402.357 Td /F1 9.8 Tf [(at another arXiv paper, titled Extremal binary matrices without constant 2-squares, )] TJ ET 0.267 0.267 0.267 rg BT 389.847 403.865 Td /F4 8.7 Tf [(2)] TJ ET 0.271 0.267 0.267 rg BT 394.666 402.357 Td /F1 9.8 Tf [( which was written by Roland Bacher and )] TJ ET BT 26.250 390.453 Td /F1 9.8 Tf [(Shalom Eliahou, of Universit Joseph Fourier Grenoble and Universit Cte dOpale Littoral respectively.)] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(This paper proved that for n=15 the end result prevents a draw result and that therefore no matter what moves are made by )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(either player that a win results for one of the two players. This told us that in some cases we test, we may only have one type of )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(outcome \(win for either player or draw\) regardless of moves made, demonstrable by computational means irrespective of )] TJ ET BT 26.250 335.334 Td /F1 9.8 Tf [(optimal play or not.)] TJ ET BT 26.250 298.731 Td /F4 12.0 Tf [(Method)] TJ ET BT 26.250 278.777 Td /F1 9.8 Tf [(We began to look at how we would tackle the problem. Firstly, we decided to try to generate a Tic-Tac-Toe game based on the )] TJ ET BT 26.250 266.872 Td /F1 9.8 Tf [(Minimax algorithm and base the rest of our work on that. Then we would try to adapt that program to play the Square Game.)] TJ ET BT 26.250 247.467 Td /F1 9.8 Tf [(Minimax Algorithm Basics)] TJ ET BT 26.250 228.063 Td /F1 9.8 Tf [(The Minimax algorithm attempts to \(min\)imise a loss in a \(max\)imum loss scenario. The following is an explanation of the )] TJ ET BT 26.250 216.158 Td /F1 9.8 Tf [(Minimax algorithm:)] TJ ET BT 26.250 196.753 Td /F1 9.8 Tf [(the Minimax algorithm is a decision rule used in decision and game theory for minimizing the possible loss for a worst case )] TJ ET BT 26.250 184.848 Td /F1 9.8 Tf [(\(maximum loss\) scenario. It was originally created for two player games such as ours, covering both the cases where players )] TJ ET BT 26.250 172.944 Td /F1 9.8 Tf [(take alternate moves and those where they make simultaneous moves.)] TJ ET BT 26.250 153.539 Td /F1 9.8 Tf [(Minimax Algorithm Value)] TJ ET BT 26.250 134.134 Td /F1 9.8 Tf [(The Minimax algorithm value is the value used to make the decisions. This is a numerical representation of how likely a given )] TJ ET BT 26.250 122.229 Td /F1 9.8 Tf [(string of moves will result in a maximum loss for a given player. Depending on the player, the lower or higher the value, the )] TJ ET BT 26.250 110.325 Td /F1 9.8 Tf [(better that string of moves is to play.)] TJ ET BT 26.250 90.920 Td /F1 9.8 Tf [(In our case there are only three states; a win for P1, a win for P2 or a draw. This means our Minimax values are 1, -1 or 0.)] TJ ET Q q 15.000 37.825 577.500 739.175 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Prior to our investigation we checked to see if any previous work had been done on this topic and found two particularly relevant )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(papers on the arXiv tool.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(First Paper)] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(The first paper, titled Guaranteed successful strategies for a square achievement game on an n x n grid )] TJ ET 0.267 0.267 0.267 rg BT 481.458 718.269 Td /F4 8.7 Tf [(1)] TJ ET 0.271 0.267 0.267 rg BT 486.277 716.762 Td /F1 9.8 Tf [( was written by )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(Thomas Jenrich of Trier University in Germany. It deals with the formulation of the problem into a workable code and talks about )] TJ ET BT 26.250 692.952 Td /F1 9.8 Tf [(guaranteed strategies for a small n.)] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(One notable thing that we had identified before reading this paper is that only of all possibilities need to be computed as all )] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(other situations are a multiple of a 90 rotation of a previously computed permutation. That idea is discussed here and we )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(decided to try to incorporate this into our work in order to optimise our computation so as to achieve results in the most efficient )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(and timely manner.)] TJ ET BT 26.250 618.429 Td /F1 9.8 Tf [(Another thing that we gleaned from this paper is that, if played optimally, when n=3, where n is the number determining the size )] TJ ET BT 26.250 606.524 Td /F1 9.8 Tf [(in units of the play area square, the game will be a draw. This gave us a reference point so that we could check if our program )] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(played optimally by comparing our generated results to this certain outcome.)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(The same goes for n=4, where Jenrich established that Player 1 will always win. This is also true for n=5. These valuable )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(benchmarks aided us greatly when the time came to run our program. These were vital when we moved to n=>5 as we would )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(have no way of knowing if our gameplay was necessarily optimal as nothing had been proven before.)] TJ ET BT 26.250 532.000 Td /F1 9.8 Tf [(The second part of Jenrichs paper gave us the suggestion that coordinate Euclidean geometry would be a good way to )] TJ ET BT 26.250 520.095 Td /F1 9.8 Tf [(represent our problem in code, since these coordinates can be easily converted to numerical values later on. This made )] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(computing the outcomes easier later on and also gives us an input method we are already quite familiar with from the school )] TJ ET BT 26.250 496.286 Td /F1 9.8 Tf [(Mathematics curriculum.)] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(We also found a formula which we managed to tweak to improve it. Jenrichs paper has a formula for showing complete )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(squares. However, we are interested in the playing process and therefore needed a formula for partially completed squares. We )] TJ ET BT 26.250 453.072 Td /F1 9.8 Tf [(adapted Jenrichs formula to get a formula that would give us a partially completed square.)] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(Second Paper)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Moving on from Jenrichs paper, which was of great use to us in establishing a foundation for our investigation, we now looked )] TJ ET BT 26.250 402.357 Td /F1 9.8 Tf [(at another arXiv paper, titled Extremal binary matrices without constant 2-squares, )] TJ ET 0.267 0.267 0.267 rg BT 389.847 403.865 Td /F4 8.7 Tf [(2)] TJ ET 0.271 0.267 0.267 rg BT 394.666 402.357 Td /F1 9.8 Tf [( which was written by Roland Bacher and )] TJ ET BT 26.250 390.453 Td /F1 9.8 Tf [(Shalom Eliahou, of Universit Joseph Fourier Grenoble and Universit Cte dOpale Littoral respectively.)] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(This paper proved that for n=15 the end result prevents a draw result and that therefore no matter what moves are made by )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(either player that a win results for one of the two players. This told us that in some cases we test, we may only have one type of )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(outcome \(win for either player or draw\) regardless of moves made, demonstrable by computational means irrespective of )] TJ ET BT 26.250 335.334 Td /F1 9.8 Tf [(optimal play or not.)] TJ ET BT 26.250 298.731 Td /F4 12.0 Tf [(Method)] TJ ET BT 26.250 278.777 Td /F1 9.8 Tf [(We began to look at how we would tackle the problem. Firstly, we decided to try to generate a Tic-Tac-Toe game based on the )] TJ ET BT 26.250 266.872 Td /F1 9.8 Tf [(Minimax algorithm and base the rest of our work on that. Then we would try to adapt that program to play the Square Game.)] TJ ET BT 26.250 247.467 Td /F1 9.8 Tf [(Minimax Algorithm Basics)] TJ ET BT 26.250 228.063 Td /F1 9.8 Tf [(The Minimax algorithm attempts to \(min\)imise a loss in a \(max\)imum loss scenario. The following is an explanation of the )] TJ ET BT 26.250 216.158 Td /F1 9.8 Tf [(Minimax algorithm:)] TJ ET BT 26.250 196.753 Td /F1 9.8 Tf [(the Minimax algorithm is a decision rule used in decision and game theory for minimizing the possible loss for a worst case )] TJ ET BT 26.250 184.848 Td /F1 9.8 Tf [(\(maximum loss\) scenario. It was originally created for two player games such as ours, covering both the cases where players )] TJ ET BT 26.250 172.944 Td /F1 9.8 Tf [(take alternate moves and those where they make simultaneous moves.)] TJ ET BT 26.250 153.539 Td /F1 9.8 Tf [(Minimax Algorithm Value)] TJ ET BT 26.250 134.134 Td /F1 9.8 Tf [(The Minimax algorithm value is the value used to make the decisions. This is a numerical representation of how likely a given )] TJ ET BT 26.250 122.229 Td /F1 9.8 Tf [(string of moves will result in a maximum loss for a given player. Depending on the player, the lower or higher the value, the )] TJ ET BT 26.250 110.325 Td /F1 9.8 Tf [(better that string of moves is to play.)] TJ ET BT 26.250 90.920 Td /F1 9.8 Tf [(In our case there are only three states; a win for P1, a win for P2 or a draw. This means our Minimax values are 1, -1 or 0.)] TJ ET Q q 0.000 0.000 0.000 rg BT 291.710 19.825 Td /F1 11.0 Tf [(2)] TJ ET BT 25.000 19.825 Td /F1 11.0 Tf [(Young Scientists Journal)] TJ ET Q endstream endobj 53 0 obj << /Type /Annot /Subtype /Link /A 54 0 R /Border [0 0 0] /H /I /Rect [ 481.4580 717.4674 486.2767 726.2858 ] >> endobj 54 0 obj << /Type /Action >> endobj 55 0 obj << /Type /Annot /Subtype /Link /A 56 0 R /Border [0 0 0] /H /I /Rect [ 389.8470 403.0629 394.6657 411.8812 ] >> endobj 56 0 obj << /Type /Action >> endobj 57 0 obj << /Type /Annot /Subtype /Link /A 58 0 R /Border [0 0 0] /H /I /Rect [ 481.4580 717.4674 486.2767 726.2858 ] >> endobj 58 0 obj << /Type /Action >> endobj 59 0 obj << /Type /Annot /Subtype /Link /A 60 0 R /Border [0 0 0] /H /I /Rect [ 389.8470 403.0629 394.6657 411.8812 ] >> endobj 60 0 obj << /Type /Action >> endobj 61 0 obj << /Type /Annot /Subtype /Link /A 62 0 R /Border [0 0 0] /H /I /Rect [ 481.4580 717.4674 486.2767 726.2858 ] >> endobj 62 0 obj << /Type /Action >> endobj 63 0 obj << /Type /Annot /Subtype /Link /A 64 0 R /Border [0 0 0] /H /I /Rect [ 389.8470 403.0629 394.6657 411.8812 ] >> endobj 64 0 obj << /Type /Action >> endobj 65 0 obj << /Type /Page /Parent 3 0 R /Contents 66 0 R >> endobj 66 0 obj << /Length 19016 >> stream 0.271 0.267 0.267 rg q 15.000 25.572 577.500 751.428 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(It is important to note that these values will change after every move due to an opponents moves. That is why the computation )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(of the Minimax algorithm values need to be performed for every move for both players. The Minimax algorithm we use here will )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(generate the best move at any given point in a game for both players, assuming that search depth isnt a barrier.)] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(Each possible move has a Minimax algorithm value calculated for it by the program, accounting for every string of moves up to )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(the specified search depth and the move with the lowest value is selected and played. In our program, we programmed it so that )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(if two or more moves have the same value, then one move is selected at random.)] TJ ET BT 26.250 681.048 Td /F1 9.8 Tf [(Alpha-Beta Pruning)] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(Calculating every possible string of moves exhaustively is one way to find an optimal play solution, but is very inefficient.vThe )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(Alpha-Beta pruning process stops a string of moves from being calculated to conclusion if the move string stops being optimal. )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a )] TJ ET BT 26.250 625.929 Td /F1 9.8 Tf [(previously examined move. The end result is completely identical to the unaltered Minimax algorithm, but it allows for more )] TJ ET BT 26.250 614.024 Td /F1 9.8 Tf [(efficient computation of the optimal move for a given player at a given point in the game.)] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(Heuristics)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(Due to a limited search depth, the program finds it difficult to make opening moves. However, we found that the middle squares )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(are the best places to start. To incorporate this finding into the program, we integrated a heuristic to prioritise middle squares if it )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(cannot find a better solution. Due to the search depths, in practice the heuristic is always activated for the opening moves. A )] TJ ET BT 26.250 539.500 Td /F1 9.8 Tf [(heuristic is a shortcut taken to speed up a calculation. Since we know the program will pick the middle squares, we save time )] TJ ET BT 26.250 527.595 Td /F1 9.8 Tf [(using this process.)] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(Adapted Program)] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(Having the necessary fundamental understanding of the Minimax algorithm and the necessary software additions, we adapted a )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(pre-existing code from cwoebker.com that played Tic-Tac-Toe optimally using a version of the Minimax algorithm.)] TJ ET BT 26.250 457.476 Td /F1 9.8 Tf [(This code worked as follows:)] TJ ET BT 26.250 438.072 Td /F1 9.8 Tf [( The random library is imported)] TJ ET BT 26.250 418.667 Td /F1 9.8 Tf [( Board size n, # of squares nxn defined \(for Tic Tac Toe n set as 3\))] TJ ET BT 26.250 399.262 Td /F1 9.8 Tf [( Search depth \(how many moves in advance are examined\) is set to 9)] TJ ET BT 26.250 379.857 Td /F1 9.8 Tf [( Winning combinations \(every combination of winning moves\) defined in a list)] TJ ET BT 26.250 360.453 Td /F1 9.8 Tf [( Advantage combinations \(every pair of squares that can lead to a win in one move\))] TJ ET BT 26.250 341.048 Td /F1 9.8 Tf [( Win is defined as player occupying one of the winning combinations)] TJ ET BT 26.250 321.643 Td /F1 9.8 Tf [( Draw is defined as all squares occupied with neither player having one winning combination)] TJ ET BT 26.250 302.238 Td /F1 9.8 Tf [(The best move for the PC is worked out as follows:)] TJ ET BT 26.250 282.834 Td /F1 9.8 Tf [( The Minimax algorithm rates every move, seeking the move with the optimal value whilst considering that the other player will )] TJ ET BT 26.250 270.929 Td /F1 9.8 Tf [(try to minimise their loss)] TJ ET BT 26.250 251.524 Td /F1 9.8 Tf [( The Alpha-Beta pruning ensures that moves are not calculated if they result in a non-optimal scenario after part of the search, )] TJ ET BT 26.250 239.619 Td /F1 9.8 Tf [(thereby making the computation more efficient)] TJ ET BT 26.250 220.215 Td /F1 9.8 Tf [( The determine \(a specific part of code\) selects the optimal move based on the Minimax algorithm computation, ensuring the )] TJ ET BT 26.250 208.310 Td /F1 9.8 Tf [(space is not already occupied by either player.)] TJ ET BT 26.250 188.905 Td /F1 9.8 Tf [(We now had a working Minimax algorithm playing Tic Tac Toe optimally. We needed to find a way to get this program to play )] TJ ET BT 26.250 177.000 Td /F1 9.8 Tf [(the Square Game in as optimal a way as possible, which would require several changes. We began to identify and implement )] TJ ET BT 26.250 165.096 Td /F1 9.8 Tf [(these changes.)] TJ ET BT 26.250 145.691 Td /F1 9.8 Tf [(Square Game Program)] TJ ET BT 26.250 126.286 Td /F1 9.8 Tf [(The changes we made to the Tic-Tac-Toe program were as follows:)] TJ ET BT 26.250 106.881 Td /F1 9.8 Tf [( The winning combinations, which tell the program which moves equate to a win situation for any given player. Since the )] TJ ET BT 26.250 94.977 Td /F1 9.8 Tf [(winning combinations for Tic-Tac-Toe are different to Ericksons Square Game, these needed to be changed to suit both the )] TJ ET BT 26.250 83.072 Td /F1 9.8 Tf [(game and the different board sizes as different sizes will give different win possibilities. These would be the co-ordinate )] TJ ET BT 26.250 71.167 Td /F1 9.8 Tf [(positions of all winning squares.)] TJ ET BT 26.250 51.762 Td /F1 9.8 Tf [( The advantage combinations, which tell the program which moves are close to a win for any given player. Similar to the )] TJ ET BT 26.250 39.858 Td /F1 9.8 Tf [(winning combinations, these needed to be changed for each board size and game. We ended up not using these as the )] TJ ET Q q 15.000 25.572 577.500 751.428 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(It is important to note that these values will change after every move due to an opponents moves. That is why the computation )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(of the Minimax algorithm values need to be performed for every move for both players. The Minimax algorithm we use here will )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(generate the best move at any given point in a game for both players, assuming that search depth isnt a barrier.)] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(Each possible move has a Minimax algorithm value calculated for it by the program, accounting for every string of moves up to )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(the specified search depth and the move with the lowest value is selected and played. In our program, we programmed it so that )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(if two or more moves have the same value, then one move is selected at random.)] TJ ET BT 26.250 681.048 Td /F1 9.8 Tf [(Alpha-Beta Pruning)] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(Calculating every possible string of moves exhaustively is one way to find an optimal play solution, but is very inefficient.vThe )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(Alpha-Beta pruning process stops a string of moves from being calculated to conclusion if the move string stops being optimal. )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a )] TJ ET BT 26.250 625.929 Td /F1 9.8 Tf [(previously examined move. The end result is completely identical to the unaltered Minimax algorithm, but it allows for more )] TJ ET BT 26.250 614.024 Td /F1 9.8 Tf [(efficient computation of the optimal move for a given player at a given point in the game.)] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(Heuristics)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(Due to a limited search depth, the program finds it difficult to make opening moves. However, we found that the middle squares )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(are the best places to start. To incorporate this finding into the program, we integrated a heuristic to prioritise middle squares if it )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(cannot find a better solution. Due to the search depths, in practice the heuristic is always activated for the opening moves. A )] TJ ET BT 26.250 539.500 Td /F1 9.8 Tf [(heuristic is a shortcut taken to speed up a calculation. Since we know the program will pick the middle squares, we save time )] TJ ET BT 26.250 527.595 Td /F1 9.8 Tf [(using this process.)] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(Adapted Program)] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(Having the necessary fundamental understanding of the Minimax algorithm and the necessary software additions, we adapted a )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(pre-existing code from cwoebker.com that played Tic-Tac-Toe optimally using a version of the Minimax algorithm.)] TJ ET BT 26.250 457.476 Td /F1 9.8 Tf [(This code worked as follows:)] TJ ET BT 26.250 438.072 Td /F1 9.8 Tf [( The random library is imported)] TJ ET BT 26.250 418.667 Td /F1 9.8 Tf [( Board size n, # of squares nxn defined \(for Tic Tac Toe n set as 3\))] TJ ET BT 26.250 399.262 Td /F1 9.8 Tf [( Search depth \(how many moves in advance are examined\) is set to 9)] TJ ET BT 26.250 379.857 Td /F1 9.8 Tf [( Winning combinations \(every combination of winning moves\) defined in a list)] TJ ET BT 26.250 360.453 Td /F1 9.8 Tf [( Advantage combinations \(every pair of squares that can lead to a win in one move\))] TJ ET BT 26.250 341.048 Td /F1 9.8 Tf [( Win is defined as player occupying one of the winning combinations)] TJ ET BT 26.250 321.643 Td /F1 9.8 Tf [( Draw is defined as all squares occupied with neither player having one winning combination)] TJ ET BT 26.250 302.238 Td /F1 9.8 Tf [(The best move for the PC is worked out as follows:)] TJ ET BT 26.250 282.834 Td /F1 9.8 Tf [( The Minimax algorithm rates every move, seeking the move with the optimal value whilst considering that the other player will )] TJ ET BT 26.250 270.929 Td /F1 9.8 Tf [(try to minimise their loss)] TJ ET BT 26.250 251.524 Td /F1 9.8 Tf [( The Alpha-Beta pruning ensures that moves are not calculated if they result in a non-optimal scenario after part of the search, )] TJ ET BT 26.250 239.619 Td /F1 9.8 Tf [(thereby making the computation more efficient)] TJ ET BT 26.250 220.215 Td /F1 9.8 Tf [( The determine \(a specific part of code\) selects the optimal move based on the Minimax algorithm computation, ensuring the )] TJ ET BT 26.250 208.310 Td /F1 9.8 Tf [(space is not already occupied by either player.)] TJ ET BT 26.250 188.905 Td /F1 9.8 Tf [(We now had a working Minimax algorithm playing Tic Tac Toe optimally. We needed to find a way to get this program to play )] TJ ET BT 26.250 177.000 Td /F1 9.8 Tf [(the Square Game in as optimal a way as possible, which would require several changes. We began to identify and implement )] TJ ET BT 26.250 165.096 Td /F1 9.8 Tf [(these changes.)] TJ ET BT 26.250 145.691 Td /F1 9.8 Tf [(Square Game Program)] TJ ET BT 26.250 126.286 Td /F1 9.8 Tf [(The changes we made to the Tic-Tac-Toe program were as follows:)] TJ ET BT 26.250 106.881 Td /F1 9.8 Tf [( The winning combinations, which tell the program which moves equate to a win situation for any given player. Since the )] TJ ET BT 26.250 94.977 Td /F1 9.8 Tf [(winning combinations for Tic-Tac-Toe are different to Ericksons Square Game, these needed to be changed to suit both the )] TJ ET BT 26.250 83.072 Td /F1 9.8 Tf [(game and the different board sizes as different sizes will give different win possibilities. These would be the co-ordinate )] TJ ET BT 26.250 71.167 Td /F1 9.8 Tf [(positions of all winning squares.)] TJ ET BT 26.250 51.762 Td /F1 9.8 Tf [( The advantage combinations, which tell the program which moves are close to a win for any given player. Similar to the )] TJ ET BT 26.250 39.858 Td /F1 9.8 Tf [(winning combinations, these needed to be changed for each board size and game. We ended up not using these as the )] TJ ET Q q 15.000 25.572 577.500 751.428 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(It is important to note that these values will change after every move due to an opponents moves. That is why the computation )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(of the Minimax algorithm values need to be performed for every move for both players. The Minimax algorithm we use here will )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(generate the best move at any given point in a game for both players, assuming that search depth isnt a barrier.)] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(Each possible move has a Minimax algorithm value calculated for it by the program, accounting for every string of moves up to )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(the specified search depth and the move with the lowest value is selected and played. In our program, we programmed it so that )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(if two or more moves have the same value, then one move is selected at random.)] TJ ET BT 26.250 681.048 Td /F1 9.8 Tf [(Alpha-Beta Pruning)] TJ ET BT 26.250 661.643 Td /F1 9.8 Tf [(Calculating every possible string of moves exhaustively is one way to find an optimal play solution, but is very inefficient.vThe )] TJ ET BT 26.250 649.738 Td /F1 9.8 Tf [(Alpha-Beta pruning process stops a string of moves from being calculated to conclusion if the move string stops being optimal. )] TJ ET BT 26.250 637.833 Td /F1 9.8 Tf [(It stops completely evaluating a move when at least one possibility has been found that proves the move to be worse than a )] TJ ET BT 26.250 625.929 Td /F1 9.8 Tf [(previously examined move. The end result is completely identical to the unaltered Minimax algorithm, but it allows for more )] TJ ET BT 26.250 614.024 Td /F1 9.8 Tf [(efficient computation of the optimal move for a given player at a given point in the game.)] TJ ET BT 26.250 594.619 Td /F1 9.8 Tf [(Heuristics)] TJ ET BT 26.250 575.214 Td /F1 9.8 Tf [(Due to a limited search depth, the program finds it difficult to make opening moves. However, we found that the middle squares )] TJ ET BT 26.250 563.310 Td /F1 9.8 Tf [(are the best places to start. To incorporate this finding into the program, we integrated a heuristic to prioritise middle squares if it )] TJ ET BT 26.250 551.405 Td /F1 9.8 Tf [(cannot find a better solution. Due to the search depths, in practice the heuristic is always activated for the opening moves. A )] TJ ET BT 26.250 539.500 Td /F1 9.8 Tf [(heuristic is a shortcut taken to speed up a calculation. Since we know the program will pick the middle squares, we save time )] TJ ET BT 26.250 527.595 Td /F1 9.8 Tf [(using this process.)] TJ ET BT 26.250 508.191 Td /F1 9.8 Tf [(Adapted Program)] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(Having the necessary fundamental understanding of the Minimax algorithm and the necessary software additions, we adapted a )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(pre-existing code from cwoebker.com that played Tic-Tac-Toe optimally using a version of the Minimax algorithm.)] TJ ET BT 26.250 457.476 Td /F1 9.8 Tf [(This code worked as follows:)] TJ ET BT 26.250 438.072 Td /F1 9.8 Tf [( The random library is imported)] TJ ET BT 26.250 418.667 Td /F1 9.8 Tf [( Board size n, # of squares nxn defined \(for Tic Tac Toe n set as 3\))] TJ ET BT 26.250 399.262 Td /F1 9.8 Tf [( Search depth \(how many moves in advance are examined\) is set to 9)] TJ ET BT 26.250 379.857 Td /F1 9.8 Tf [( Winning combinations \(every combination of winning moves\) defined in a list)] TJ ET BT 26.250 360.453 Td /F1 9.8 Tf [( Advantage combinations \(every pair of squares that can lead to a win in one move\))] TJ ET BT 26.250 341.048 Td /F1 9.8 Tf [( Win is defined as player occupying one of the winning combinations)] TJ ET BT 26.250 321.643 Td /F1 9.8 Tf [( Draw is defined as all squares occupied with neither player having one winning combination)] TJ ET BT 26.250 302.238 Td /F1 9.8 Tf [(The best move for the PC is worked out as follows:)] TJ ET BT 26.250 282.834 Td /F1 9.8 Tf [( The Minimax algorithm rates every move, seeking the move with the optimal value whilst considering that the other player will )] TJ ET BT 26.250 270.929 Td /F1 9.8 Tf [(try to minimise their loss)] TJ ET BT 26.250 251.524 Td /F1 9.8 Tf [( The Alpha-Beta pruning ensures that moves are not calculated if they result in a non-optimal scenario after part of the search, )] TJ ET BT 26.250 239.619 Td /F1 9.8 Tf [(thereby making the computation more efficient)] TJ ET BT 26.250 220.215 Td /F1 9.8 Tf [( The determine \(a specific part of code\) selects the optimal move based on the Minimax algorithm computation, ensuring the )] TJ ET BT 26.250 208.310 Td /F1 9.8 Tf [(space is not already occupied by either player.)] TJ ET BT 26.250 188.905 Td /F1 9.8 Tf [(We now had a working Minimax algorithm playing Tic Tac Toe optimally. We needed to find a way to get this program to play )] TJ ET BT 26.250 177.000 Td /F1 9.8 Tf [(the Square Game in as optimal a way as possible, which would require several changes. We began to identify and implement )] TJ ET BT 26.250 165.096 Td /F1 9.8 Tf [(these changes.)] TJ ET BT 26.250 145.691 Td /F1 9.8 Tf [(Square Game Program)] TJ ET BT 26.250 126.286 Td /F1 9.8 Tf [(The changes we made to the Tic-Tac-Toe program were as follows:)] TJ ET BT 26.250 106.881 Td /F1 9.8 Tf [( The winning combinations, which tell the program which moves equate to a win situation for any given player. Since the )] TJ ET BT 26.250 94.977 Td /F1 9.8 Tf [(winning combinations for Tic-Tac-Toe are different to Ericksons Square Game, these needed to be changed to suit both the )] TJ ET BT 26.250 83.072 Td /F1 9.8 Tf [(game and the different board sizes as different sizes will give different win possibilities. These would be the co-ordinate )] TJ ET BT 26.250 71.167 Td /F1 9.8 Tf [(positions of all winning squares.)] TJ ET BT 26.250 51.762 Td /F1 9.8 Tf [( The advantage combinations, which tell the program which moves are close to a win for any given player. Similar to the )] TJ ET BT 26.250 39.858 Td /F1 9.8 Tf [(winning combinations, these needed to be changed for each board size and game. We ended up not using these as the )] TJ ET Q q 0.000 0.000 0.000 rg BT 291.710 19.825 Td /F1 11.0 Tf [(3)] TJ ET BT 25.000 19.825 Td /F1 11.0 Tf [(Young Scientists Journal)] TJ ET Q endstream endobj 67 0 obj << /Type /Page /Parent 3 0 R /Annots [ 69 0 R 71 0 R 73 0 R ] /Contents 68 0 R >> endobj 68 0 obj << /Length 21740 >> stream 0.271 0.267 0.267 rg q 15.000 31.762 577.500 745.238 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Minimax algorithm would work without needing these.)] TJ ET BT 26.250 748.071 Td /F1 9.8 Tf [( Board size, which was changed from 33 to other sizes when necessary.)] TJ ET BT 26.250 728.667 Td /F1 9.8 Tf [(One thing we noted was when we set the program to play against itself, both players co-operated for a Player 1 victory. This )] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(meant that we had to play AI vs AI games across two different computers, manually inputting the computers successive moves )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(using the keyboards.)] TJ ET BT 26.250 685.452 Td /F1 9.8 Tf [(When we ran the game against a human it played without bugs, but not particularly well. We wanted to improve the codes )] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(ability to play the game. We decided to try to improve the programs intelligence by increasing the search depth.)] TJ ET BT 26.250 654.143 Td /F1 9.8 Tf [(Search Depth)] TJ ET BT 26.250 634.738 Td /F1 9.8 Tf [(The search depth is the amount of possible moves into the future that the program calculates. For example, a search depth of 5 )] TJ ET BT 26.250 622.833 Td /F1 9.8 Tf [(calculates the Minimax algorithm value for every possible string of moves of length 5.)] TJ ET BT 26.250 603.429 Td /F1 9.8 Tf [(This would dramatically increase our computation times for larger boards, and so if we wanted to make sure our program played )] TJ ET BT 26.250 591.524 Td /F1 9.8 Tf [(optimally before exploring more powerful computational systems we would need to reduce our board size to compensate for the )] TJ ET BT 26.250 579.619 Td /F1 9.8 Tf [(increased computation. Increasing the search depth would make the program examine every possible combination of moves up )] TJ ET BT 26.250 567.714 Td /F1 9.8 Tf [(to the specified number and any set of moves that are not optimal are not computed as they are removed by Alpha-Beta )] TJ ET BT 26.250 555.810 Td /F1 9.8 Tf [(pruning, which reduces the time needed to compute.)] TJ ET BT 26.250 536.405 Td /F1 9.8 Tf [(We used search depths of between 3 and 5 on board sizes of between 3 and 6 to try and see if our code was playing better )] TJ ET BT 26.250 524.500 Td /F1 9.8 Tf [(than it did previously. In order to do this, we set some games with a search depth of 0 so that the program would play randomly )] TJ ET BT 26.250 512.595 Td /F1 9.8 Tf [(and if our program played better than random we took that as showing an improvement in play over pure chance. Our program )] TJ ET BT 26.250 500.691 Td /F1 9.8 Tf [(performed much better than when playing at random and the programs ability increased with an increased search depth. The )] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(problem is that for any large board and/or a large search depth the time taken to compute is not realistic for one of our laptops. )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(The time to play full game was on the order of thousands of years on some settings, making this method impractical for most )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(scenarios, especially ones of interest.)] TJ ET BT 26.250 445.572 Td /F1 9.8 Tf [(At this point we realised that our own computational power was no longer sufficient for our investigations needs and so we )] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(began to look at obtaining the use of a High-Performance Computing facility, otherwise known as a supercomputer.)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Use of High-Performance Computing)] TJ ET BT 26.250 394.857 Td /F1 9.8 Tf [(We were awarded a Class C Project)] TJ ET 0.267 0.267 0.267 rg BT 182.835 396.365 Td /F4 8.7 Tf [(3)] TJ ET 0.271 0.267 0.267 rg BT 187.654 394.857 Td /F1 9.8 Tf [( by the Irish Centre for High-End Computing \(ICHEC\). We applied to them because they )] TJ ET BT 26.250 382.953 Td /F1 9.8 Tf [(have had previous experience with the BTYS Exhibition and access to the facility could be interfaced from our school over the )] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(internet without needing to travel to the facility itself. We were introduced via email to Dr Simon Wong, a computational scientist )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(working for ICHEC. He kindly agreed to provide us with the technical expertise and requisite permissions in order to access )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(ICHECs facilities.)] TJ ET BT 26.250 327.834 Td /F5 9.8 Tf [(Fionn )] TJ ET BT 53.345 327.834 Td /F1 9.8 Tf [(Supercomputer)] TJ ET BT 26.250 308.429 Td /F1 9.8 Tf [(Dr Wong provided us with advice and support for our use of ICHECs High-Performance Computing facility, named Fionn. We )] TJ ET BT 26.250 296.524 Td /F1 9.8 Tf [(were awarded a Class C Discovery project classification by ICHEC for our investigation. As a result, we were provided with the )] TJ ET BT 26.250 284.619 Td /F1 9.8 Tf [(following resources for our work:)] TJ ET BT 26.250 265.215 Td /F1 9.8 Tf [( 60,000 core-hours of processing time)] TJ ET BT 26.250 245.810 Td /F1 9.8 Tf [( 100 GB of storage)] TJ ET BT 26.250 226.405 Td /F1 9.8 Tf [( 3 User accounts)] TJ ET BT 26.250 207.000 Td /F1 9.8 Tf [(Using the Putty computer program we were able to interface onto Fionn from our school with the help of our teacher, Dr Kerins.)] TJ ET BT 26.250 187.596 Td /F1 9.8 Tf [(One significant issue we encountered was the firewall used to protect ICHECs network infrastructure from unauthorised usage. )] TJ ET BT 26.250 175.691 Td /F1 9.8 Tf [(As we could not access a fixed IP address at school we thought we would not be in a position to use )] TJ ET BT 460.895 175.691 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 485.280 175.691 Td /F1 9.8 Tf [(. Niall Wilson, the )] TJ ET BT 26.250 163.786 Td /F1 9.8 Tf [(Infrastructure Manager of ICHEC, was very helpful to us in arranging the IP exceptions for us to access )] TJ ET BT 473.317 163.786 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 497.702 163.786 Td /F1 9.8 Tf [( from our school.)] TJ ET BT 26.250 144.381 Td /F1 9.8 Tf [(Fionn uses a Linux-based operating system. It doesnt have a Graphical User Interface \(GUI\) like Windows and OSX has, )] TJ ET BT 26.250 132.477 Td /F1 9.8 Tf [(instead using typed commands to complete functions. Therefore, we used command line inputs to transfer our program onto our )] TJ ET BT 26.250 120.572 Td /F1 9.8 Tf [(folder from the PC in the Physics laboratory.)] TJ ET BT 26.250 101.167 Td /F1 9.8 Tf [(The command line system was very strange at the start but with Dr Kerins guidance we managed to get our program up and )] TJ ET BT 26.250 89.262 Td /F1 9.8 Tf [(running on Fionn. We were only able to use the login node on Fionn because we were unable to package our program in a )] TJ ET BT 26.250 77.358 Td /F1 9.8 Tf [(suitable way.)] TJ ET BT 26.250 57.953 Td /F1 9.8 Tf [(In order to be able to utilise the full computational power of Fionn we would have needed to parallelise our program. )] TJ ET BT 26.250 46.048 Td /F1 9.8 Tf [(Parallelisation is where a computational task is broken down into smaller problems solved simultaneously by multiple cores. )] TJ ET Q q 15.000 31.762 577.500 745.238 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Minimax algorithm would work without needing these.)] TJ ET BT 26.250 748.071 Td /F1 9.8 Tf [( Board size, which was changed from 33 to other sizes when necessary.)] TJ ET BT 26.250 728.667 Td /F1 9.8 Tf [(One thing we noted was when we set the program to play against itself, both players co-operated for a Player 1 victory. This )] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(meant that we had to play AI vs AI games across two different computers, manually inputting the computers successive moves )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(using the keyboards.)] TJ ET BT 26.250 685.452 Td /F1 9.8 Tf [(When we ran the game against a human it played without bugs, but not particularly well. We wanted to improve the codes )] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(ability to play the game. We decided to try to improve the programs intelligence by increasing the search depth.)] TJ ET BT 26.250 654.143 Td /F1 9.8 Tf [(Search Depth)] TJ ET BT 26.250 634.738 Td /F1 9.8 Tf [(The search depth is the amount of possible moves into the future that the program calculates. For example, a search depth of 5 )] TJ ET BT 26.250 622.833 Td /F1 9.8 Tf [(calculates the Minimax algorithm value for every possible string of moves of length 5.)] TJ ET BT 26.250 603.429 Td /F1 9.8 Tf [(This would dramatically increase our computation times for larger boards, and so if we wanted to make sure our program played )] TJ ET BT 26.250 591.524 Td /F1 9.8 Tf [(optimally before exploring more powerful computational systems we would need to reduce our board size to compensate for the )] TJ ET BT 26.250 579.619 Td /F1 9.8 Tf [(increased computation. Increasing the search depth would make the program examine every possible combination of moves up )] TJ ET BT 26.250 567.714 Td /F1 9.8 Tf [(to the specified number and any set of moves that are not optimal are not computed as they are removed by Alpha-Beta )] TJ ET BT 26.250 555.810 Td /F1 9.8 Tf [(pruning, which reduces the time needed to compute.)] TJ ET BT 26.250 536.405 Td /F1 9.8 Tf [(We used search depths of between 3 and 5 on board sizes of between 3 and 6 to try and see if our code was playing better )] TJ ET BT 26.250 524.500 Td /F1 9.8 Tf [(than it did previously. In order to do this, we set some games with a search depth of 0 so that the program would play randomly )] TJ ET BT 26.250 512.595 Td /F1 9.8 Tf [(and if our program played better than random we took that as showing an improvement in play over pure chance. Our program )] TJ ET BT 26.250 500.691 Td /F1 9.8 Tf [(performed much better than when playing at random and the programs ability increased with an increased search depth. The )] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(problem is that for any large board and/or a large search depth the time taken to compute is not realistic for one of our laptops. )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(The time to play full game was on the order of thousands of years on some settings, making this method impractical for most )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(scenarios, especially ones of interest.)] TJ ET BT 26.250 445.572 Td /F1 9.8 Tf [(At this point we realised that our own computational power was no longer sufficient for our investigations needs and so we )] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(began to look at obtaining the use of a High-Performance Computing facility, otherwise known as a supercomputer.)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Use of High-Performance Computing)] TJ ET BT 26.250 394.857 Td /F1 9.8 Tf [(We were awarded a Class C Project)] TJ ET 0.267 0.267 0.267 rg BT 182.835 396.365 Td /F4 8.7 Tf [(3)] TJ ET 0.271 0.267 0.267 rg BT 187.654 394.857 Td /F1 9.8 Tf [( by the Irish Centre for High-End Computing \(ICHEC\). We applied to them because they )] TJ ET BT 26.250 382.953 Td /F1 9.8 Tf [(have had previous experience with the BTYS Exhibition and access to the facility could be interfaced from our school over the )] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(internet without needing to travel to the facility itself. We were introduced via email to Dr Simon Wong, a computational scientist )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(working for ICHEC. He kindly agreed to provide us with the technical expertise and requisite permissions in order to access )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(ICHECs facilities.)] TJ ET BT 26.250 327.834 Td /F5 9.8 Tf [(Fionn )] TJ ET BT 53.345 327.834 Td /F1 9.8 Tf [(Supercomputer)] TJ ET BT 26.250 308.429 Td /F1 9.8 Tf [(Dr Wong provided us with advice and support for our use of ICHECs High-Performance Computing facility, named Fionn. We )] TJ ET BT 26.250 296.524 Td /F1 9.8 Tf [(were awarded a Class C Discovery project classification by ICHEC for our investigation. As a result, we were provided with the )] TJ ET BT 26.250 284.619 Td /F1 9.8 Tf [(following resources for our work:)] TJ ET BT 26.250 265.215 Td /F1 9.8 Tf [( 60,000 core-hours of processing time)] TJ ET BT 26.250 245.810 Td /F1 9.8 Tf [( 100 GB of storage)] TJ ET BT 26.250 226.405 Td /F1 9.8 Tf [( 3 User accounts)] TJ ET BT 26.250 207.000 Td /F1 9.8 Tf [(Using the Putty computer program we were able to interface onto Fionn from our school with the help of our teacher, Dr Kerins.)] TJ ET BT 26.250 187.596 Td /F1 9.8 Tf [(One significant issue we encountered was the firewall used to protect ICHECs network infrastructure from unauthorised usage. )] TJ ET BT 26.250 175.691 Td /F1 9.8 Tf [(As we could not access a fixed IP address at school we thought we would not be in a position to use )] TJ ET BT 460.895 175.691 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 485.280 175.691 Td /F1 9.8 Tf [(. Niall Wilson, the )] TJ ET BT 26.250 163.786 Td /F1 9.8 Tf [(Infrastructure Manager of ICHEC, was very helpful to us in arranging the IP exceptions for us to access )] TJ ET BT 473.317 163.786 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 497.702 163.786 Td /F1 9.8 Tf [( from our school.)] TJ ET BT 26.250 144.381 Td /F1 9.8 Tf [(Fionn uses a Linux-based operating system. It doesnt have a Graphical User Interface \(GUI\) like Windows and OSX has, )] TJ ET BT 26.250 132.477 Td /F1 9.8 Tf [(instead using typed commands to complete functions. Therefore, we used command line inputs to transfer our program onto our )] TJ ET BT 26.250 120.572 Td /F1 9.8 Tf [(folder from the PC in the Physics laboratory.)] TJ ET BT 26.250 101.167 Td /F1 9.8 Tf [(The command line system was very strange at the start but with Dr Kerins guidance we managed to get our program up and )] TJ ET BT 26.250 89.262 Td /F1 9.8 Tf [(running on Fionn. We were only able to use the login node on Fionn because we were unable to package our program in a )] TJ ET BT 26.250 77.358 Td /F1 9.8 Tf [(suitable way.)] TJ ET BT 26.250 57.953 Td /F1 9.8 Tf [(In order to be able to utilise the full computational power of Fionn we would have needed to parallelise our program. )] TJ ET BT 26.250 46.048 Td /F1 9.8 Tf [(Parallelisation is where a computational task is broken down into smaller problems solved simultaneously by multiple cores. )] TJ ET Q q 15.000 31.762 577.500 745.238 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(Minimax algorithm would work without needing these.)] TJ ET BT 26.250 748.071 Td /F1 9.8 Tf [( Board size, which was changed from 33 to other sizes when necessary.)] TJ ET BT 26.250 728.667 Td /F1 9.8 Tf [(One thing we noted was when we set the program to play against itself, both players co-operated for a Player 1 victory. This )] TJ ET BT 26.250 716.762 Td /F1 9.8 Tf [(meant that we had to play AI vs AI games across two different computers, manually inputting the computers successive moves )] TJ ET BT 26.250 704.857 Td /F1 9.8 Tf [(using the keyboards.)] TJ ET BT 26.250 685.452 Td /F1 9.8 Tf [(When we ran the game against a human it played without bugs, but not particularly well. We wanted to improve the codes )] TJ ET BT 26.250 673.548 Td /F1 9.8 Tf [(ability to play the game. We decided to try to improve the programs intelligence by increasing the search depth.)] TJ ET BT 26.250 654.143 Td /F1 9.8 Tf [(Search Depth)] TJ ET BT 26.250 634.738 Td /F1 9.8 Tf [(The search depth is the amount of possible moves into the future that the program calculates. For example, a search depth of 5 )] TJ ET BT 26.250 622.833 Td /F1 9.8 Tf [(calculates the Minimax algorithm value for every possible string of moves of length 5.)] TJ ET BT 26.250 603.429 Td /F1 9.8 Tf [(This would dramatically increase our computation times for larger boards, and so if we wanted to make sure our program played )] TJ ET BT 26.250 591.524 Td /F1 9.8 Tf [(optimally before exploring more powerful computational systems we would need to reduce our board size to compensate for the )] TJ ET BT 26.250 579.619 Td /F1 9.8 Tf [(increased computation. Increasing the search depth would make the program examine every possible combination of moves up )] TJ ET BT 26.250 567.714 Td /F1 9.8 Tf [(to the specified number and any set of moves that are not optimal are not computed as they are removed by Alpha-Beta )] TJ ET BT 26.250 555.810 Td /F1 9.8 Tf [(pruning, which reduces the time needed to compute.)] TJ ET BT 26.250 536.405 Td /F1 9.8 Tf [(We used search depths of between 3 and 5 on board sizes of between 3 and 6 to try and see if our code was playing better )] TJ ET BT 26.250 524.500 Td /F1 9.8 Tf [(than it did previously. In order to do this, we set some games with a search depth of 0 so that the program would play randomly )] TJ ET BT 26.250 512.595 Td /F1 9.8 Tf [(and if our program played better than random we took that as showing an improvement in play over pure chance. Our program )] TJ ET BT 26.250 500.691 Td /F1 9.8 Tf [(performed much better than when playing at random and the programs ability increased with an increased search depth. The )] TJ ET BT 26.250 488.786 Td /F1 9.8 Tf [(problem is that for any large board and/or a large search depth the time taken to compute is not realistic for one of our laptops. )] TJ ET BT 26.250 476.881 Td /F1 9.8 Tf [(The time to play full game was on the order of thousands of years on some settings, making this method impractical for most )] TJ ET BT 26.250 464.976 Td /F1 9.8 Tf [(scenarios, especially ones of interest.)] TJ ET BT 26.250 445.572 Td /F1 9.8 Tf [(At this point we realised that our own computational power was no longer sufficient for our investigations needs and so we )] TJ ET BT 26.250 433.667 Td /F1 9.8 Tf [(began to look at obtaining the use of a High-Performance Computing facility, otherwise known as a supercomputer.)] TJ ET BT 26.250 414.262 Td /F1 9.8 Tf [(Use of High-Performance Computing)] TJ ET BT 26.250 394.857 Td /F1 9.8 Tf [(We were awarded a Class C Project)] TJ ET 0.267 0.267 0.267 rg BT 182.835 396.365 Td /F4 8.7 Tf [(3)] TJ ET 0.271 0.267 0.267 rg BT 187.654 394.857 Td /F1 9.8 Tf [( by the Irish Centre for High-End Computing \(ICHEC\). We applied to them because they )] TJ ET BT 26.250 382.953 Td /F1 9.8 Tf [(have had previous experience with the BTYS Exhibition and access to the facility could be interfaced from our school over the )] TJ ET BT 26.250 371.048 Td /F1 9.8 Tf [(internet without needing to travel to the facility itself. We were introduced via email to Dr Simon Wong, a computational scientist )] TJ ET BT 26.250 359.143 Td /F1 9.8 Tf [(working for ICHEC. He kindly agreed to provide us with the technical expertise and requisite permissions in order to access )] TJ ET BT 26.250 347.238 Td /F1 9.8 Tf [(ICHECs facilities.)] TJ ET BT 26.250 327.834 Td /F5 9.8 Tf [(Fionn )] TJ ET BT 53.345 327.834 Td /F1 9.8 Tf [(Supercomputer)] TJ ET BT 26.250 308.429 Td /F1 9.8 Tf [(Dr Wong provided us with advice and support for our use of ICHECs High-Performance Computing facility, named Fionn. We )] TJ ET BT 26.250 296.524 Td /F1 9.8 Tf [(were awarded a Class C Discovery project classification by ICHEC for our investigation. As a result, we were provided with the )] TJ ET BT 26.250 284.619 Td /F1 9.8 Tf [(following resources for our work:)] TJ ET BT 26.250 265.215 Td /F1 9.8 Tf [( 60,000 core-hours of processing time)] TJ ET BT 26.250 245.810 Td /F1 9.8 Tf [( 100 GB of storage)] TJ ET BT 26.250 226.405 Td /F1 9.8 Tf [( 3 User accounts)] TJ ET BT 26.250 207.000 Td /F1 9.8 Tf [(Using the Putty computer program we were able to interface onto Fionn from our school with the help of our teacher, Dr Kerins.)] TJ ET BT 26.250 187.596 Td /F1 9.8 Tf [(One significant issue we encountered was the firewall used to protect ICHECs network infrastructure from unauthorised usage. )] TJ ET BT 26.250 175.691 Td /F1 9.8 Tf [(As we could not access a fixed IP address at school we thought we would not be in a position to use )] TJ ET BT 460.895 175.691 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 485.280 175.691 Td /F1 9.8 Tf [(. Niall Wilson, the )] TJ ET BT 26.250 163.786 Td /F1 9.8 Tf [(Infrastructure Manager of ICHEC, was very helpful to us in arranging the IP exceptions for us to access )] TJ ET BT 473.317 163.786 Td /F5 9.8 Tf [(Fionn)] TJ ET BT 497.702 163.786 Td /F1 9.8 Tf [( from our school.)] TJ ET BT 26.250 144.381 Td /F1 9.8 Tf [(Fionn uses a Linux-based operating system. It doesnt have a Graphical User Interface \(GUI\) like Windows and OSX has, )] TJ ET BT 26.250 132.477 Td /F1 9.8 Tf [(instead using typed commands to complete functions. Therefore, we used command line inputs to transfer our program onto our )] TJ ET BT 26.250 120.572 Td /F1 9.8 Tf [(folder from the PC in the Physics laboratory.)] TJ ET BT 26.250 101.167 Td /F1 9.8 Tf [(The command line system was very strange at the start but with Dr Kerins guidance we managed to get our program up and )] TJ ET BT 26.250 89.262 Td /F1 9.8 Tf [(running on Fionn. We were only able to use the login node on Fionn because we were unable to package our program in a )] TJ ET BT 26.250 77.358 Td /F1 9.8 Tf [(suitable way.)] TJ ET BT 26.250 57.953 Td /F1 9.8 Tf [(In order to be able to utilise the full computational power of Fionn we would have needed to parallelise our program. )] TJ ET BT 26.250 46.048 Td /F1 9.8 Tf [(Parallelisation is where a computational task is broken down into smaller problems solved simultaneously by multiple cores. )] TJ ET Q q 0.000 0.000 0.000 rg BT 291.710 19.825 Td /F1 11.0 Tf [(4)] TJ ET BT 25.000 19.825 Td /F1 11.0 Tf [(Young Scientists Journal)] TJ ET Q endstream endobj 69 0 obj << /Type /Annot /Subtype /Link /A 70 0 R /Border [0 0 0] /H /I /Rect [ 182.8350 395.5629 187.6537 404.3813 ] >> endobj 70 0 obj << /Type /Action >> endobj 71 0 obj << /Type /Annot /Subtype /Link /A 72 0 R /Border [0 0 0] /H /I /Rect [ 182.8350 395.5629 187.6537 404.3813 ] >> endobj 72 0 obj << /Type /Action >> endobj 73 0 obj << /Type /Annot /Subtype /Link /A 74 0 R /Border [0 0 0] /H /I /Rect [ 182.8350 395.5629 187.6537 404.3813 ] >> endobj 74 0 obj << /Type /Action >> endobj 75 0 obj << /Type /Page /Parent 3 0 R /Contents 76 0 R >> endobj 76 0 obj << /Length 19469 >> stream 0.271 0.267 0.267 rg q 15.000 21.735 577.500 755.265 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(This is why High-Performance Computing is effective in solving otherwise impractical computations. We were not in a position to )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(do this for two reasons.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(Firstly, by the time we were satisfied with our program and arranged a relaxation of the firewall it was mid-December and we )] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(simply had no time remaining to parallelise our program. Secondly, for a programme to be parallelised it needs to be an )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(executable file. This means that it can be run independently without any user inputs. By the time we had access to Fionn we )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(were still unable to make the programme play effectively against itself and so we had to manually play one computer against )] TJ ET BT 26.250 688.548 Td /F1 9.8 Tf [(another. This issue prevents the parallelisation of the program for now.)] TJ ET BT 26.250 669.143 Td /F1 9.8 Tf [(We instead investigated smaller board sizes where optimal gameplay was already established in order to see if our game )] TJ ET BT 26.250 657.238 Td /F1 9.8 Tf [(played effectively for these established n and to ascertain whether High-Performance Computing facilities could be applied to )] TJ ET BT 26.250 645.333 Td /F1 9.8 Tf [(our investigation sometime in the future as a proof-of-concept. Having had positive results from this, we increased the size of )] TJ ET BT 26.250 633.429 Td /F1 9.8 Tf [(the board to sizes where optimal play results were unknown, but to compensate for this we had to lower the search depth, )] TJ ET BT 26.250 621.524 Td /F1 9.8 Tf [(meaning that moves that were less optimal would ensue.)] TJ ET BT 26.250 584.921 Td /F4 12.0 Tf [(Results and Conclusions)] TJ ET BT 26.250 564.967 Td /F1 9.8 Tf [(Control of Central Squares)] TJ ET BT 26.250 545.562 Td /F1 9.8 Tf [(The first result we obtained from our investigations is that control of the central squares of the board is advantageous, )] TJ ET BT 26.250 533.658 Td /F1 9.8 Tf [(irrespective of board size. In addition, the setting up of several possible winning move combinations is important for attempting )] TJ ET BT 26.250 521.753 Td /F1 9.8 Tf [(to create a dilemma situation for an opponent From this, we can conclude that the opening moves of an optimal game will be to )] TJ ET BT 26.250 509.848 Td /F1 9.8 Tf [(the middle squares and that the control of these would form part of an optimal gameplay strategy.)] TJ ET BT 26.250 490.443 Td /F1 9.8 Tf [(Use of Dilemmas in Gameplay)] TJ ET BT 26.250 471.039 Td /F1 9.8 Tf [(A dilemma, as discussed above, is where a player propagates a scenario where they have more than one winning move )] TJ ET BT 26.250 459.134 Td /F1 9.8 Tf [(available to them, ensuring a victory. The applications of dilemmas were discussed at length earlier, and whilst we were not able )] TJ ET BT 26.250 447.229 Td /F1 9.8 Tf [(to incorporate the dilemmas per se into our program, if the search depth is sufficient the Minimax algorithm will recognise an )] TJ ET BT 26.250 435.324 Td /F1 9.8 Tf [(upcoming dilemma for an opponent and attempt to force it. Equally, it will try to propagate them for the opponent. As in chess, )] TJ ET BT 26.250 423.420 Td /F1 9.8 Tf [(draughts and other deterministic two-player games, dilemmas are a vital part of any successful gameplay strategy and are )] TJ ET BT 26.250 411.515 Td /F1 9.8 Tf [(surely a part of an optimal one. As successful creation of a dilemma for an opponent creates a certain win, we can conclude that )] TJ ET BT 26.250 399.610 Td /F1 9.8 Tf [(they form a part of an optimal gameplay strategy.)] TJ ET BT 26.250 380.205 Td /F1 9.8 Tf [(Full/Near-Full Board at end of mutual Optimal Gameplay)] TJ ET BT 26.250 360.801 Td /F1 9.8 Tf [(In the course of our investigation, we discovered that the AI never won quickly when the opponent, either AI or human, played )] TJ ET BT 26.250 348.896 Td /F1 9.8 Tf [(well. The board was always full or nearly full before a conclusion to the game emerged. This happened more when the search )] TJ ET BT 26.250 336.991 Td /F1 9.8 Tf [(depth increased and the game played against itself better. From this, we believe that no shortcuts to a win in mutual optimal )] TJ ET BT 26.250 325.086 Td /F1 9.8 Tf [(play exist and that optimal games need to be played almost, or completely, to exhaustion before a win for either player results.)] TJ ET BT 26.250 288.484 Td /F4 12.0 Tf [(Improvements and Further Work)] TJ ET BT 26.250 268.530 Td /F1 9.8 Tf [(Resolution to the AI Problem)] TJ ET BT 26.250 249.125 Td /F1 9.8 Tf [(We feel that the main problem we had in our investigation was our inability to make our program play against itself )] TJ ET BT 26.250 237.220 Td /F1 9.8 Tf [(automatically. Whenever we tried to do this, both AI players co-operated for a Player 1 win. In order to make further progress )] TJ ET BT 26.250 225.315 Td /F1 9.8 Tf [(towards an optimal strategy, we will need to fix this issue. We believe the issue is that the program is maximising Player 1s )] TJ ET BT 26.250 213.411 Td /F1 9.8 Tf [(Minimax algorithm value with both players moves.)] TJ ET BT 26.250 194.006 Td /F1 9.8 Tf [(Parallelisation of the Program)] TJ ET BT 26.250 174.601 Td /F1 9.8 Tf [(If the above problem can be dealt with, then parallelisation of the program will be possible. This means that the full )] TJ ET BT 26.250 162.696 Td /F1 9.8 Tf [(computational power of a High-Performance Computing facility could be utilised to solve games for higher values of n and )] TJ ET BT 26.250 150.792 Td /F1 9.8 Tf [(possibly find an optimal strategy in the future.)] TJ ET BT 26.250 131.387 Td /F1 9.8 Tf [(Further Investigation using High-Performance Computing)] TJ ET BT 26.250 111.982 Td /F1 9.8 Tf [(We think that if the above recommendations can be implemented, this investigation could be taken a step further and some )] TJ ET BT 26.250 100.077 Td /F1 9.8 Tf [(definite strategies could be discovered if computed at full search depths by a High-Performance Computing facility.)] TJ ET BT 26.250 80.673 Td /F1 9.8 Tf [(We intend to continue our work in the future and implement these improvements.)] TJ ET BT 26.250 44.070 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET Q q 15.000 21.735 577.500 755.265 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(This is why High-Performance Computing is effective in solving otherwise impractical computations. We were not in a position to )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(do this for two reasons.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(Firstly, by the time we were satisfied with our program and arranged a relaxation of the firewall it was mid-December and we )] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(simply had no time remaining to parallelise our program. Secondly, for a programme to be parallelised it needs to be an )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(executable file. This means that it can be run independently without any user inputs. By the time we had access to Fionn we )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(were still unable to make the programme play effectively against itself and so we had to manually play one computer against )] TJ ET BT 26.250 688.548 Td /F1 9.8 Tf [(another. This issue prevents the parallelisation of the program for now.)] TJ ET BT 26.250 669.143 Td /F1 9.8 Tf [(We instead investigated smaller board sizes where optimal gameplay was already established in order to see if our game )] TJ ET BT 26.250 657.238 Td /F1 9.8 Tf [(played effectively for these established n and to ascertain whether High-Performance Computing facilities could be applied to )] TJ ET BT 26.250 645.333 Td /F1 9.8 Tf [(our investigation sometime in the future as a proof-of-concept. Having had positive results from this, we increased the size of )] TJ ET BT 26.250 633.429 Td /F1 9.8 Tf [(the board to sizes where optimal play results were unknown, but to compensate for this we had to lower the search depth, )] TJ ET BT 26.250 621.524 Td /F1 9.8 Tf [(meaning that moves that were less optimal would ensue.)] TJ ET BT 26.250 584.921 Td /F4 12.0 Tf [(Results and Conclusions)] TJ ET BT 26.250 564.967 Td /F1 9.8 Tf [(Control of Central Squares)] TJ ET BT 26.250 545.562 Td /F1 9.8 Tf [(The first result we obtained from our investigations is that control of the central squares of the board is advantageous, )] TJ ET BT 26.250 533.658 Td /F1 9.8 Tf [(irrespective of board size. In addition, the setting up of several possible winning move combinations is important for attempting )] TJ ET BT 26.250 521.753 Td /F1 9.8 Tf [(to create a dilemma situation for an opponent From this, we can conclude that the opening moves of an optimal game will be to )] TJ ET BT 26.250 509.848 Td /F1 9.8 Tf [(the middle squares and that the control of these would form part of an optimal gameplay strategy.)] TJ ET BT 26.250 490.443 Td /F1 9.8 Tf [(Use of Dilemmas in Gameplay)] TJ ET BT 26.250 471.039 Td /F1 9.8 Tf [(A dilemma, as discussed above, is where a player propagates a scenario where they have more than one winning move )] TJ ET BT 26.250 459.134 Td /F1 9.8 Tf [(available to them, ensuring a victory. The applications of dilemmas were discussed at length earlier, and whilst we were not able )] TJ ET BT 26.250 447.229 Td /F1 9.8 Tf [(to incorporate the dilemmas per se into our program, if the search depth is sufficient the Minimax algorithm will recognise an )] TJ ET BT 26.250 435.324 Td /F1 9.8 Tf [(upcoming dilemma for an opponent and attempt to force it. Equally, it will try to propagate them for the opponent. As in chess, )] TJ ET BT 26.250 423.420 Td /F1 9.8 Tf [(draughts and other deterministic two-player games, dilemmas are a vital part of any successful gameplay strategy and are )] TJ ET BT 26.250 411.515 Td /F1 9.8 Tf [(surely a part of an optimal one. As successful creation of a dilemma for an opponent creates a certain win, we can conclude that )] TJ ET BT 26.250 399.610 Td /F1 9.8 Tf [(they form a part of an optimal gameplay strategy.)] TJ ET BT 26.250 380.205 Td /F1 9.8 Tf [(Full/Near-Full Board at end of mutual Optimal Gameplay)] TJ ET BT 26.250 360.801 Td /F1 9.8 Tf [(In the course of our investigation, we discovered that the AI never won quickly when the opponent, either AI or human, played )] TJ ET BT 26.250 348.896 Td /F1 9.8 Tf [(well. The board was always full or nearly full before a conclusion to the game emerged. This happened more when the search )] TJ ET BT 26.250 336.991 Td /F1 9.8 Tf [(depth increased and the game played against itself better. From this, we believe that no shortcuts to a win in mutual optimal )] TJ ET BT 26.250 325.086 Td /F1 9.8 Tf [(play exist and that optimal games need to be played almost, or completely, to exhaustion before a win for either player results.)] TJ ET BT 26.250 288.484 Td /F4 12.0 Tf [(Improvements and Further Work)] TJ ET BT 26.250 268.530 Td /F1 9.8 Tf [(Resolution to the AI Problem)] TJ ET BT 26.250 249.125 Td /F1 9.8 Tf [(We feel that the main problem we had in our investigation was our inability to make our program play against itself )] TJ ET BT 26.250 237.220 Td /F1 9.8 Tf [(automatically. Whenever we tried to do this, both AI players co-operated for a Player 1 win. In order to make further progress )] TJ ET BT 26.250 225.315 Td /F1 9.8 Tf [(towards an optimal strategy, we will need to fix this issue. We believe the issue is that the program is maximising Player 1s )] TJ ET BT 26.250 213.411 Td /F1 9.8 Tf [(Minimax algorithm value with both players moves.)] TJ ET BT 26.250 194.006 Td /F1 9.8 Tf [(Parallelisation of the Program)] TJ ET BT 26.250 174.601 Td /F1 9.8 Tf [(If the above problem can be dealt with, then parallelisation of the program will be possible. This means that the full )] TJ ET BT 26.250 162.696 Td /F1 9.8 Tf [(computational power of a High-Performance Computing facility could be utilised to solve games for higher values of n and )] TJ ET BT 26.250 150.792 Td /F1 9.8 Tf [(possibly find an optimal strategy in the future.)] TJ ET BT 26.250 131.387 Td /F1 9.8 Tf [(Further Investigation using High-Performance Computing)] TJ ET BT 26.250 111.982 Td /F1 9.8 Tf [(We think that if the above recommendations can be implemented, this investigation could be taken a step further and some )] TJ ET BT 26.250 100.077 Td /F1 9.8 Tf [(definite strategies could be discovered if computed at full search depths by a High-Performance Computing facility.)] TJ ET BT 26.250 80.673 Td /F1 9.8 Tf [(We intend to continue our work in the future and implement these improvements.)] TJ ET BT 26.250 44.070 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET Q q 15.000 21.735 577.500 755.265 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(This is why High-Performance Computing is effective in solving otherwise impractical computations. We were not in a position to )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(do this for two reasons.)] TJ ET BT 26.250 736.167 Td /F1 9.8 Tf [(Firstly, by the time we were satisfied with our program and arranged a relaxation of the firewall it was mid-December and we )] TJ ET BT 26.250 724.262 Td /F1 9.8 Tf [(simply had no time remaining to parallelise our program. Secondly, for a programme to be parallelised it needs to be an )] TJ ET BT 26.250 712.357 Td /F1 9.8 Tf [(executable file. This means that it can be run independently without any user inputs. By the time we had access to Fionn we )] TJ ET BT 26.250 700.452 Td /F1 9.8 Tf [(were still unable to make the programme play effectively against itself and so we had to manually play one computer against )] TJ ET BT 26.250 688.548 Td /F1 9.8 Tf [(another. This issue prevents the parallelisation of the program for now.)] TJ ET BT 26.250 669.143 Td /F1 9.8 Tf [(We instead investigated smaller board sizes where optimal gameplay was already established in order to see if our game )] TJ ET BT 26.250 657.238 Td /F1 9.8 Tf [(played effectively for these established n and to ascertain whether High-Performance Computing facilities could be applied to )] TJ ET BT 26.250 645.333 Td /F1 9.8 Tf [(our investigation sometime in the future as a proof-of-concept. Having had positive results from this, we increased the size of )] TJ ET BT 26.250 633.429 Td /F1 9.8 Tf [(the board to sizes where optimal play results were unknown, but to compensate for this we had to lower the search depth, )] TJ ET BT 26.250 621.524 Td /F1 9.8 Tf [(meaning that moves that were less optimal would ensue.)] TJ ET BT 26.250 584.921 Td /F4 12.0 Tf [(Results and Conclusions)] TJ ET BT 26.250 564.967 Td /F1 9.8 Tf [(Control of Central Squares)] TJ ET BT 26.250 545.562 Td /F1 9.8 Tf [(The first result we obtained from our investigations is that control of the central squares of the board is advantageous, )] TJ ET BT 26.250 533.658 Td /F1 9.8 Tf [(irrespective of board size. In addition, the setting up of several possible winning move combinations is important for attempting )] TJ ET BT 26.250 521.753 Td /F1 9.8 Tf [(to create a dilemma situation for an opponent From this, we can conclude that the opening moves of an optimal game will be to )] TJ ET BT 26.250 509.848 Td /F1 9.8 Tf [(the middle squares and that the control of these would form part of an optimal gameplay strategy.)] TJ ET BT 26.250 490.443 Td /F1 9.8 Tf [(Use of Dilemmas in Gameplay)] TJ ET BT 26.250 471.039 Td /F1 9.8 Tf [(A dilemma, as discussed above, is where a player propagates a scenario where they have more than one winning move )] TJ ET BT 26.250 459.134 Td /F1 9.8 Tf [(available to them, ensuring a victory. The applications of dilemmas were discussed at length earlier, and whilst we were not able )] TJ ET BT 26.250 447.229 Td /F1 9.8 Tf [(to incorporate the dilemmas per se into our program, if the search depth is sufficient the Minimax algorithm will recognise an )] TJ ET BT 26.250 435.324 Td /F1 9.8 Tf [(upcoming dilemma for an opponent and attempt to force it. Equally, it will try to propagate them for the opponent. As in chess, )] TJ ET BT 26.250 423.420 Td /F1 9.8 Tf [(draughts and other deterministic two-player games, dilemmas are a vital part of any successful gameplay strategy and are )] TJ ET BT 26.250 411.515 Td /F1 9.8 Tf [(surely a part of an optimal one. As successful creation of a dilemma for an opponent creates a certain win, we can conclude that )] TJ ET BT 26.250 399.610 Td /F1 9.8 Tf [(they form a part of an optimal gameplay strategy.)] TJ ET BT 26.250 380.205 Td /F1 9.8 Tf [(Full/Near-Full Board at end of mutual Optimal Gameplay)] TJ ET BT 26.250 360.801 Td /F1 9.8 Tf [(In the course of our investigation, we discovered that the AI never won quickly when the opponent, either AI or human, played )] TJ ET BT 26.250 348.896 Td /F1 9.8 Tf [(well. The board was always full or nearly full before a conclusion to the game emerged. This happened more when the search )] TJ ET BT 26.250 336.991 Td /F1 9.8 Tf [(depth increased and the game played against itself better. From this, we believe that no shortcuts to a win in mutual optimal )] TJ ET BT 26.250 325.086 Td /F1 9.8 Tf [(play exist and that optimal games need to be played almost, or completely, to exhaustion before a win for either player results.)] TJ ET BT 26.250 288.484 Td /F4 12.0 Tf [(Improvements and Further Work)] TJ ET BT 26.250 268.530 Td /F1 9.8 Tf [(Resolution to the AI Problem)] TJ ET BT 26.250 249.125 Td /F1 9.8 Tf [(We feel that the main problem we had in our investigation was our inability to make our program play against itself )] TJ ET BT 26.250 237.220 Td /F1 9.8 Tf [(automatically. Whenever we tried to do this, both AI players co-operated for a Player 1 win. In order to make further progress )] TJ ET BT 26.250 225.315 Td /F1 9.8 Tf [(towards an optimal strategy, we will need to fix this issue. We believe the issue is that the program is maximising Player 1s )] TJ ET BT 26.250 213.411 Td /F1 9.8 Tf [(Minimax algorithm value with both players moves.)] TJ ET BT 26.250 194.006 Td /F1 9.8 Tf [(Parallelisation of the Program)] TJ ET BT 26.250 174.601 Td /F1 9.8 Tf [(If the above problem can be dealt with, then parallelisation of the program will be possible. This means that the full )] TJ ET BT 26.250 162.696 Td /F1 9.8 Tf [(computational power of a High-Performance Computing facility could be utilised to solve games for higher values of n and )] TJ ET BT 26.250 150.792 Td /F1 9.8 Tf [(possibly find an optimal strategy in the future.)] TJ ET BT 26.250 131.387 Td /F1 9.8 Tf [(Further Investigation using High-Performance Computing)] TJ ET BT 26.250 111.982 Td /F1 9.8 Tf [(We think that if the above recommendations can be implemented, this investigation could be taken a step further and some )] TJ ET BT 26.250 100.077 Td /F1 9.8 Tf [(definite strategies could be discovered if computed at full search depths by a High-Performance Computing facility.)] TJ ET BT 26.250 80.673 Td /F1 9.8 Tf [(We intend to continue our work in the future and implement these improvements.)] TJ ET BT 26.250 44.070 Td /F4 12.0 Tf [(Acknowledgements)] TJ ET Q q 0.000 0.000 0.000 rg BT 291.710 19.825 Td /F1 11.0 Tf [(5)] TJ ET BT 25.000 19.825 Td /F1 11.0 Tf [(Young Scientists Journal)] TJ ET Q endstream endobj 77 0 obj << /Type /Page /Parent 3 0 R /Annots [ 79 0 R 81 0 R 83 0 R 85 0 R 87 0 R 89 0 R ] /Contents 78 0 R >> endobj 78 0 obj << /Length 4880 >> stream 0.271 0.267 0.267 rg q 15.000 591.847 577.500 185.153 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(We would like to gratefully acknowledge the contributions to our investigation from the following individuals: Dr Tim Kerins, )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(Coliste an Spioraid Naoimh \(Supervising Teacher\) Dr Anca Mustata, University College Cork \(Project Supervisor\) Dr David )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(Goulding, Tyndall National Institute \(Project Supervisor\) Dr Simon Wong, Irish Centre for High-End Computing \(Research )] TJ ET BT 26.250 731.762 Td /F1 9.8 Tf [(Support\) We would also like to gratefully acknowledge the allocation of a Class C research designation for our investigation )] TJ ET BT 26.250 719.857 Td /F1 9.8 Tf [(from the Irish Centre for High-End Computing. ?)] TJ ET BT 26.250 690.755 Td /F4 12.0 Tf [(References)] TJ ET BT 26.250 663.300 Td /F1 9.8 Tf [(1.)] TJ ET BT 38.132 663.300 Td /F1 9.8 Tf [(Jenrich, T. Guaranteed successful strategies for a square achievement game on an n by n grid 2012)] TJ ET 0.267 0.267 0.267 rg BT 26.250 654.814 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET 0.271 0.267 0.267 rg BT 26.250 636.264 Td /F1 9.8 Tf [(2.)] TJ ET BT 38.132 636.264 Td /F1 9.8 Tf [(Bacher, R., Eliahou, S. Extremal binary matrices without constant 2-squares 2010)] TJ ET BT 26.250 616.860 Td /F1 9.8 Tf [(3.)] TJ ET BT 38.132 616.860 Td /F1 9.8 Tf [(Combinatorial analyses using the Min-Max algorithm.)] TJ ET 0.267 0.267 0.267 rg BT 26.250 608.374 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET Q q 15.000 591.847 577.500 185.153 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(We would like to gratefully acknowledge the contributions to our investigation from the following individuals: Dr Tim Kerins, )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(Coliste an Spioraid Naoimh \(Supervising Teacher\) Dr Anca Mustata, University College Cork \(Project Supervisor\) Dr David )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(Goulding, Tyndall National Institute \(Project Supervisor\) Dr Simon Wong, Irish Centre for High-End Computing \(Research )] TJ ET BT 26.250 731.762 Td /F1 9.8 Tf [(Support\) We would also like to gratefully acknowledge the allocation of a Class C research designation for our investigation )] TJ ET BT 26.250 719.857 Td /F1 9.8 Tf [(from the Irish Centre for High-End Computing. ?)] TJ ET BT 26.250 690.755 Td /F4 12.0 Tf [(References)] TJ ET BT 26.250 663.300 Td /F1 9.8 Tf [(1.)] TJ ET BT 38.132 663.300 Td /F1 9.8 Tf [(Jenrich, T. Guaranteed successful strategies for a square achievement game on an n by n grid 2012)] TJ ET 0.267 0.267 0.267 rg BT 26.250 654.814 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET 0.271 0.267 0.267 rg BT 26.250 636.264 Td /F1 9.8 Tf [(2.)] TJ ET BT 38.132 636.264 Td /F1 9.8 Tf [(Bacher, R., Eliahou, S. Extremal binary matrices without constant 2-squares 2010)] TJ ET BT 26.250 616.860 Td /F1 9.8 Tf [(3.)] TJ ET BT 38.132 616.860 Td /F1 9.8 Tf [(Combinatorial analyses using the Min-Max algorithm.)] TJ ET 0.267 0.267 0.267 rg BT 26.250 608.374 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET Q q 15.000 591.847 577.500 185.153 re W n 0.271 0.267 0.267 rg BT 26.250 767.476 Td /F1 9.8 Tf [(We would like to gratefully acknowledge the contributions to our investigation from the following individuals: Dr Tim Kerins, )] TJ ET BT 26.250 755.571 Td /F1 9.8 Tf [(Coliste an Spioraid Naoimh \(Supervising Teacher\) Dr Anca Mustata, University College Cork \(Project Supervisor\) Dr David )] TJ ET BT 26.250 743.667 Td /F1 9.8 Tf [(Goulding, Tyndall National Institute \(Project Supervisor\) Dr Simon Wong, Irish Centre for High-End Computing \(Research )] TJ ET BT 26.250 731.762 Td /F1 9.8 Tf [(Support\) We would also like to gratefully acknowledge the allocation of a Class C research designation for our investigation )] TJ ET BT 26.250 719.857 Td /F1 9.8 Tf [(from the Irish Centre for High-End Computing. ?)] TJ ET BT 26.250 690.755 Td /F4 12.0 Tf [(References)] TJ ET BT 26.250 663.300 Td /F1 9.8 Tf [(1.)] TJ ET BT 38.132 663.300 Td /F1 9.8 Tf [(Jenrich, T. Guaranteed successful strategies for a square achievement game on an n by n grid 2012)] TJ ET 0.267 0.267 0.267 rg BT 26.250 654.814 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET 0.271 0.267 0.267 rg BT 26.250 636.264 Td /F1 9.8 Tf [(2.)] TJ ET BT 38.132 636.264 Td /F1 9.8 Tf [(Bacher, R., Eliahou, S. Extremal binary matrices without constant 2-squares 2010)] TJ ET BT 26.250 616.860 Td /F1 9.8 Tf [(3.)] TJ ET BT 38.132 616.860 Td /F1 9.8 Tf [(Combinatorial analyses using the Min-Max algorithm.)] TJ ET 0.267 0.267 0.267 rg BT 26.250 608.374 Td /F1 7.5 Tf [(REFERENCE LINK)] TJ ET Q q 0.000 0.000 0.000 rg BT 291.710 19.825 Td /F1 11.0 Tf [(6)] TJ ET BT 25.000 19.825 Td /F1 11.0 Tf [(Young Scientists Journal)] TJ ET Q endstream endobj 79 0 obj << /Type /Annot /Subtype /Link /A 80 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 654.1207 91.2600 661.7520 ] >> endobj 80 0 obj << /Type /Action /S /URI /URI (http://arxiv.org/abs/1109.2341) >> endobj 81 0 obj << /Type /Annot /Subtype /Link /A 82 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 607.6800 91.2600 615.3112 ] >> endobj 82 0 obj << /Type /Action /S /URI /URI (https://www.ichec.ie/research/expired_projects/iccom006c) >> endobj 83 0 obj << /Type /Annot /Subtype /Link /A 84 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 654.1207 91.2600 661.7520 ] >> endobj 84 0 obj << /Type /Action /S /URI /URI (http://arxiv.org/abs/1109.2341) >> endobj 85 0 obj << /Type /Annot /Subtype /Link /A 86 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 607.6800 91.2600 615.3112 ] >> endobj 86 0 obj << /Type /Action /S /URI /URI (https://www.ichec.ie/research/expired_projects/iccom006c) >> endobj 87 0 obj << /Type /Annot /Subtype /Link /A 88 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 654.1207 91.2600 661.7520 ] >> endobj 88 0 obj << /Type /Action /S /URI /URI (http://arxiv.org/abs/1109.2341) >> endobj 89 0 obj << /Type /Annot /Subtype /Link /A 90 0 R /Border [0 0 0] /H /I /Rect [ 26.2500 607.6800 91.2600 615.3112 ] >> endobj 90 0 obj << /Type /Action /S /URI /URI (https://www.ichec.ie/research/expired_projects/iccom006c) >> endobj xref 0 91 0000000000 65535 f 0000000008 00000 n 0000000073 00000 n 0000000119 00000 n 0000000389 00000 n 0000000426 00000 n 0000000647 00000 n 0000000848 00000 n 0000017548 00000 n 0000017655 00000 n 0000017763 00000 n 0000017874 00000 n 0000017987 00000 n 0000018103 00000 n 0000021513 00000 n 0000030360 00000 n 0000030487 00000 n 0000030646 00000 n 0000030773 00000 n 0000030932 00000 n 0000031060 00000 n 0000031164 00000 n 0000031291 00000 n 0000031392 00000 n 0000031520 00000 n 0000031633 00000 n 0000031761 00000 n 0000031856 00000 n 0000031983 00000 n 0000032142 00000 n 0000032269 00000 n 0000032428 00000 n 0000032556 00000 n 0000032660 00000 n 0000032787 00000 n 0000032888 00000 n 0000033016 00000 n 0000033129 00000 n 0000033257 00000 n 0000033352 00000 n 0000033479 00000 n 0000033638 00000 n 0000033765 00000 n 0000033924 00000 n 0000034052 00000 n 0000034156 00000 n 0000034283 00000 n 0000034384 00000 n 0000034512 00000 n 0000034625 00000 n 0000034753 00000 n 0000034848 00000 n 0000034967 00000 n 0000054634 00000 n 0000054762 00000 n 0000054798 00000 n 0000054926 00000 n 0000054962 00000 n 0000055090 00000 n 0000055126 00000 n 0000055254 00000 n 0000055290 00000 n 0000055418 00000 n 0000055454 00000 n 0000055582 00000 n 0000055618 00000 n 0000055683 00000 n 0000074753 00000 n 0000074851 00000 n 0000096645 00000 n 0000096773 00000 n 0000096809 00000 n 0000096937 00000 n 0000096973 00000 n 0000097101 00000 n 0000097137 00000 n 0000097202 00000 n 0000116725 00000 n 0000116844 00000 n 0000121777 00000 n 0000121903 00000 n 0000121985 00000 n 0000122111 00000 n 0000122219 00000 n 0000122345 00000 n 0000122427 00000 n 0000122553 00000 n 0000122661 00000 n 0000122787 00000 n 0000122869 00000 n 0000122995 00000 n trailer << /Size 91 /Root 1 0 R /Info 5 0 R >> startxref 123103 %%EOF