Mancala: Multiway Analysis and Building a Game GUI in Wolfram Language

Okay, thank you everybody for coming. We have a whole hour for this presentation. I will take up every last microsecond of it, but there's fortunately nobody after us, so we can run over. I would like to hold questions until the end. It'll be easier to answer them that way, otherwise we will never get done tonight. So again, thank you. I'm Bob Nakbar. I'm a member of Wolfram Solutions, the consulting department in Wolfram research. I'm a longtime Mathematica user, going all the way back to version 1.1. And so for today I'll be talking about the Mancala game, also known as Kala, mostly looking at it from a multi way analysis perspective and also building a game GUI and Wolfram language to actually play the game. So let's begin. So you've all read the abstract, we'll go past that. So I'll have an introduction. I'll quickly run through how the game is played so that people can follow along the rest of the the presentation without being super lost. I will talk about how I made Mancala computable, talking about the game board, how we implemented the gameplay, the different types of rules, a little bit about random games. And then the meat of the talk is about studying all possible games for a given set of rules in a given game setup and generating game graphs and things like that. Then the results of all of that are how many different games, for example, are possible for a given setup. I'll talk about scores and wins. I'll talk about fairness, I'll talk about early win decidability, a little bit about perfect play. And then I will also talk about the multi way analysis that I've done on the Mon Cala game, mostly based on branchial graphs and a little bit about causal invariance. I'll quickly summarize the the results that I've, I've obtained about game complexity, game fairness and, and early wins. And then I will talk about the, the GUI that I built and we can actually play it a little bit better. We can play it at the end. Okay, so why did, why did I do this? A little bit of background. I'm an organic chemist by training and last year I gave a talk on chemical reaction networks. This is showing a biological chemical reaction network, how monoterpene molecules can be synthesized from a precursor molecule and all these different types of chemical structures can be derived from, from just a very small number of different types of chemical reactions that get used multiple times and produces this multi way system of the metabolism. Two years ago, one of my summer school students worked on a multi way analysis of the PEG solitaire game. And these are some of the multi way graphs that he was able to generate when he studied that, that game. Last year, Stephen wrote a huge blog post on games and puzzles in a multi way analysis. He did cover the PEG solitaire game along with a number of other games and puzzles. And that was a very interesting post. It's in the bibliography at the end if you want to take a look at it. And last summer, one of the Wolfram summer research program students looked at the Moncala game and this was the, the multi way graph that, that he had generated. It's only a partial graph. He was trying to study the full game board that's typically used. And so he sort of has had a partial analysis. And when I saw that this was the tipping point, that got me to look at the Mancala game more closely. And I quickly put together some code that let me play the game and study it. And that's what I'm going to be talking about today. Just a little history. This is the Kala board that I was given when I was about 12 years old. I still have, still have all the original seeds and everything. My kids played with it and it, you know, it was a lot of fun. These are the instructions on the back down at the bottom it says, you know, for more information, look at the little booklet that came along with it. Well, I don't know what happened to that booklet. It, it's gotten lost in the intervening time. So just quickly. Moncala is a two player game. It's been around for a very, very long time. The game that the board that I just showed is for the North American version known as Kala. Traditionally it consists of six pits each containing four seeds and a store for each user. If this is my side of the board here, this is my store. My opponent would be sitting across from me and this would be my opponent's store. And the idea is to take all the seeds from one pit and then sow them from one to the next around, including putting one in your store. If you have enough seeds to go all the way around you, you continue sewing in your opponent's pits, you skip your opponent's store, and then you continue sowing in your own. So that's basically the way the game is played. And it involves strategy and counting because you want to decide, you know, which pit do I take. If I take the, the seeds from, you know, one particular pit, where will the last one end up? Well, how many will I Be giving to my opponent while I be setting my opponent up to do something strategically advantageous for them or not. So that's what makes the game interesting and fun to play. So what if we could, you know, use the tools of multi computation to learn something new about the game? And I think I actually did, and I will into that later on. We could also study the consequences of different numbers of pits or seeds. I certainly can't do that with a traditional wooden board, but computationally we, we can do that. And then what if it's possible to force a win for one player or the other? You know, is that possible? You know, if I make a particular certain move very first, will that guarantee that I can win the game or not? And then once I got into this project, I discovered there were a number of other interesting questions, like could I play it interactively? And especially could I do it long distance via the cloud? For example, could I put a notebook up on the Wolfram cloud that has the interactive game in it and have somebody else also have access to that and we could play back and forth. And then also what if I could change the rules, use slightly different rule sets or, or eliminate one of the typical rules that are used? How does that change the game? And I've actually been able to. To take a look at that. So the game itself, so. Oh, I should have done that a moment ago. We had a little technical difficulties at the beginning and I forgot to initialize everything. So here we go. This is what the game looks like. This is the default setup. Six pits, a pit on my side, my opponent, six pits here and their store. And usually we. We put four seeds in each pit like this. I won't try to draw little dots for the pits. I'll just put the numbers there. It saves the users counting and it's easier to work with. And as I had said, the. Well, actually, I hadn't said. The objective to the game is to capture the most number of pits into my store. Once the seed ends up in a pit, it stays there, whether it's my store or my opponent's store. Once the seeds land there, they are out of play. And the object is to get as many of them as you can and. And certainly more than your opponent. The game is played by making different kinds of moves. As I had said, you select all the seeds from a given pit and then sew them around the board. So let's just do that here computationally. So with the initial board here, if I take all the seeds from Pit 3, which is this one here, I take them out. Now it's empty, and then I start sewing around the board. And so I put. The first one's going to go in pit four and then into pit five, and the last one's going to. And that's it. I had two, so that's the end of my turn. Now it's yellow's turn. So the board flips, and now yellow is at the bottom, and yellow can count its pits. 1, 2, 3, 4, 5, 6. And if the yellow then decides to take pit 5, that would be this one here. And they would sew. They take the seats out, they would sew one to pit six, one into their store, and then one more into my pit number one, and then their turn is over. And. And that's the basic play. When a player's last seed is sown into one of their pits that's empty, then they get to capture all the seeds in the opponent's pit directly across the board. So let's start with this board here. And if I take pit number four, which has two seeds in it, and then I start sowing, I sew into five, I sew into six. I'm directly. You know, that was empty. Now it has one in it. I capture my opponent's one seed and my seed, and they move into my store. So Now I have 22 there, and then my. My move is over. If your last seed lands in your own store, then. Then you get an extra turn. And we can do that here. If I choose pit one, which has six seeds in it, and I start sewing them, and the last one ends here in my store, it gets incremented by one, and then I get an extra turn, and I can then choose another pit and keep going. There is no limit to the number of extra turns one can take. Here's an example here where yellow chose the pit one, and then that was the play we just saw. They get another turn. Now I choose Pit 6, which would land in the store, and I get another turn. Then I can choose Pit 5 and so on, and I can get a very long string of. Of. Of turns. And then lastly, when I choose Pit 5, it lands in an empty pit. I capture that, and then that's the end of my turn, and the board turns, and now it's the blue player's turn. The game is over when all the seeds on one side of the board. Excuse me, when all the pits on one side of the board are empty. So, for example, here, if I am yellow and I choose pit two, I land in pit three, which was empty, I I capture my opponent's seed and mine. They move to my store. It's 32. This side is now completely empty and is over all the seeds that I have on my side. Any remaining seeds would then go to to my store. And now I have a total of 34 and the opponent blue has 14. When the one side goes empty, you might be moving your last seed from pit number six into your store or you could be ending up capturing as I had just done. So it doesn't matter which side is emptied, whether it's the one being played or not, but it that that ends the game. Okay, so how do we make it computable? All the code that I'm using is in the package the Mancala wl. It's available in the Wolfram Cloud and here is a link to it. Unfortunately I was not able to upload that to the Big Marker website. Only the notebook is there, but here's the link to it so you can get there. There are a few presentation features that are in the initialization section at the end of the of the presentation notebook. So the code is there for those. Okay, so the first thing to do then is to load the package so we can play and these are all the functions that are in the package that let me play the game. The main ones that I'm using are are multi way that plays the game. For a given board setup there is initialized board that makes an initial board determines the you get to give the number of pits, the number of seeds as inputs and it generates a board that then multi way will then use to play all possible all possible games and return the edges to a game graph. For that particular setup, the game graph function will take all those edges and produce a multi way graph coloring the edges by whose play it was possibly also adding which pit was played and then coloring the different vertices of the graph by which player has has won the game if the game passes through that that vertex and a few other functions here that, that are useful for, for handling the code. And also the. Let's see the Moncala GUI itself that we'll use to play the game at the end. Okay, so let's initialize a board so. Oh no, Why is that still blue? Okay, I don't know why I'm getting these messages, but initialized board did work. It. It produced a board. Oh, I know why. Hang on. I don't know why that cell didn't evaluate. So let's go back. Okay, so here we are. Okay, there okay, no messages now. We're great. Okay, so this is what the board looks like computationally. We've got Player 1's pits here in this list. Player 1's store is this number here. The whole first element of the list is essentially Player 1 side of the board on the right hand side. The second element has the second player's pits, and the second player's store is there. And the here's the information on the initialized board function. You can give it the number of pits and the number of seeds to use, and it's overloaded so that you can just call it and get the default of 6 and 4. Okay. We can display the board with a display board function. And the player that's playing is always shown at the bottom. And. We give it the expression for a board, which we did here, and it defaults to player one playing. And if we have names for the players, we can give a list of two names for that. For example, like this here. The board is completely configurable. We can have very small boards with one pit each, or very large boards with six pits. There's no limit to how big you want to make the board. We can have one seat in each pit to as many as four or more. I've just shown up to four, four here. This would be the traditional game over here. Six pits, four seeds. Okay. And we can make random boards. Okay, so here's a random board, and we could do it again and get a different one. And these would be useful for debugging, testing things like that. Or if you are trying to study a game whose setup is so large that we can't compute the game graph, you could, you know, for example, start, you know, use the random board to, to generate random boards to study different aspects of the game that way. And then here's the. The information on. On random board, again, overloaded. So you can give it no arguments. And you get. Get the default of 6 and 4. Okay. The game is played computationally by using a game state which consists of the board and the player whose turn it is and a play function. And I will describe the play function in just a little bit. So the game state looks like this. We've got the board for the first part of it here. And then the last element of the game state is the next player, in this case player number two. Okay, we have four different types of play. There's regular play, which includes all the rules that I described at the beginning. The, the capture rule and the extra turn rule, as well as just Sowing the seeds. We can play with just the capture rule and sowing seeds or just the extra turn rule and sowing the seeds or only sowing the seeds. When I first started looking at the multi way analysis of the mancala game, I was curious to know what effect the extra turn rule had on the game. And so I implemented that and I was just calling it simple play compared to regular play. And then I, you know, it, it became obvious that I really needed to look at both the playing with with the extra turn and not playing with capture and then playing by only sowing the seeds without capture and without extra turn. And it's been enlightening to see what those different types of play have have shown me about the game. So for example I can, let's see, we've defined the state here already with this state. And if I play with the regular rules and I choose Pit 5 which would be this one here, I would move there which would be a capture which means I, I capture the pit opposite from the my opponent. So we see that. Let's see. Oh yeah, okay. Yeah. So yeah, it was players player two's turn. So pit five for player two was this one here that is now empty. Pit six got incremented, their store got incremented and one more on my side got incremented and that was the end of my turn. And so you know the, the play regular takes really just a game state and the which pit you want to play. Okay, the different types of rules that we have for regular play we've got sewing, we've got the extra turn rule, we've got the capture and then the end of game rule. When one side of the board is empty, all the remaining seeds go to that player's store. The simpler games, simpler sets of rules that I just described, Capture play, extra turn play and so only play. Here's an example of what they look like. So with regular play this is doing essentially a random game. Pit 2 was chosen and then it's player yellow players turn, they chose pit three, uh, they got an extra turn, uh, and they chose one and then it was blue's turn and so on. With capture play the game proceeds this way slightly differently. With the extra turn play and the so play. So only play games tend to be longer because you're not capturing and removing seeds from the board as quickly. So these are some of the ways you can study the different plays. Random games are just that. We start out with one of the players going first and then randomly one of the the pits with Seeds in it is selected and that initiates the play. So for example, here I can make an initial board and then play the game. And this one actually has 57 different boards in it. And we can get a look at that, see what it looks like. Takes a moment to render all of that. And we start out here with a full board and we proceed down this way and then up here and down and each of the edges is labeled with the pit that was chosen. And then finally the final game, the final board is down here. And I can't quite read the score. It looks like blue, blue one. Okay, so studying all possible games. The complexity of the mancala is really big. This is the expression that will compute the number of possible game states, board states, if you will, given M pits and N seeds. And the traditional board is here, and it's got 13, quadrillion different ways you could distribute the seeds on the board and have a particular player being the next player. Not all of these states are reachable though in normal gameplay. So even though this is very large, not all of them are reached. Usually it's a small number, you know, single to a few percent of the possibilities are actually encountered in a typical game, but it's still a very large number. I mean, you know, 1% of 13, quadrillion is still a very large number of games. So the way we compute all the possible games, I used a recursive depth first search strategy. I used a data structure, a hash set data structure to keep track of the different game states that were visited, so that once one was visited, I didn't have to play any further from that and I could backtrack and then go on to other game states to play those. Each play is stored as a tagged directed edge. The tag that's used is the vertex is the pit that was chosen for the play. And in our analysis, a play is a single act of selecting a pit, sowing the seeds, possibly making a capture, and successive turns are considered separate plays. The whole collection of plays by a given player at one time is called a turn. And yeah, so just to clear that up, when I gave a preview of this talk last week, there were some questions from some of the people about that. So I just wanted to clear that up. Once we have all these edges, we can then construct a Wolfram language graph and visualize that and compute paths and things like that, path lengths, and study the game that way. So the multi way function is what is used to take an initial game state and then find all possible game states that can Be derived for that for a given set of rules. So let's make a very simple one. A two pit board with two seeds in each. Player one is going to go first. We can then use the multi way function and to find all of the derivative states from that. And I'm going to label all the edges with the move that was chosen, the pit that was chosen. So we can visualize that. So there are 23 different plays that were made. And the first one looks like this. Here's the directed edge. Pit number one was chosen. And so if we. Here's the state that we started with. This was the resulting state of choosing pit one. Pit one for player one is empty. Their second pit now has one more seed in it. And that's what an edge or a play looks like. We can then use the game graph function, which is basically the graph function taking all those edges. But it will color vertices by the winning player. It will color the edges by the player whose turn it was during that play. Some of those nice features can be turned off by using the performance goal function, which you know is very useful if you're just interested in computing the graph and then doing computations on the graph and not visualizing it when they're very, very large. So what do I mean by visualizing the graph? Let's make the game graph for the game we we just studied. It's a directed graph. Every edge, it goes in only one direction. This is the root at the top. This was the initial state. Choosing Pit 1 goes this way and ended up in an extra turn for the blue player, which they then took. I know it's blue because the edges are labeled with blue. And it ended up in this state here. And even though blue was playing yellow won the game, if player one took their second pit instead, they would have finished their turn and then yellow would have had a turn and so on. Down the tree, down the game graph, there are 1, 2, 3, 4, what I'm calling leaves. These are vertices with zero out degree. They don't have any edges emanating from them. They are sinks and they are states at which the game ended. There was this one here was a win for the yellow player, this was a win for the blue player, another win for the yellow player. And this last one here was a draw or a tie. We can put the game boards on the graph by using the vertex shape function, which is very handy, and we can actually see how the play went. So if we chose pit one, that was this one here, it landed in their store they get an extra turn, as I had mentioned. And then they have only one pit to choose from, which is this one. They would play there, there and there. Their side is empty and so that ends the game. But because they had left so many seeds here on the yellow side, they all went to yellow and the yellow ended up winning even though blue was the. The player that played first and, and emptied their side. And you can see how the, the different games went. Okay, I had mentioned the root. The root is the vertex whose in degree is zero, no edges coming into it. And that's the initial game state. The leaves are the vertices that have a zero out degree. And we had four of them. As I had mentioned, all the paths from the root to all of the leaves are possible games. So we had four leaves. The first one had just one path to it. The other four leaves had two paths leading into it for a total of seven games. And we can show those on the graph. And let's see, there are. Yeah, so we had seven distinct. Seven distinct games. If I look at all those paths, the shortest game had three. Three game states in that path or two edges. So the shortest game was just two moves. The longest game had seven moves. And then we can look at those on the graph. So here's the short game. Here are two games that ended up as a win for yellow. They ended up there. Here are the two games that blue won. And then there were two games that ended up as a draw. We can get the scores from the paths by taking the last board and looking at the scores from them. And these were the scores. The blue score, the first player score is always first. So the blue lost this one, lost that one lost that one won this game, won that game. And here are two draws. And so we can also summarize it this way just by finding the differences and collecting them together. Okay, so we enumerated lots of different games. I tried to look at different board setups from one to six pits with one to six seeds in them. I was not able to compute all of them because of limited computing resources. Essentially being memory bound, being able to to store all of those edges in memory to. Before I had finished traversing the game graph, I studied four different sets of rules. The regular play, capture play, extra turn play, and the so only play. I did not employ any strategies to winnow the possibilities to only advantageous moves. We are effectively doing a zero depth perception of the graph. We were looking at all possible ways the game could have been played, essentially using a random strategy as it Were for each of the game graphs. I tabulated the number of vertices, a number of edges, the number of leaves. I looked at the number of paths or games. The number of games is much, much larger than just the number of edges. And so I was not able to compute all of the games from the game graphs that I was able to compute again because of memory limitations. I also looked at the path length distribution, not just, you know, what was the shortest game or the longest game, but how many of each length did I have. And some interesting results there. And I also looked at the score distribution and the wind tie loss distribution, trying to understand how how the mancala game works out. So here are the results for a very simple setup with two pits and two seeds with the different types of gameplay. These are the types of multi way graphs that one can get. This is the one that we saw here already. For regular play, if I take away the extra turn rule and use only the capture play and the sowing, this is the multi way graph, that one gets a little bit different. If I take away the capture play and use only the extra turn rule, I have that. And if I take away the both the capture and the extra turn rules and only sow seeds, this is what I get here. If I add another seed to it, in other words two pits and three seeds, the game graphs get quite a bit more complicated and of course the games then get more interesting and the games are actually longer as well. And alternatively if I add another pit, three pits with just two seeds, it gets quite a bit more complex and of course more interesting for the players. We can already get a little bit of intuition about what's happening. The capture play which is used here and in the regular play we can see shortens the game quite a bit. Many fewer layers here because we're removing seeds from the board faster. The extra turn play, which would be the difference between these two graphs and these two graphs is subtle and it's not clear from looking at the multi way graphs by themselves exactly what's going on. But the multi way analysis that I'll get to later actually gave me a little insight into that which I'll share with you then. So the game game graph size. I'll go through these results very quickly. I've got everything tabulated here. So only play the games were fairly large. I was not able to compute all of them. And in regular play here the games were a little bit smaller, but still quite a few. The largest game graph I had was this one here with 106 million edges in it. I've also tabulated in here the, besides the number of vertices and edges, the number of leaves ending game states that we had, and the percentage of the total board and player state space that was visited by the given setup with a given set of rules. As you can see, it's fairly small, you know, down only, you know, single digits percent for some of the larger games. We can also look at it this way to get an idea of what's happening. The growth of the complexity is as polynomial in the number of seeds. So here I'm showing along the x axis the total number of seeds, which is the number of pits times the number of seeds. And each curve represents whether I've got one pit, two pits, three pits, four pits, five pits and six pits. And we can see that it's a curve that has negative curvature, which in a log plot means it's essentially polynomial. Whereas if we look at the same data now, but by the number of seeds, here's all the games with one seed with 2, 3, 4, 5, 6, they're essentially linear, which means it's exponential in the, the number of pits. We can look at the same data this way as, as a 3D surface in the number of pits and the number of seeds. Again, this is on a log scale. Alternatively, we can look at it as, as bar charts. It's not that these setups, six pits with 2, 3, 4, 5 or 6 seeds had zero, it's that they were not computable on the hardware that I had. Okay, so we can also look at the number of games and the number of plays in the games. So the number of different games or the paths, I could compute fewer of those for the game graphs that I did have. And we can see that the number of games gets quite large very quickly. 100, 106 million here for. So play with the same setup, but with extra turn play is, is a little bit smaller and so on. With capture play here at 148 million different games, the I'm also tabulating the shortest and the longest games. So you can see the games can be quite short if one of the players makes a fatal first move and the, the other player can then take advantage of that. And some of them are, are quite long. The number of games that can be played is essentially exponential in the, in the number of seeds and it's super exponential in the number of pits. It's much easier seen here that these are more or less linear for increasing numbers of seeds within the pits and then increasing the number of Pits makes these on a log plot have positive curvature. So they're super exponential. And again, these are other visualizations here. The 3D service plot shows how these rise in number of games increases very rapidly. And here is the bar chart of the same data. Okay. Looking at scores and wins. These histograms or bar charts show the actual scores. You can read them off and it for example here player one had one, one seed. Player two had had three seeds. So player three won the game here. This was their, their final score. So they're colored by who wins the game. Ties are, are white and. Stop that. Okay, we can see that the, the distribution of scores is somewhat symmetrical around ties. And looking at this, it looks like blue tends to win a little bit more often here things are a little more even and so on. So one could go through all of these numbers and tabulate them to see who wins more often or not. There's an interesting case here with two pits and five seeds where the blue player wins nearly all the games. And if we take away the extra turn play, the blue player wins all the games. And then lastly, there was only one game that I encountered where one player captured all the seeds and that was playing with one pit and three seeds. The the blue player ends up catch capturing everything. We can also look at the number of wins, number of losses and ties. And, and that's shown here. So and for regular play it looks like this, the number of ties is, is fairly high, but is often less than either player actually winning. Okay, I looked at fairness and what one, what we could can do is for each winning game state is assign a value of plus or minus one to that state, plus one meaning player one won the game, minus one meaning player two won that game. And then propagate that value up the game graph by averaging the scores. You know, the, the of, of the fairness at one level up to the next level. And so when I do that here, for example, we can take this, the, the game here that we looked at early on, this was a win for player two. And so going up this way, there's only one way, one edge feeding back into to this vertex. So it's also a full negative one or fully red. And so is this one here. Whereas if we look at this one, this game state, it has two states that derive from it a tie and a win for player two. So its score is going to be, its fairness is going to be minus one half. And this one here was a win for one and minus one half here. So it's Slightly on the positive side. And we can work this all the way back up to the root node. And so for these four different types of play, for the two pit two seed setup, we can see that for so only play, there's a slight Advantage to Player 2. A slight advantage. A little bit stronger advantage for player two with extra turn play. With capture play, player one has the advantage. And for regular play, player two has the advantage. We can tabulate these fairnesses for the root vertex across all the different game states and the different types of play. And this is what the fairness looks like for that some of them are fair. The smaller games tend to be very biased to one player or the other. But as the games get larger, the fairness ends up being much closer to zero. So it's for random play. Then the you know, the odds are fairly even as to which player wins more often than the other. Look at these same results in a histogram. This is for all of them. Since the games are very predetermined for a single pit with a different number of seeds, if we leave those out, we can see that the fairness is really all center very much around zero, being fairly even for the plot play. Okay, early wind decidability. There are a couple of different ways we can look at that. Looking at random play and looking at perfect play. In other words, if a player could look all the way down through the game graph and then make their choice of move based on which one was going to get them to a winning state, or if not a winning state, at least a tie, that would be perfect play. So I did not do an exhaustive analysis for random play on the decidability. But one thing that we can do is propagate the the win status if you will up the game tree with the color by outcome function. As I had mentioned before, when game graph generates the graph, besides coloring the edges by player, it colors the vertices by who won, you know which player won the game at that point based on the score. So obviously for the leaves the game is over and we know the final score and we can certainly color those. But if we look at the score at the different game states before we get to the end, if one of the players has more than half the seeds, then the the vertex can be colored by by that player and that's what game graph will do. And then if the the color can, you know, if there's only for a given state, if there's only one edge out of it, then it inherits the the. The the wind status of the of the descending the dependent vertex. So if we color that way, we can push the color up, and we can see that we now can color some additional vertices here based on what was the score status from the immediately following vertices here? This one we can't decide because this was a win and this was a tie. So with random play, it could have gone either way. And if we do this for larger game graphs, in this case, looking at three pits and two seeds and, and propagating the color upwards, we can still see that there's a very large number of game states where the game has not been decided. Very, you know, nearly half or, or more than half are undecided. A small number of ties can be picked out early. A little bit larger number of wins for player one or for player two. But with random play, you. You can't push that all the way back up to the top. Okay, for perfect play, we can use the, the vertex win status function to get the. The status in a computable way and then use that to color the vertices. And when we do that, we. Here was the game graph we had before using the win status function and then coloring things. It. It gives us this coloring here. So we can actually, if we played perfectly, even though, for example, at, at this point here, player two has a choice of going here or going here. This one here is more advantageous because they win. This was a tie. So player two in perfect play would have chosen this one. At this point here, it's player one's turn. They would have chosen this vertex because it would have led. Would lead to a win for player one. And we can work our way backwards up there. This is player two's turn. They don't have any choice but to go here, which would be a win for player one. But player two actually could make a choice here where they would end up choosing this move here, which would have been advantageous for them, which would have eventually lead to a win. So with perfect play, player two can always guarantee a win with this particular setup. For some of the smaller game setups, I've tabulated this analysis here for all of them and the different plays that we can play. Here's the one that we've been looking at a lot already. And these results here are consistent with those reported by Donkers in their paper from 2000 or 2001. Okay, so that's, that's analyzing things with. With perfect play, they. When I showed you the, the wind distribution, it was interesting that there was a couple of very pathologic setups that Led to player one winning nearly all or all of them. And this is the game graph for that. And we can see that just by looking at the score. Player one has has won. Player one wins all but one state. And the scores are such that the the win status is is determined very early. The player one is capturing most of the seeds very early on. We can push that frontier all the way up to as high as we can with a color by outcome function which shows here that we can push it up almost to the top. And if Player 1 chooses their as their first play to choose Pit 1, they will have guaranteed a win for themselves. If they choose pit 2, then player 2 can actually win if they choose their their second pit which then gives them an extra turn. And if they choose their Pit 2 again, they end up winning. If they make a mistake and choose pit one, then it goes here and player one will then win in the end. So this was the only game setup that I found that that was very lopsided that way. If we take away the capture rule and use only the the extra turn play for the same game setup and look at that, it'll take just a little bit to compute that we're actually doing this computation live. I'm not pulling in the results that I had computed earlier and saved them. So some of the game graphs it takes hours to compute all of the edges. And we can see here that by removing the capture play, it very much changes the the nature of the play. For this board setup with five pits and two. Two pits and five seeds and the yellow, this player two can win a fair number of times, but it's. It's not determined until you're about halfway through the game. Okay, so the multi way analysis I looked at two aspects of multi way analysis. I looked at Branchiel graphs and causal invariance. The branchial graphs represent game states where a pair of game states immediately follow a common predecessor state. Essentially you know, a splitting of the possible paths. They provide insight into entanglement of of nearby paths or complexity or mixing of the the play. And it's been also carried described as characterizing the unpredictability of the play. I limited the analysis to to looking at branch of graphs down to 20 plays or 10 plays just for brevity. And if we look at the the so only play with two pits and one seed, one to six seeds. These are all the different games game graphs that are generated. And the branchial graphs look like this. For one seed, for two seeds, three seeds, four seeds, five seeds and Six seeds, not very interesting. Mostly just pairs of vertices being connected by an edge. A little bit of, little bit larger branchial graphs here, but not very much. If I look at two pits with one to six seeds, these are the game graphs and these are the branch graphs here again not, not very different. Not, not much mixing or unpredictability even for the the most number of seeds. If I increase the number of pits though, things get a little more, But still not very, still mostly just pairs of edges or small triangles. If I look at all possible all the plays with three, four, five and six pits, but with only one seed, we start to see a little more interesting behavior. Still fairly uncomplicated here with three pits. When I go to four pits though, and look at what happens with the branchial graphs, they're starting to branch out a little bit more. When I go to five pits then things do become more interesting. We're seeing much larger branchial graphs involving many more vertices. And when I include capture play, they, they get, they start to get even larger. And then when I go to six pits and do the same analysis, the extra turn play increases the complexity of the branchial graphs, they, they get much, much larger involving many more game states. When I get rid of the, the extra turn play, they, they get simpler again. And when I turn it include it back in again, we get the, the increased complexity. So this was the insight that I got from the multi way analysis about the, the effect of the, the extra turn rule, what it, what it's doing. Okay, so then very quickly the wrong button. So very quickly the game complexity, we can measure that by the size of the game graph and we looked at how the complexity grows with the number of seeds and pins pits. We can also measure the complexity by the number of games or the number of paths and see how that grows as the setup changes. We can also measure the complexity by the length of the game. The capture rule shortens games substantially, generally by about 1/3. So if we were a game without the capture play had 30 moves, typically if we include the capture play it goes down to about 20. And also we saw that the, the distributions of the path lengths were generally bell shaped and they did have quite a bit of variability. The coefficient of variation ranged from 15 to 85% over those that I could compute. And the average length of the game grows linearly in both the number of seeds and the number of pits. Yet another measure of complexity, although it's qualitative, is the character of the branchial graphs that we had just looked at just a few minutes ago. And the extra turn play greatly increases the mixing or unpredictability of games when you get more than five pits. Okay, fairness. Generally things are fairly even. There's a, a slight favor toward the second player for the most part. We saw with random play the, the first player wins more often. See and yeah, okay. Early wind decide ability. Perfect play does not always necessarily allow the first player to win or draw. We saw cases where or player two would be able to do that. Okay, the interactive gui, we're a little bit over but this shouldn't take too long so I will thank you ahead of time for your patience. And then when we're done, I will take a look at the questions and try to answer as many as I can. Okay, so looking at the in building an interactive gui, interestingly the, the game boards that you were seeing were not done with graphics. It's all textual with textual elements using rows, grids and framed objects. The framed object has an option called rounding radius which makes things look like nice circles or nicely rounded lozenges. And here is the function that I use to make a pit. It's a framed object here. And here's the rounding radius. And with the appropriate rounding radius and image size they look like circles. I get to color the background by the player and so on. And so that's how I accomplished that. Doing the players stores is done essentially the same way with just a different image size to make it longer. Instead of being a circle, the board part of the game is putting all of the players pits into a row and then each side of the board into a grid. See? Yeah. So here's making the board, we make the player store and we've got the seeds already. And, and that's that. Okay. The row and that I just mentioned, the whole board is placed into a grid and then that is placed into a framed object. And then lastly I put that inside of a row with the players names on either side. If you want to see the details. That's all in the code in the display board function in in the package. Now to make the board dynamic we do two things. First of all, we need to make a finite state automaton that controls the game. And let's try clicking on that again. There we go. Okay, so the finite state automaton that controls the gameplay, we start here and we come into the setup where the user gets to choose the number of pits, the number of seeds, what colors they want to use, what type of gameplay they want to have, and what the players Names are and from there you go to a start state and that initiates the play. And then you play and play and play until the game is over. And then once the game is over you can play again with the same setup. You can recap the game, review all the moves, find out where you, you know, find out why you, you know, where, where the mistakes were that you made to let the opponent win. Or you could go to a new setup and choose another, you know, different number of pits or seeds and so on. From the recap you can go back and and play another game or go to another setup. The this finite state automaton is controlled with a switch statement. And this is the outline of the switch. We start with a setup state and based on the state we take a different branch of the switch. And then depending on what happens within that branch of the switch, the, the the state gets changed. And then because this is dynamic switch will re evaluate because state changed. It's one of the track symbols. And the board gets redrawn and the we, we get to go to the next state. Largely we, we end up playing, you know, inside the play state. To make the board dynamic, we need to turn the pits into buttons. And that's done just by using button. And we use the make pit function here to make the glyph for it its color and the number of seeds in it. And if the number of seeds is greater than zero, then it's a button. Otherwise we just display the, the static glyph. And this is the code here that will make the play. It knows which seed was picked, it knows the state of the board. It calls the play function, gives it the game board, the current player and the pit that was chosen and gets a new game board back and a new current player. And then the dynamic that's wrapped around the switch sees that and then decides what to do if the game is over. It goes to the end of game state and so on or it continues in the play state. So to demonstrate we can actually play the game. And this is the interface for doesn't display very large with the style sheet for the, the presenter tools. Let's just make it a very short game. We'll choose two seeds and three pits and we'll use regular play. And I'll just take the defaults of me and you for the players and the colors. There are a number of different colors you can choose from to make it interesting. And then so we start with our play and I can choose pit two here. And that was the end of My turn. I distributed one here and one here and one here. And now it's your turn and, and you can play. Let's say you choose that one and then I choose here. I get an extra turn. I get to choose again. Even though it was the only pit that had seeds on my side, it didn't empty my side. I still have one here that's left. Now it's your turn and if you're smart, you'll choose this pit here, keeping this seed on your side, forcing me to make the last move. If I choose this pit here, I'll distribute all the way around and then I will have more than one choice to make. So we'll make the smart move here and then I'm forced to make only this last move here. I will be emptying my side. I will have four. These pits here will be left stranded and they will then get moved into your your store and you'll end up with eight. So if I make that move, here's the final game. You've got eight, I've got four and you won. I can recap the game. So here are all the different boards that we went through and who was the player and what pit was chosen. So you can review the game if you would like to. Or we can go and play again. Or we can reset and play again. I was not able to get this to work in the Wolfram Cloud. Unfortunately not all the dynamic features are fully supported recorded there. So working in a notebook is just fine. Two players can play it if they have two different mice and take their turns and play accordingly with the buttons on the bottom. And with that I would like to thank you for your attention and I will entertain questions right now. So let's see. Oh, not too many. Yep. Okay, so let's see. Any good resources for multi way graphs? Yes, actually if we go to the back matter here, just a quick acknowledgments. Brad Klee was very helpful in discussions about multi way analysis, causal invariance, branchial graphs, modeling, perfect play, and computing fairness. He gave me all those ideas that I was able to implement there. David Rees is a dynamic maven and I mean it in the computational sense of dynamic. He really knows how dynamic works and gave me a number of pointers that improve the performance of the gui. And I would also like to thank the Wolfram Solutions department that provided lots of direct and indirect feedback during an early presentation. So to find out more about multi way analysis, looking at Stephen's Games, Puzzles and Multicomputational Systems blog Post that came out last year is very good. Here's the link to it. He wrote another post that just came out a few weeks ago on expression evaluation and fundamental physics. There's a lot of work about multi way analysis, branchial graphs, causal analysis and things like that in the physics project. So you can go to the website for the physics project and read a lot about it there. And it's an active area of study at the Wolfram Institute as well. Let's see. It says could the background the package file. Okay, I will check the permissions on that. It should have been public, so you should be able to download it. My email address is available in. In the website for the conference. If you still can't get it, send me an email request and I will email you a copy of the package. It's. It's relatively small, so it can be an attachment to an email very nicely. But I will check the permissions on that as soon as we get done. Um, a random symmetric board would be an interesting. Would be interesting as well. I assuming that it would be random on one side and then the other player, other player's side would have the same number of seeds in each of the pits. That's certainly one way that one could construct that. If I didn't get the right answer there or the answer you were looking for, let me know. The random board function actually plays a random game and then picks one of the boards from that game randomly. That way you're guaranteed that for a given type of play, for the rules you're using and the board setup, you're getting a board that is reachable by legitimate play rather than just an arbitrary pigeonholing of all of the seeds in all into all of the pits and stores. So that's the way the random board works. Why didn't I use an association as my hash set? Association is fast, but. But hash set is even faster. And since I'm computing game trees with millions of vertices, the memory requirements for an association would have been much, much larger than a hash set. So that's why I use the hash set data structure. Have I tried implementing a computer enemy for this? I'm not quite sure what they mean by a computer enemy. Since the rules are so simple, I'd love to see a reinforcement learning approach for tackling this. Also, would I be able to win against you or does your experience kill every chance I have? No, you will not kill every chance you have if you play against me. I play games relatively naively. I look one or two levels deep the last game we played there, I really only looked one level deep at the last game that the last play there. I find it more interesting to, to play that way than trying to puzzle it all the way through so that I can be, you know, dominate my opponent and win every game. But it has been suggested to try to teach an LLM how to play and have an LLM play against itself or against a human player. But no, I, I've not tried to, to implement any kind of strategy. I, I want to keep my playing with my grandkids still fun and fair. Let's see, somebody's intuition is that not only 2 pits, 5 seeds, but any capture game with n pits and 2n plus seeds would be highly advantageous to the first player. That is a hypothesis that we could test computationally. And with the package you should be fully prepared to do that. Try to do three pits with seven seeds according to this formula here might not be computable with your available memory and hardware. So we, you know, we might have to change the way things are done. Instead of trying to keep all the edges in computer memory in the ram, we could write them to disk, for example, and use the disk for storage. You know, that's a possibility there. Let's see, a couple more questions have, let's see. Maybe I said at the beginning, but why did you choose Mancala over other tabletop games like Go? I chose Mancala because I had seen the Wolfram Research summer program student use it for their project. I had played the game in the past and we surprisingly had just recently given a game to our grandkids to play with. And I thought, oh, this would be fun to do. And I, like I said, I have an interest in networks and multi way analyses and that's why I chose Moncala to look at. I've not played Go in the past, so I'm not that familiar with it. Whereas I had played Kala on that wooden board many, many times with my brothers and sister and with the game we gave to my grandkids, we played that one, as, you know, a lot as well. So that, that's why I went with Mancala. Let's see. And then the last question. Hope you might consider a function repository or a packet repository entry for the package. It would have to be a packlet repository entry, the function repository. I would have to write several functions because you know, a function repository entry is just a, a single function where a packet would let me. A packlet would let me make all of the functions in the package available. That's something that could be done. It will take a little while to write all the documentation to go with it, but that's something, you know, I I just not considered that this is more of a fun project rather than something that a more more earnest one like my compartmental modeling Packlet that was a has been a several year effort bringing that code to the stage that it is and getting it submitted to the Packlet repository a year and a half ago. So that looks like all of the questions and somebody has kindly been ticking them off as I answered them for me. Thank you very much for the the house elf in the background. If there are no more questions, I will let everybody go to their dinners. And thank you again for your attention for your questions. If you do play with a game, you have suggestions for me, I'd be more than happy to to answer them. And it's an active area. In fact, today I I tried another rule set. I had a hypothesis that the so only game would be causally invariant, that there would only be one final game state. And that's not the case for any of the rules sets that I've described today. And then quickly this morning I modified the end of game rule so that not just one side being empty, end of the game both sides have to be empty and rule continues so that whichever side has seeds gets to play. If it's your side that's empty, you you have to skip a play and it's your opponent's turn next. I got that implemented this morning in between the different talks and even with that setup, the the so only strategy is is still not causally invariant. There are still a number of different possible ways the game can end. And it is has become quite obvious to me that the order in which you make your plays is very important and can substantially change the final game from a win to you to a loss or a tie. So that that's one more learning that I got today before I give my presentation. So again that's very I'm getting long winded again. So enough and I hope you enjoy the rest of the the tech conference tomorrow and Friday. I will be around. I'll try to join some of the networking sessions. If you've got questions you can buttonhole me there or email me. My email address is available in the attendees section of the website. So again thank you everybody and it's been a pleasure.