Hi! I'm Nithin Kannan, and this is my BASIS Scottsdale Senior Research Project blog. My work is going to be on studying how to balance a board game (and different variations) called nim between a skilled and unskilled player. But before I start talking about what I want to work on, I'll give a short introduction about me.
So I really like math. I like everything about math: competing in it, teaching it, and learning it. This trimester, for my Senior Research project, I'm going to be working at ASU Math Department for my project, attempting to research my problem and learn as much game theory as possible. As the weeks go by, I'll go through my general plan of attack for the problem.
Initially, I want to write programs for the problems in order to help me build my intuition. Seeing the computer spit out probabilities would allow for me to notice patterns in results. Then, given the results, I would attempt to prove mathematically (without a computer) patterns I noticed on the computer. For the math, I would need to simplify different recursive functions in order to better understand the system.
I've given a brief intro about me and I've sorta explained how I want to go about thinking about my problem. But now, I'm going to actually explain the problem, starting with the rules of nim.
Nim is a two player game, in which there are a fixed number of central stones and two players who are able to take up to a certain amount of stones from the central pile in alternating turns. To clarify what I'm saying, let's look at an example.
Consider a pile with 100 stones in the middle. Player 1 and Player 2 are able to remove between 1 and 4 stones in a turn. Player 1 and Player 2 continue to alternate on moves, trying not to be the first person unable to make a move. The player would be unable to make a move if there are no stones in the center.
This games initially seems complicated, but with a few games under your belt, you should be able to see a winning strategy. Both players want the pile to have a multiple of 5 (0 mod 5) stones after their turn at all times. This would mean that the opponent would never be able to take the last stone.
In the case we're looking at, if Player 1 took 3 stones on his first turn, Player 2, if playing ideally, would take 2 stones. Continually keeping the number of stones at a multiple of 5, Player 2 would be able to make the final move. The general winning strategy for nim is very similar to the one presented in this case. This means that nim has been perfectly solved. Given a board and a set of rules, we can tell immediately who will win.
For my Senior Research Project, I'm going to look at how we can make the game equally likely for each player to win given a skilled and unskilled player.
I'll introduce definitions of skilled and unskilled players, along with different variations of nim, in my next post. Hopefully I'll have a lot of math to tell you guys about too.
Thats all for now.
Thanks for reading.
:)
So I really like math. I like everything about math: competing in it, teaching it, and learning it. This trimester, for my Senior Research project, I'm going to be working at ASU Math Department for my project, attempting to research my problem and learn as much game theory as possible. As the weeks go by, I'll go through my general plan of attack for the problem.
Initially, I want to write programs for the problems in order to help me build my intuition. Seeing the computer spit out probabilities would allow for me to notice patterns in results. Then, given the results, I would attempt to prove mathematically (without a computer) patterns I noticed on the computer. For the math, I would need to simplify different recursive functions in order to better understand the system.
I've given a brief intro about me and I've sorta explained how I want to go about thinking about my problem. But now, I'm going to actually explain the problem, starting with the rules of nim.
Nim is a two player game, in which there are a fixed number of central stones and two players who are able to take up to a certain amount of stones from the central pile in alternating turns. To clarify what I'm saying, let's look at an example.
Consider a pile with 100 stones in the middle. Player 1 and Player 2 are able to remove between 1 and 4 stones in a turn. Player 1 and Player 2 continue to alternate on moves, trying not to be the first person unable to make a move. The player would be unable to make a move if there are no stones in the center.
This games initially seems complicated, but with a few games under your belt, you should be able to see a winning strategy. Both players want the pile to have a multiple of 5 (0 mod 5) stones after their turn at all times. This would mean that the opponent would never be able to take the last stone.
In the case we're looking at, if Player 1 took 3 stones on his first turn, Player 2, if playing ideally, would take 2 stones. Continually keeping the number of stones at a multiple of 5, Player 2 would be able to make the final move. The general winning strategy for nim is very similar to the one presented in this case. This means that nim has been perfectly solved. Given a board and a set of rules, we can tell immediately who will win.
For my Senior Research Project, I'm going to look at how we can make the game equally likely for each player to win given a skilled and unskilled player.
I'll introduce definitions of skilled and unskilled players, along with different variations of nim, in my next post. Hopefully I'll have a lot of math to tell you guys about too.
Thats all for now.
Thanks for reading.
:)
Do you think you might extend your research to other games, or will you focus entirely on nim? I'm curious as to how you could level the playing field, considering that it seems like there'd be no way for someone who doesn't know the multiple-of-5 strategy to win against someone who does know it.
ReplyDeleteActually something that's cool about nim is that it's mathematically equivalent to all other games without chance! This means games like chess are equivalent to a certain board on nim.
DeleteGreat question Rachel!
DeleteNithin, you do such a fantastic job explaining your project in a clear and understandable way. I look forward to checking in every week!
Pretty good introduction! Concerning your problem, I'm wondering how you plan to even the odds of winning, considering how certain it seems given the way you explained it. Would it require changing the rules, or simply employing a different strategy when playing?
ReplyDeleteSo actually that's what my project's on: finding out and analyzing different ways of winning. The first way I want to look at is by limiting the possible moves of the better player.
DeleteNice explanation of the game! What aspects would you change to make the odds of winning equally likely? Also, how exactly are recursive functions simplified?
ReplyDeleteSo recursive functions dont give me a probability directly. I need to plug complex recursive functions into my computer to get a result. Having a simpler function would solve the problem by giving exact probabilities for winning in certain scenarios.
DeleteExcellent explanation Nithin! Crystal clear. I can't wait to see how far you get when you get to focus solely on your problem. I would love to see some diagrams of the game so we could get a visual. :)
ReplyDelete