It likes adding stones to its own mancala the most and dislikes leaving captures open.If you are looking for an easy homemade board game to play with your family while using strategic thinking, then try this ancient mancala board game. The genetic algorithm was able to determine which factors were most important, which were good, and which were bad. The board was evaluated by multiplying each of these attributes by a learned weight then adding them all up. The number of stones I had added to my mancala for a given move, the number my opponent had added, the number of stones I and my opponent had each added to our six cups and the captures that were possible, either for me or for my opponent. In my case, my chromosomes encoded weights for each of several attributes relevant to a game of mancala. The steps of fitness testing and reproduction are repeated until some stopping condition. The chromosomes are combined and crossed over, then an element of random mutation is introduced to keep things from settling into ruts. Then, the most fit chromosomes are allowed to reproduce with one another, and reproduction is imitated. The first step of this is to encode the information you need in a “chromosome”-usually a binary string or, in my case, a string of constants.ĭetermining the fitness by playing other bots Genetic algorithms work off of principles of biology-reproduction, survival of the fittest, and genetic mutations.
I decided to let the bots learn for themselves what’s a good function or not, which is where the genetic algorithm comes in. Sure, having more pebbles in your mancala is better, but there are subtle things at play leading up to that outcome that I wasn’t sure of.
#Mancala tules how to#
The problem was that I don’t know much about mancala and how to evaluate the board to determine if it’s good or not. A board where the bot has won should have the highest possible value, a board where it has lost should have the lowest possible value. It takes in the board state and spits out a number that expresses how good or bad the board is. The function for evaluating the board state at any given time is called the heuristic function. That’s where the heuristic function comes in. Instead, there needs to be a way to evaluate how good the board is at any time and just try to get to a good place. That means that it’s incredibly expensive to try to look ahead to the end of the game and figure out how to get there. In mancala, though, there are 6 moves at any time and each move affects the remaining states of the game. In tic-tac-toe, there are at most 9 possible moves to be made at any given time, so it’s not unreasonable to examine all possible states of the game board. Minimax trees and AB pruning consider how good the board is for each player during their turn. The best move I consider is the only move the bot considers Here’s that example more visually (I’m X, the bot is O). How the bot thinksĪB pruning is a method of ignoring board states which will never occur (if the opponent also behaves like the bot).ĪB pruning assumes the following: if I’m playing a game of tic tac toe and there’s a move I can make that will make it possible for me to win, I will ignore all other moves so the bot making a decision can, too.
It recurses n levels then returns the move which will eventually produce the most desirable board state. The bot uses a minimax tree to select the next move, meaning it chooses the move that will produce the best outcome assuming the opponent will do the same. My goal was to build a mancala bot that could beat both me and other mancala bots. This project was for Northwestern’s EECS 348. Here’s a writeup of general techniques and results. I spent the past week goofing around with genetic algorithms to develop a heuristic for evaluating a mancala board for more successful move selection.
0 kommentar(er)
