Introduction

Oware is a count-and-capture board game of the Mancala family, which is played on a flat surface (typically a wooden plank) with 12 pits and 48 seeds. At the beginning of a game each pit contains four seeds. The twelve pits on the surface are laid out in two rows of six pits per row. These rows are named the “North" and “South" rows. These pits represent the areas that both players control respectively.

Oware is believed to have evolved in Ethiopia about 3,500 years ago (Climent, Canal, and Casanovas n.d.). Around the world, oware is known by different names such as: Ayo, Awale, Adji-Boto and Warri (The Oware Soceity n.d.; Climent, Canal, and Casanovas n.d.). Just as there are many names for oware, there are also may rules by which it is played. Rules are usually agreed upon at the commencement of a game. To make moves in oware, players collect the seeds in a pit which they control and distribute them into other pits in a counter-clockwise direction. The fashion in which this distribution occurs is determined the by the agreed rules in play.

Being a count and capture game, oware posses a style of gameplay which is calculatory and combinatorial in nature. This property has made oware a good candidate for mathematical analysis and artificial intelligence research (Davis and Kendall 2002; Rijswijck 2002; Daoud et al. 2004; Romein and Bal 2003).

Oware can be classified as a two player, zero-sum game of perfect information without any chance elements. In a zero sum game, the gain of one player is the loss of the other (De Bruin and Pijls 1996). Much of the work that has gone into oware game playing is based on work that has earlier been applied to other similar zero-sum games like chess or checkers. The later mentioned games have received more research attention over the years.

A couple of notable artificial oware players have been created. “Lithindon" was an artificial oware player that made use of endgame databases combined with alpha-beta search (Meulen, Allis, and Herik 1990). “Marvin" was another artificial player that used a hybrid method called drop-out expansion which mixes depth-first and breadth-first search techniques to construct opening books (Lincke 2001). “Ayo" was also another artificial player which used a shallow minimax search with an evaluation function which was tuned by a genetic algorithm (Daoud et al. 2004). In fact, with the assistance of intense computational resources, oware has been solved using parallel retrograde analysis (Romein and Bal 2003). The game tree was found to have a total of 889,063,398,406 states. It was also found out that if both players played optimally, the game always ended in a draw.

What is owarega.me?

Owarega.me is a multi-player implementation of oware intended to be played either on a mobile device or on a web browser. Apart from challenging other human players on the site, users can also play against the computer. It supports two different oware rule sets: “Abapa" and “Anan-Anan". ‘

‘Abapa’’ rules offer a much more complex game play which largely encourages the adoption of strategies in order to be better placed to win. Due to its complexity, “Abapa” happens to be the standard set of rules used in a wide variety of oware competitions (The Oware Soceity n.d.; Climent, Canal, and Casanovas n.d.). Also, much of the research performed on the game of oware, use the Abapa set of rules. “Anan-anan” on the other-hand features a simpler rule set which encourages faster game play.

To play a turn in Abapa, a player picks up the seeds in any of the pits under her control and goes ahead to distribute these seeds in a counter-clockwise direction around the board, until the seeds in the players hands are finished. When the last seed is dropped in a pit on the opponents side which contains one or two seeds, the player captures those seeds. If the pits preceding the captured pit also contain two or three seeds, the player captures those as well. In the case where the player picks up enough seeds to go round all the pits on the board, the player must skip the pit they originally picked the seeds from to start the distribution. There could be an instance when all the pits on the opponents side contain one or two seeds, the player can play a move to capture all the seeds on the opponents side. This is known as the “kroo” move or the “grand-slam” move (Climent, Canal, and Casanovas n.d.). The grand-slam move is quite controversial and it is disallowed in some cases (Sandler 2011). An “Abapa” game ends when one player captures more than 24 seeds. In that case the player with more seeds is the winner. It could also end in a draw when both players capture 24 seeds.

Anan-anan games also require the player to pick up seeds in one of the pits on her side for counter-clockwise distribution around the board. When the last seed is dropped into a pit which is not empty, or does not contain three seeds, the player is required to pick the seeds in the pit and continue distributing them until the last seed is dropped into an empty pit. In the case where the last seed is dropped into a pit containing three seeds (to make four seeds), the current player captures that pit irrespective of who owns the pit. Most other captures occur when a seed (which is not the last seed to be dropped) is dropped into a pit containing three seeds. In such a case the owner of the pit picks up the seeds. The game ends when one player captures more than 24 seeds. Given the recursive nature of the Anan-anan rules, it is sometimes possible for the game to hit a state where distribution continues indefinitely. In such cases the game ends and the winner becomes the one with the highest number of captured seeds.

Difficulty, Game Trees and Minimax Search

On owarega.me, users can challenge the computer at three difficulty levels: Abofra, which is the easiest, Abrantse, which is the intermediate, and Opanyin, which is the hardest. The computer’s game playing is performed with the minimax search algorithm. Given that the game is targeted to run offline on either a web browser or a mobile device, a database-search-backed artificial intelligence agent would not be feasible. This is primarily due to the memory constraints that such target environments have. On the other hand, game tree searching using the minimax algorithm might perform well at shallow search depths if a proper evaluation function is provided (Daoud et al. 2004; Davis and Kendall 2002).

Game trees are useful for evaluating two-player zero sum games of perfect information (De Bruin, Pijls, and Plaat 1994). The nodes of the game tree represent the state of the board, with the root node being the current state. Edges on the game tree represent possible legal moves a player could make at a particular node. Turns taken alternatively by both players are represented in the levels of the tree.

Game playing by owarega.me involves searching the game tree with the minimax algorithm to help decide on the best move to make. This algorithm provides a MAX player who plays to maximize its position of the game and a MIN player who plays to minimize its position of the game. Nodes on the tree are evaluated by an evaluation function which provides a value of the game at that node. For non-leaf nodes, the MAX player selects moves which maximizes its position whiles the MIN player selects moves which minimizes its position. This scheme is applied recursively to the game tree to a specific depth. The minimax algorithm can formally be represented as. The success of the minimax algorithm depends largely on how well the evaluation function represents the state of the game. It has been shown that good evaluation functions could be generated using evolutionary approaches (Davis and Kendall 2002; Daoud et al. 2004; Rijswijck 2002).

As part of efforts to develop an evaluation function without human intervention for the BamBam oware player, van Rijswijck proposed evolving an evaluation function by mining data from endgame databases using a genetic algorithm based approach (Rijswijck 2002). Davis and Kendall, generated an evaluation function by using a co-evolution approach(Davis and Kendall 2002). For their work they proposed a simple evaluation function, which was a sum of weighted values related to features in the game. The features they worked with were: the number of opponents pits vulnerable to having 2 or 3 seeds captured and the scores of the two players. Through a tournament selection process, they evolved an evaluation function, which performed well against the shareware Awale software with a search depth of 7 (Davis and Kendall 2002). Daoud et al. went ahead to show that by adding more features to the evaluation function, the depth of the search could be reduced without loss in performance (Daoud et al. 2004). For their work they extended the evaluation function used by Davis and Kendall by considered the range seeds in a given pit can travel as well as pits which were empty.

Methodology

For owarega.me, the evaluation function was evolved using an implementation of the approach proposed by David and Kendall along with the improvements made by Daoud et al. This evaluation function can formally be defined as.

where:

	The number of features available in the evaluation function.
..	The weights for the various features in the evaluation function.
..	The values of the various features for any given game state.

For the Abapa rules, 12 different features as proposed by Daoud et al. were used. See Table [tab:abfeatures] for these features.

Feature	Description	Feature	Description
	The number of pits that the user can use to capture 2 seeds.		The number of pits that the user can use to capture 3 seeds.
	The number of pits that owarega.me can use to capture 2 seeds.		The number of pits that owarega.me can use to capture 3 seeds.
	The number of pits on the user’s side with enough seeds to reach the owarega.me’s side.		The number of pits on owarega.me’s side with enough seeds to reach the user’s side.
	The number of pits with more than 12 seeds on the users’s side.		The number of pits with more than 12 seeds on owarega.me’s side.
	The user’s current score.		Owarega.me’s current score.
	The number of empty pits on the user’s side.		The number of empty pits on owarega.me’s side.

For the Anan-Anan rules, 14 different features closely related to those used in the “Abapa” rules were used. See Table [tab:aafeatures] for these features.

Feature	Description	Feature	Description
	The user’s current score.		Owarega.me’s current score.
	The number of pits on the user’s side that are vulnerable to be captured.		The number of pits owarega.me’s side that are vulnerable to be captured.
	The number of pits on the user’s side which capture more seeds for the user.		The number of pits on owarega.me’s side which capture more seeds for owarega.me.
	The number of pits with more than 12 seeds on the users’s side.		The number of pits with more than 12 seeds on owarega.me’s side.
	The number of pits on the user’s side which capture more seeds for owarega.me.		The number of pits on owarega.me’s side which capture more seeds for the user.
	The number of empty pits on the user’s side.		The number of empty pits on owarega.me’s side.
	The number of pits on the user’s side with 3 seeds.		The number of pits on owarega.me’s side with 3 seeds.

Weights of the features of the evaluation function were unknown, and a genetic algorithm was employed to find them. Chromosomes for the generic algorithm were represented as value encoded strings with real number values. For each of the rule sets(Abapa or Anan-Anan), the genetic algorithm started with a population of 20 players. Each of these players had the weights () of their evaluation functions initialized with random values between . Players then took turns playing each other twice; once as “North” and once as “South”. A player that won a game was assigned a score of 3 and players that drew a game were assigned scores of 1. A player that lost a game received no score. After a round of play, the top 5 players are selected into the elitism set and the rest of the players are crossed and mutated to generate 15 new players. A uniform crossover technique was used in generating new offspring; mutation was performed by adding or subtracting a random number whose value is less than 5% the value of the feature. This process was repeated for 250 generations. After the entire run, the evaluation function for the player with the best score was chosen as the final evaluation function.

In line with the evaluation approach used bye Davis and Kendal and Daoud et al., the evolved player was tested against the freeware Awale software(Myriad Software 2013).

Results

The genetic algorithm was run with minimax at depths of 3 and 5 for the both the Abapa and Anan-anan rule sets. The two depths were intended to represent the two hardest difficulty levels of the game. Tables 1 and 2 show the weights that were evolved at a search depth of 5 and 3 for Abapa rules respectively. Tables 3 and 4 also show the weights that were evolved at a search depth of 5 and 3 for Anan-Anan rules respectively.

Using Abapa Rules

The weights evolved for the Abapa rules at a search depth of 5 showed that, the evolved player placed the most emphasis on its current score. It also displayed an offensive strategy; with higher weights for pits having enough seeds to reach the opponent. Similarly, there were higher weights for pits that could be used to capture seeds from the opponent. The least weights were assigned to the opponents pits which could capture seeds and the opponent’s score.

At a search depth of 3, the evolved player still placed emphasis on its current score. It also evolved higher weights for pits that can capture 2 seeds and pits that have enough seeds to reach the opponent. Also, at this depth, the least weights were assigned to the opponents pits which could capture 2 seeds and the opponent’s current score.

By having a lot of weight on pits with enough seeds to reach the opponent, the evolved player at both search depths showed the tendency to take advantange of the “kroo” move.

To evaluate owarega.me’s Abapa rules performace at its hardest level of difficulty, it was matched against the freeware Awale game. Awale provides four difficulty levels: Initiation, Beginner, Amateur and Grand Master. owarega.me was able to beat Awale at the Initiation, Beginner and Amateur levels. At the Grand Master level however, owarega.me failed to match up to the Awale software. See the Tables 1 and 2 for the weights evolved at both depths respectively.

Using Anan Anan Rules

For Anan-Anan rules, the algorithm was also run with minimax at depths of 3 and 5. At a depth of 5, the evolved player showed an attacking style of play by placing a lot of weight on: its pits with three seeds, its current score and the opponent’s pits that lose seeds. The least weights were placed to the opponents vulnerable pits and the opponents pits that have three seeds.

At a search depth of 3, the evolved player placed extremely huge emphasis on: its current score, the vulnerable pits of the opponent and its pits that capture more seeds in a round.

Evaluation of the owarega.me’ Anan-Anan performance at its hardest difficulty, was once again performed against the freeware Awale game. Awale posses the multi rule feature which makes it able to play Anan-Anan. It however calls the Anan-Anan rule “oware”. Just as with the abapa rules, owarega.me managed to beat Awale at only three of its difficulty levels. These were the Initiation, Beginner, Amateur and Grand Master levels. See the Tables 3 and 4 for the weights evolved at both depths respectively.

Conclusion

The main aim of performing this work was to implement an artificial intelligence player with techniques based on existing research for the owarega.me site. The approach taken was based primarily on the work of Davis and Kendall(Davis and Kendall 2002) and Daoud et al. (Daoud et al. 2004), who evolved players using co-evolution approaches and genetic algorithms. The player for owarega.me was succesfully implemented and tested against the freeware version of the “Awale” software. The performance of owarega.me against Awale proved to be close to those achieved by Davis and Kendal and Daoud et al.

Future Work

If future patronage of owarega.me should be high amongst human players, an Elo rating system could be developed to rank the various human players against each other. Games played between the best players (according to rankings), and the computer could be used as a good basis for assessing the computer’s performance against the human population that are likely to play against it.

References