Friday, April 15, 2016

Lots of cool classes

Hello again!

I think this week is the last blog post which makes me very sad. I’ve really enjoyed these last 10 weeks doing research (and not attending school). It’s crazy to think that my time at BASIS has already come. But ok, I know what you’re thinking right now. Where is the math?

I have had quite the hectic week. Differential Geometry on Tuesday was difficult for me and I have not had any time to review.

Starting Wednesday, I left for my visit to Stanford. It has been really fun as I’ve been meeting up with all my friends here and sitting in on amazing math lectures. I’ll give a brief summary of the classes and what I learned in them.

Graph Theory: I had seen most of the material before in math class in ninth grade, but I learned a lot of cool theorems about Hamiltonian cycles ( paths that go through every vertex exactly once in a graph) and their relationship with the degree ( the number of edges attached) of vertices. Graph theory has a lot of cool applications in social networking and computer science as well for those interested!

Abstract Algebra: I had already seen all the material before (thanks to Ms. Bailey), but the lecture was nice. It focused on relations (homomorphisms) between mathematical objects called groups.

Algorithms: Technically this is a computer science class but it’s actually a math class. I learnt about different sorting algorithms and compared their worst case times. I learnt about Big-O and Big-Omega notation which would actually end up helping for my next class.

Analytic Number Theory: After feeling good about understanding the previous three lectures well, I (stupidly) decided to attend a much more difficult class. This class was hard. I understood sentences and bits of proofs, but for the most part I was very lost. Apparently math uses Big-O and Big-Omega notation as well.

Representation Theory: I normally would not understand anything in this class, since it has a lot of prerequisites. However, luckily for me, today was the first day of category theory. I now (2 years after category theory) know the definition of a category. Things Ms. Bailey said way back when make sense now.

All these classes were really cool  (even the ones I did not understand) so feel free to ask me if you want to know anything about them.

As for nim, I’ve wrapped up and cleaned up my program. My equation is still ugly, but my result is somewhat neat. J
That’s all for now!


Thanks for reading~

Saturday, April 9, 2016

Inspiration from Science Fair

So this week at ASU was pretty standard. I'm falling a bit behind in differential geometry again. It looks like I gotta hit the books hard this weekend. We've been learning really cool and general theorems about surfaces like Isometries and the Theorema Egregium, which literally translates to " The Remarkable Theorem" (it is actually very cool). Surprisingly this week, there was a lot of computation in proving various theorems, which was something I had not seen too much of in Differential Geometry previously. The lecturer actually took time out of the lecture to tell us the importance of computation. A lot of the theorems we had this week, including the Theorema Egregium, had very computational proofs that ultimately led to a beautiful and abstract statement. This weekend really opened me up to the possibility that sometimes the ugly road in math can lead to the best results.

Another cool thing I did was visit the Arizona Science and Engineering fair this week. I got to see the cool high school projects, which as always were super awesome. I also got to see the middle schoolers and the lower schoolers from our school. Seeing the younger kids projects was cool, since I got to see how developed their creative thinking skills in math already are. I visited a lot of my friends from science fair last year and saw how they've been doing in life and research. The most interesting part, however, was seeing a friend (Abi) and his project. He worked on the secretary problem (https://en.wikipedia.org/wiki/Secretary_problem). Also Wikipedia is not very bad for math so its ok that I used a wikipedia link. In his paper, he tackled different variations of the secretary problem similarly to how I was solving different variations of nim. On his poster, he had fairly complicated looking recursive equations that allowed for picking the optimal secretary in certain cases. One neat trick he did, however, was to convert some of his summations into integrals. This not only made his equations look much less intimidating, but also gave some intuition in his equation. Another point he focused on was looking at the results as the number of candidates in his problem got larger.

I now have a couple of things that I want to try to do to my equations. Maybe this will give the nice results I've been looking for all this time. Maybe it wont ( like all the other things I've tried). I'll keep you updated with how my equations look next week.

Thanks for reading~

Monday, April 4, 2016

The Second Midterm

This week has been interesting at my Senior Research Project site. I spent most of my time studying for differential geometry instead of looking at nim since we had a midterm this week. For nim, this week, I primarily looked at trying to convert general theorems about impartial games into nim as well as trying to look at theorems about other games and how they would translate into nim. I had a lot of general hunches about different games, but proving things has been harder than I originally expected. With a lot of proofs I've attempted, the intuition for the general outline of the proof has been there, but I have been largely unsuccessful at converting these ideas into rigid proof-writing. Theorems such as the Sprague Grundy theorem that make statements of different games often dont provide very simple proofs. Rather than showing directly that a certain aspect of a game holds, the theorems use proofs like contradiction, induction, and casework. Some of the proofs also seem to follow a circuitous path only to get a nice proof at the end. Thats been nim research for me.

Now for most of the week, I have been frantically cramming differential geometry. After falling behind a bit in the past few weeks, I caught up this week and felt somewhat ready for the midterm. Thankfully, this was not actually for a grade. I took the practice midterm and was able to solve about three of the five problems. With the book, I could solve four of them. But one problem took me too long to solve. It wasn't too long, but it just had a proof that went in a direction that I never bothered to look at ( like all the game theory proofs I had been reading).

I kept studying for the midterm, thinking that I wasn't prepared. Suprisingly, the midterm went well (at least for my standards) and I got four of the five problems. The last problem seemed obvious from reading it and turned out to have a simple proof. I just overthought it.

So now I feel like I'm back on track (for real this time) with differential geometry. I've really enjoyed the college experience and schedule. It has taught me to manage my time better, study independently, and read higher level textbooks better. The class has definitely taught me skills I'll need in college next year.

As for nim... I'm a bit behind. I've hit a few roadblocks, but I'm ready to keep trying to solve some of the cool problems I have.

That is all for now. Thanks for reading~

Monday, March 28, 2016

Nim is the only impartial game

I was joking with Eric Kim, a classmate of mine, this week that the game he was studying could be reduced to a certain position of nim. His work on Richmann games studies another very interesting unsolved game theory problem. A Richmann game is a combinatorial strategy game. Given a finite graph and a token placed on a starting vertex (point) of the graph, the game begins. Each player also starts with a fixed amount of money. Then on each turn, both players secretly write on a card how much of their money they are willing to give in order to move the token closer to their destination vertex. The person who bids more is then allowed to move the token one step closer to their destination vertex. However, the player who made the move must pay their opponent how much ever they had on their card. The game ends once one player gets the token to their destination point.

Lots of interesting theorems come out of this game. For example, there is a ratio, such that if the amount of money one player has divided by the amount of money the other player has is exceeding that value, victory will be guaranteed for one player. The game also allows for Richmann values to be designated to positions and Richmann costs be designated to moves.

Just within the setup of the game, I noted some similarities to nim. In both games, we are able to assign value to certain positions. Both games also follow the strict alternating turns pattern.

As I was noting the similarities, things started to add up for me. I saw (very intuitively and roughly and not very mathematically at all) how the games seemed similar. So I stared at my notebook for some time. However, something bothered me. A simple rule of Richmann games seemed out of place. The rule was that addressing the occurence of a tie. If two players both are willing to wager the same amount of money, the rules of Richmann games say to flip a coin, with the winner of the coin flip allowed to move the token towards their destination. Given that the probability that two players wager the same value is quite literally zero (since they can wager any non-negative real number, of which there are infinite), this shouldn't actually affect the game. This still bothered me, so I started to look into this a bit more (yayy for new problems). Thats where my week has been in terms of nim.

With Differential Geometry, I think I've caught up, but I wont really know till the midterm next week. Hopefully I'll be able to answer all the problems this time.

Thats all for now.

Thanks for reading~

Monday, March 21, 2016

DIfferential Geometry is hard for me

So Spring Break is finally over. My week away from academics actually proved to be quite relaxing. It allowed me to catch up with friends I hadn't talked to in a while, read books that I wanted to, sleep in (which was honestly the best part), and just relax after four grueling (but super fun) weeks of my senior research project.

Spring Break was also why I did not have a blog post up last week, since I was obviously taking time off. As for this week, a couple of things happened. The MathCounts team I had been coaching did amazingly at the state competition. We had the overall winner and a 3rd place contestant, both who will be moving on to an all expense paid trip to National MathCounts. I'm really excited to see them do well at the next level and even next year, when I'm not there.

And back to my senior research project again. Differential Geometry has been incredibly difficult for me. Not only does it require a solid understanding for both Linear Algebra and Multivariable Calculus, but it also requires rigorous proofs. A lot of differential geometry proofs have been simple to state, even in layman terms, but have incredibly technical proofs. My textbook, de Carmo's Differential Geometry on Curves and Surfaces, has started to get very hard for me, so I've looked at a few other books to learn from.

I might try to read Needham's Visual Differential Geometry and Beltrami's Hyperbolic Plane in order to catch up with what I've been struggling with.

The class has been very analysis-like, so I also thought about reading more complex and real analysis. A few textbooks I've wanted to read are Baby Rudin, Visual Complex Analysis, and Pugh's Real Mathematical Analysis.

I'll start reading some of these books and maybe introduce them and my opinions on them next week. Differential Geometry, despite being so very incredibly horribly terribly difficult has been super rewarding for me. Seeing a college level class six months before I head out has me aware of how difficult college will be.

My senior research project has been a mix of both nim research and differential geometry (more differential geometry recently), but I really have learned a lot from it. I've learned what undergrad research is like and what taking undergraduate classes is like. Getting the whole experience as a hopeful math major has been eye opening.

Thats all for now~
Bye

Monday, March 7, 2016

Mostly Differential Geometry

I'm still having problems programming, so the majority of the blog is going to be about differential geometry at ASU. We went over our midterm this week and continued with lectures. Though the classes have all been really interesting, the schedule of a college student seems pretty routine. Go to class, learn the material, reread the book to make sure you actually get the concepts from lecture, solve practice problems, and repeat.

This week was a lot harder for me than the previous weeks in terms of keeping up with the material. I've had multivariable calculus at school (yay BASIS/Ms. Bailey) and have learnt a bit more afterwards, but the class requires a fluency in it that I don't have. I have the same problem with linear algebra in the class. Luckily, after a good amount of reading and rereading, I've been able to get through the material.

We've been looking at diffeomorphisms this week and how to create maps between two surfaces. A big part of the course studies how surfaces can be smoothly transformed. This week, our lecturer, Dr. Kotschwar, was out of the state for a conference, so we had Dr. Julien Paupert fill us in. This week, we focused on  orientation of surfaces.

Orientation looks at how many 'sides' a surface has. With something like a hollow sphere, we could distinguish the sphere's inside and outside. But with surfaces like mobius strips (https://en.wikipedia.org/wiki/M%C3%B6bius_strip), we cannot distinguish 'sides' in the same way.

Also wikipedia isn't as bad as people think it is, especially in math.

For the most part, a lot of the theorems that we have proved have been intuitively 'obvious', but rather difficult to prove. Soon, we're going to get to the really cool stuff.

You guys are probably also wondering whats going on with my game theory research. I've still been programming/spending most of my time studying differential geometry, so I'll have cool results hopefully by the next post. I don't have much else to say about my project. Next time, I might try to keep my post more organized. I might try to keep myself limited to three things I've learnt at differential geometry and focus on my game theory project. I'll also share some of my (very ugly) recursive formulas I have.

I'll also post pictures (for real this time) since everyone else seems to be doing that. OK, thats all I got. Thanks for reading again.


Saturday, February 27, 2016

Test Week

Hello again! This week definitely wasn't as busy as the last week, but it was still pretty fun. As for research, I've been debugging some of my programs (I'm not very good at programming) and reading literature on other variations of nim. One interesting concept I was looking at was the idea of a Grundy Value.

A Grundy Value is a number that a certain position of an impartial game can be written as. Grundy Values are usually looked at only in impartial games, meaning that it's only looked at in games like nim (since most boardgames aren't technically impartial).

Using binary, the Grundy Values allow us to associate each nim game to a number. This binary representation also allows us to determine 'safe values' in nim. These safe values would be points that a certain player would be guaranteed a win at. Looking at safe values can also check whether a board game is impartial or not. Having a certain set of safe values for a game could mean that the game is not impartial.

My problem is applying all these concepts to nim with a handicap. Once the handicap is added, the game is no longer impartial. Either some of the terms I was learning about don't apply at all anymore or I need to modify them to still apply with the handicap. I'm still pretty lost, but hopefully I can translate some of the theorems for impartial games to nim with a handicap.

In terms of my math class at ASU, things have been going well. I've caught up with the material for the most part. I've really enjoyed the lectures so far too! As for the test...

I took the first midterm for the differential geometry class at ASU. I thought I knew the material, but I turned out to be wrong. There were five problems on the test (and an extra credit problem). I solved three of them. Then I got stuck on the fourth. After wasting a lot of time on the problem, I realized I had another problem to do.  I moved on to the fifth, but I didn't know how to do that one either. The test was hard for me. It's a lot different in college apparently.

I'll study harder for the next one. The test was still fun despite me being bad at it. I don't have anything else to say...

Thanks for reading~

Saturday, February 20, 2016

I have a test coming soon

So this week at ASU was also pretty interesting. In terms of my research project, I'm still writing programs that can calculate win probabilities of certain game scenarios in nim. I'm trying different types of recursive approaches in hopes of getting a better understanding of what actually is happening in the game. One approach I'm using is looking at the win probability of one player in terms of the other and vice versa. The other approach tries to eliminate the second player from the game entirely in the recursive function. Now, there really isn't a point in writing two programs that do the exact same thing, but I was hoping that looking at the problem from two different angles would help give me insight mathematically (since computer programs just spit out numbers and that's no fun). I'm still programming, but I'm gonna try to bring you guys some cool math for next week.

Also at ASU, my differential geometry class has been going well. I really like the class (and the lecturer) and have almost caught up. We had a quiz on definitions and basic problems today that went well. I forgot to name the book we're using so i'll do that now. It's called Differential Geometry on Curves and Surfaces, written by Do Carmo.

What's also cool is that we have our first midterm on Tuesday, meaning I gotta study ( a lot). This is going to be my first non-Ms. Bailey college level math test so I'm pretty excited. I also need to catch up on homework in the class, since I joined late. I might post a bit about some of the cool things I learn in class or about interesting problems I studied  during my time at ASU.

Lastly, ASU has really great math seminars. Once every two weeks, ASU hosts ASU math circle, where the math department gives a lecture on a cool new topic of research in mathematics in a manner that is understandable to high schoolers. Also, each friday, ASU math department also holds a geometry seminar. While these might be a bit harder than the math circle talks, these are really cool in that the professors at ASU present on topics that they are studying or hope to study soon. Going to these talks is a nice way to see how research at ASU math is going.

Funny thing is, this week, Noam Elkies came to give a talk at ASU. For those of you who don't know who he is, he's a pretty big mathematician. He's the youngest tenured professor at Harvard and just a straight up genius. I had been looking forward to his talk for weeks now, but I totally forgot about it this week. So yeah... that was sad

OK thats all
bye~

Friday, February 12, 2016

Starting my SRP

So this week was strange... I spent a lot of time working on my senior research project at ASU. I did a lot of cool things.

First, I wrote a couple of programs for finding win percentages of different variations of nim. The variation of nim that I considered first was similar to fibonacci nim. From the last post, we know that in nim, there is a set number of stones in the middle, with each player taking turns to remove a certain amount from the pile. The goal of each player is to take the last stone. However in fibonacci nim, after each turn, the other player is allowed to take up to a fixed multiple of the previous players move.  
For example, consider a game with a 100 stones in the middle. If a player took 5 stones in his previous turn, fibonacci nim would allow the next player to take up to 2*5 = 10 stones from the middle on his turn. This would mean that the players would not only have to consider the number of stones in the middle, but also the number of stones removed in the previous turn.

As for handicapping this game, the method I considered was changing the "multiplying factor" of each player. In fibonacci nim, we can say that this factor is 2 for both players, since each player is allowed to take up to twice as many stones as the previous player. However, one method of handicapping would be to limit the multiplying factor of the better player. This would limit the possible moves he could make, reducing his chances of winning. This would mean that the skilled player, who plays perfectly, may not be able to always defeat the unskilled player, who plays randomly.

The second cool thing I did at ASU was attend a talk (there are weekly geometry seminars on Friday) about subriemannian geometry. Now I wish I could say I understood the talk, but I most definitely didn't. I understood the definition of a subriemannian manifold and that was pretty much it. The talk seemed cool though. There were a lot of pretty pictures and stuff. Other people seemed to like it.

The last thing I did was sign up for Math 494 at ASU. So over the next quarter, I'm going to be attending a differential geometry class, taking the tests and doing homework with the students there. The class actually started four weeks ago, so I've got a bit of studying to do. But the class seems fun, so I'm gonna try to learn the stuff.

Ok that's all. Thanks for reading~

Friday, January 22, 2016

An Intro to my project

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.
:)