WIXLIB

Win%SecondMoveAvg StonesAvg MarginWin MarginLoss MarginAvg CapturesAvg GoAgainsAvg Moves//Win Percentage Going Second for both players//Average number of stones in Mancala at end (both)//Average stone margin in Mancalas for both players//Average Win Margin for both players//Average Loss Margin for both players//Average number of captures per game (both)//Average number of go-agains per game (both)//Average number of total moves per game (both)B. Searching and StateSearchingMini-max and Alpha-Beta pruning methods of traversing and searching the state space wereincorporated. We first developed Mini-max as our searching technique with a basic heuristicbeing the most stones in our home bin. As we incorporated the look-ahead depth, we noticedthat Mini-max was taking a substantial amount of time ( 20 seconds) to pick a move with lookaheads larger than 10. As the look-ahead increased, it was observed that the computation timeinvolved in expanding the search space increased nearly exponentially. As a result, Alpha-Betapruning was used to reduce this computation time by ignoring parts of the game tree that did notimprove on the current best found move, making it a more efficient overall search. Afterimplementation, we noticed immediate results. Thus, the searching technique employed in oursolutions is Alpha-Beta pruning using Mini-max as the base. Below is a brief description ofthese two techniques:Mini-maxA technique used to open up the search space for the game. This algorithm returns the best move given thebest utility at the end of a search depth. The move selected is based on the assumption that the opponent isusing the same set of heuristics.Alpha-Beta PruningA technique to reduce the number of nodes evaluated in the search tree by the above Mini-max algorithm.It stops completely evaluating a move that a player can make when at least one reply has been found thatproves the move to be worse than a previously examined move. Since it clearly doesn't benefit the player toplay that move, it need not be evaluated any further. This algorithm reduces computation timesignificantly, yet does not affect the search result in any way.As previously stated, we originally planned to incorporate the refining of our evaluationfunction. We envisioned this being done by evolving the evaluation function through “breeding”of the evaluation functions which are shown to perform the best. In essence, the weights foreach set of heuristics would be combined to form a new set of weights through “breeding”. Thenthe refining process continues until they converge on values.After reading papers on related approaches to the game, we realized that this would be anextremely difficult task requiring a substantial amount of time and work. Because of this, wedecided to omit the breeding of weights and keep it discrete for contribution of weights. Bydiscrete, we mean 0 for no use and 1 for entire use. There are no fuzzy values for the weights ofheuristics, and we left it as a good future addition to the work.5

To determine the move to make, the heuristics are applied and each returns a utility value thatrepresents how good that move is based on the current board configuration. By usingcombinations of heuristics, the utility values they return get summed to give the total utility of amove given that particular set of heuristics.6TotalUtility ( S k ) Weight ( H i ) * Utility ( H i )i 0To mimic human game play and to insure Computer players do not look far ahead into the game(to keep the Computer moves interesting and not predictable), we enforced a searchable depthlimit – say a 6 move look-ahead. This acts as a time-based approach in that Human playerscannot count the number of stones in each bin, making the move time-limit usually short. Byforcing Computer players to do this, it is giving us a “good enough, soon enough” result, andalso mimics how a human actually plays the game by only being able to look ahead a fewpossible moves. As will become apparent after viewing the results, with the exception of acouple odd cases, a larger look-ahead directly translates to more ending stones and thereforemore wins.StateThe state of the board was represented concisely as a 1D array with each player’s set of bins inregions of the array, along with the heuristic array, which move it is, and the statistics variables.Each node in the search/game tree was represented by the board state at that point, the depth ofthe node, the Mini-max move, and evaluation function information. This provided enoughinformation to efficiently evaluate states and compare heuristics.III. Testing & Development DifficultiesA. TestingTo perform the tournament-style and heuristic combinations comparison and testing, weemployed batch processing. Batching allowed many tests in an unattended environment, wherethe output was computed during program execution and printed out into a results file. Theoutput was formatted so as to allow us to simply copy and paste them into Microsoft Excel orOpen Office and immediately sort and generate graphs from the results. It also provided us witha very distinct way of evaluating if the games were being played correctly and if the searchingand heuristics were working as desired. There were many instances where viewing the statisticalresults told us exactly what was going wrong, allowing an easy fix.Other forms of testing were by using the Computer vs. Human GUI mode of the software. Thiswould allow us to make certain moves and see if the heuristic that we were playing againstwould actually pick the move that its function told it to (the one giving it the best utility). TheGUI version was also a key aspect in testing and gave us an opportunity to visualize the movesas they took place, along with the sequence of moves performed by each player for the entiregame.It should be noted that we implemented and tested the usual variation of the game: 4 startingstones per bin with 6 bins on each side (in addition to the single home bin per player). Anotherfactor/variable could have been to increase the number of starting stones per bin from 4 to, say,6

6. Although the moves would be different, the heuristic calculations might return differentnumbers, but all in all we would expect extremely similar results. We feel like that variablewould not increase what we would find out about the game itself or the heuristics we chose toanalyze. Thus, we left this as future work that could be done on this project. Both theLinux/batch and Windows/GUI versions implement it so that it is easy to change. In the GUI,this option is actually implemented so you can change the number of starting stones per bin viathe Options dialog box. For the scope of this project, we felt like this would have been overkillbut left it implemented in the GUI version so that anyone who feels intrigued could change thenumber and play the game to see how the heuristics perform with a different starting number ofstones.B. Problems EncounteredWe ran into design decisions on how to represent board state, and therefore changed not only ourboard representation but also our entire state representation scheme a couple of times. With asoftware project increasing in size involving multiple team members, small changes in the codebecame less apparent as development progressed. Without the use of a version control system,sharing the most updated copy of the code became a challenge at times.Early in Mini-max development, we discovered that we were thinking about the utilities in thewrong manner. We were initially not trying to maximize our utility and minimize the opponent’sutility, but were instead looking at the board from the wrong perspective when deciding onmoves. After some discussion this was resolved so that each agent analyzed the board usingtheir own point-of-view/perspective.In addition to the time complexity of a search depth and the Mini-max-to-Alpha-Betaperformance improvement, most of the troubles were associated with getting Mini-maxoriginally working correctly. Slowly stepping through the program and debugging allowed us tofind out what the problems were and fix them accordingly.IV. Statistical and Game Play ResultsA. Explanation of ResultsAs previously described, one configuration in the batch file represented the AI Computer playerbeing given a set of heuristics and look-aheads to use during the set of games playing first thenplaying second. The Random player simply chose a random, valid move for each of its movesand therefore had no special heuristic or intelligence. By using a Random player, it allowed usto compare heuristics and combinations of them against each other based on how they performedagainst the Random player in 100 games starting first and 100 starting second. We ran this manygames so that it would give the percentages a chance to level out and converge to a stableaverage.The other configuration in the batch file represented both AI Computer players being provided aset of heuristics and look-aheads to use during the set of games playing first then playing second.This did not use a Random player at all, but instead faced heuristics against each other to seehow they performed when going up against each other. In such a case, we didn’t need to runhundreds of games because they would play each other the same each game unless the lookahead values or heuristic arrays were changed.7

HeuristicsH0:H1:H2:H3:H4:H5:H6:Chooses first valid move (going left to right)(My Mancala – Opponent’s Mancala)How close I am to winningHow close my opponent is to winning# of stones close to my home (1/3)# of stones away from my home (1/3)# of stone in the middle (1/3)The following statistical results and analysis is not a self-proclaimed “solution” to the game, andwe are not stating that we have “figured out” the game of Mancala completely. There are manyother ways to analyze its heuristics and strategy. We chose a subset of the plethora of heuristicsfor the game: the ones we thought were most important and interesting. Although our analysisand results are quite thorough, there is potentially much more analysis to do to determine theoptimal way to play the game and which heuristics are the most beneficial in certain gamesituations. Keep this in mind when reading the following sections. See the later subsection onLook-ahead Analysis for the results of varying the look-ahead.B. Results for AI Computer vs. RandomThe results below reflect performance and statistics relating to all possible heuristiccombinations being played against the Random player. The analysis in this section will mostlyfocus on average statistics per move. Analyzing the data with respect to the opponent’s statisticscould not be done, due to the fact that the data for the player making random moves was nottracked. The average results on a per-move basis will show the characteristics of the AI duringeach move, uncovering the overall strategy of the AI. Once the average data per move is sorted,it will be apparent which combinations of heuristics result in the best strategies. This also servesto verify that the heuristics are performing their job correctly.Overall AnalysisThe following data was gathered from the raw analysis of P1 vs. Random (AI with heuristics vs.AI making random moves) sorted by win percentage. Figure 1 contains the count of the numberof AI’s (Player 1’s) that used the particular heuristic with a particular percentage of winning.Figure 2 shows the same data, only this time the count of the number of AI’s who used theparticular heuristic is the percentage of AI’s who used the particular heuristic with a particularpercentage of winning.8

Figure 3 shows the data from Figure 1, exhibiting how more AI’s used a wide combination ofmany heuristics to result in a better winning percentage. In particular, it shows how H1(comparing one’s score with the opponent’s score) is a large contribution to winning since H1 isused more with AI players that performed well and not as much with AI’s that won less. H2(how close one is to winning) also contributes to success in the 98% and greater range with AI’slosing more who don’t use H2. H3 (how close one’s opponent is to winning) was a contributorto AI’s winning 95% of the time and above.H4, H5, and H6, heuristics which concentrate on the layout of the board, do contribute towinning success when combined with other heuristics, but left by themselves do not performvery well. In combinations by themselves, H4 performed the best; H5 with H6 was next, thenH4 with H5, H4 with H6, H6, H4 with H5 and H6, and finally H5.Figures 4 and 5 both depict charts gathered from Figure 2. Figure 4 shows, using cones, thepercentage of AI’s at each winning percent that used each heuristic. Figure 5 gives the sameresults at a different viewing angle. A full cone represents 100%, and no cone represents 0%.9

10

08750.656250.95875Win 0.9950.996250.99750.9987510.8Percent of AI's Using 9750.998751Figure 4: Percentage of AI's Using Heuristic At Win %H6H5H4HeuristicH3H2H1Win %Figure 5: Percentage of AI's Using Heuristic vs. Win %H6H4H5H3HeuristicH2H111H1H2H3H4H5H6

Figure 6 contains the data for sorted average stones per move. Figure 7 shows a simple chartexpressing the heuristics of each AI visually as a function of the average stones per move.Looking closely at H1 and H2, the chart shows that using one or the other or both results in amove which yields more stones on average compared to not using H1 or H2. The chart alsoshows that in order to have a good stone-per-move ratio one must use H1 if not using H2, and H2if not using H1. This is exactly what should be happening, as a player using H2 will attempt tofind the move which results in getting closest to winning (having one more than half the totalnumber of stones in the home bin). Similarly for H1, the player will look for the move whichputs itself farthest ahead of his opponent. This means that each move the player will be lookingfor the move which results in the largest gain. This is verified in the graph where the AI with thebest average stones per move is the AI that only used H2. The next best AI used a combinationof H1, H2, and H4. This makes sense in that the player used H2 and H1, which maximize theamount of stones in the home bin, but also H4, the move which results in a board configurationwith the most stones close to home. This could have possibly allowed the player to end the gameby clearing his side of the board, resulting in a final move which obtained a large amount ofstones. It also could have resulted in captures. It is also obvious that H3 does not play a largerole in average stones-per-move as it only relies on making moves which keep the opponentfrom obtaining stones in his or her home bin.12

Figure 8 contains the data for sorted average captures per move. The accompanying chart inFigure 9 shows the AI’s for each average capture per move. H1 and H2 are required to have ahigh rate of capture; this is a side effect of their definition, which is to find the move whichresults in the largest gain of stones for the player. One of the largest gains of stones is a capturemove. At a minimum a capture will result in two stones being placed into the player’s bin. Thedifference between Figure 7 and Figure 9 is that the AI’s which have the best average capturesper move factor in H4, H5, and H6. This is required since capturing requires that there be anempty bin on the player’s side of the board. By factoring in quantities of stones in its movedecision, it allows the player to open up areas of his side of the board, resulting in capturemoves. Using H4, H5, and H6 alone will not prove successful in capturing since searching usingonly those heuristics does not take into account obtaining any stones in his or her home bin. It isworth noting that H2 alone ranked in the top 15%, whereas H1 alone barely made the top third.For the upper 50% of the data, H3 required H2 and H4 to be successful.Figure 10 contains the go-again per move data for each AI, and Figure 11 is its visualrepresentation. By themselves, H1 performed the best, then H2, then H3—all being in the topthird of the results. H1 performs the best since it looks for moves which will result in thegreatest difference between the player and his opponent. Going again results in a minimum ofobtaining one stone with the possibility of obtaining another in the resulting turn, and thepossibility of setting up a series of moves for a capture. H1 is best at this since going againkeeps the opponent’s score the same, and any subsequent scoring only increases the utility valueof H1 at each node. H2 does not find as many moves which allow it to go again because it relieson finding moves which result in the largest gain for the player without looking at the differencesbetween the players’ scores. H3 ranks well in this analysis since it looks at how to keep theopponent’s score as low as possible. One way to do this is to not let the opponent have amove—instead, go again! Another trend in the data is that H4 is not used as much as H5 or H6in the upper third of the data. This is because H3 keeps stones close to home. When stones areclose to home and there’s a lot of them or they’re in large piles, it is not possible to go againsince the last stone dropped will not be in the player’s home but somewhere far from it. A playerhas a better chance of going again (dropping the last stone in his or her home bin) if they pick upa large group of stones from the middle of the board or the one-third of the board farthest fromhome.Figures 12 and 13 correspond to the combined data of average captures plus average go-againsper move for each AI. One overwhelming consistency is the use of H1 or H2 or both in order toeffectively make a capture move or go again. Heuristics H4, H5, and H6 have no bearing on theupper 10% of the data. Alone, H1 and H2 rank very near the top and H3 falls just short of the50% mark. H3 however makes up, in combination with H1 and/or H2, nearly 75% of the top15%. Alone, H5 performs best since having your stones farthest from home would result in thegreatest possibility for a capture or a go-again. The majority of AI’s that used H4 fell in thelower 50% of the data since having stones close to home does not allow for many captures andalso not very many go-agains, unless the stones in the bin are in small numbers, which is why H4alone performs better than H6 which comes in second-to-last.13

14

15

16

17

18

19

20

C. Round-Robin Results for AI Computer vs. AI ComputerThe results below reflect performance and statistics relating to heuristic combinations beingplayed against other heuristic combinations. This is the round-robin portion of the results wherethe results below describe the tournament and games of it. It is not important, in this section, toperform analysis of average statistic per move,

An Artificial Intelligence Approach to Mancala Chris Gifford, James Bley, Dayo Ajayi, and Zach Thompson Electrical Engineering and Computer Science Department University of Kansas, Lawrence, KS 66045 Correspondence: cgifford@eecs.ku.edu I. Introduction The game of Mancala is a two-player strategy game whose objective is to collect the most