Chopsticks Game – A Combinatorial Challenge

point-finger2trans

So I don’t know if anyone else is familiar with this game, but I just remember playing it with friends in middle school and it occurred to me the other day that it would be an interesting game to analyze combinatorially, and perhaps write a game playing algorithm for. This game can be found in more detail here: http://en.wikipedia.org/wiki/Chopsticks_(hand_game)

Players: 2+.

Rules of Play: Players each begin with two “piles” of points, and each pile has 1 point to begin with. We used fingers to represent this, one finger on each hand.

On each turn, a player can choose to do one of two things:

  1. Send points from one of the player’s pile to one of the opponents piles. So if Player 1 wanted to send 1 point to Player 2’s left pile, then Player 2 would have 2 points in the left pile and Player 1 would still have 1 point in his left pile. Player 1 does not lose points, they are simply “cloned” over to the opponents pile.
  2. If the player has an even number of points in one pile and zero points in the other pile, the player may elect to split his points evenly between the two piles. This consumes the player’s turn. Example: if Player 1 has (0     4) then he can use his turn to split his points, giving him (2     2).

If a player gets exactly 5 points in either pile, that pile loses all of its points and reverts to 0. However, if points applied goes over 5 (such as adding 2 points to a 4 point pile), then the remainder of points are added. (meaning that 4 + 2 = 1). The opponent simply gets points mod 5.

If a player gets to 0 points in both their piles, then they lose. The last person that has points remaining wins.
=========================
Okay, so let’s break this down. Here’s an example game for those of you that are more visually oriented (follow the turns by reading left to right, moves are marked with red arrows):

Okay, so let’s point out a few things about this game.

  • On turn 4, player 2 adds 3 points to player 1’s 2 points, making 5. The rules state that any pile with exactly 5 points reverts to zero.
  • On turn 7, player 2 adds 3 points to 3 points. 3+3=6 as we all know, but 6 \equiv 1 \mod 5, so player 1 now has one point in his pile.
  • On turn 13, player 2 decides to split his points, turning his one pile of 4 into two piles of 2. This consumes his turn.
  • On turn 15, player 2 adds 2 points to player 1’s 3, thus reverting his pile to zero. Player 1 now has no more points to play with, so player 2 wins.

We can think about this game as a combinatorial problem. What are the optimal positions to play? How would one program a computer to play this game? I plan to create an interactive web game where players can try this for themselves.

Advertisements

Twitter FriendCloud

Today I’m going to talk about a personal project I’ve been working on recently. I was trying to come up with some way to make a cool project with natural language processing and I had also noticed that with the rise of social networks, there is a treasure trove of data out there waiting to be analyzed. I’m a fairly active user of Twitter, and its a fun way to get short snippets of info from people or topics you’re interested in. I know personally, I have found a lot of math, science, and tech people that have twitter accounts and post about their work or the latest news in the field. I find just on a short inspection that the people I follow tend to fall into certain “groups”:

  • math
  • computer science
  • general science
  • academia
  • authors
  • tech bloggers
  • feminism
  • various political and social activist figures (civil rights, digital privacy, etc)

This list gives a pretty good insight into the things I am most interested in and like hearing about on my twitter timeline. Now I thought to myself, what if I could automate this process and analyze any user’s timeline to find out what “groups” their friends fell into as well? I had my project.

Currently in the beginning stages, I decided to tentatively call my project “FriendCloud” and registered with the API to start messing around. I’m using Python-Twitter to interact with the twitter API, and its helping me to get practice with Python at the same time. The first thing I wanted to do was be able to pull down a list of all the people that I follow. Since I follow a little over 1000 people, this proved to be a daunting task with the rate limiting that Twitter has built in to their API. At the moment, what I had to do was get my script to pull as many user objects as possible until the rate limit ran out, then put the program to sleep for 15 minutes until the rates refreshed and I could download more.

It took a little over an hour to get the list of all my friends and I am trying to look into a way to do this quicker in the future. After that, I can go through users and pull down a selection of their tweets. After this is done, I have a corpus of text that I can analyze. I have been using NLTK (a Python NLP toolkit) to pick out some of the most common keywords and themes. There is a lot of extraneous data to deal with, but as I pare it down I’ve noticed some interesting trends just in my own tweets.

I hope in the future to be able to extend this to the people I follow on twitter and be able to place them into rough “groups” based on their most commonly tweeted keywords (similar to how a word cloud works). In this way, a user can get an at a glance look at what topics the person is most likely interested in and what sort of people they may be likely to follow in the future.

Day 15: Hangman?

Not feeling like writing much today either. It’s been a tough day.

Making a hangman solving program would be pretty cool. I guess its sort of like an anagram solver in reverse, if that makes sense. We don’t have the word, we are trying to create the word based on a few known letters. Determining what letters are most common in certain positions and finding patterns of words (“ing”, “ed”, “ion”) would be helpful. Compare the current game state with a dictionary to make guesses about the word. Not really a fleshed out idea. Probably coming back to this one.

I think its interesting to think of how we can implement computer programs to “solve” different types of games.

Day 12: Ethical Issues Concerning Artificially Intelligent Agents

If one thinks back as little as twenty years, or even ten years and considers the technology, it is easy to see that there has been an exponential increase in all sorts of technological research. Computers are becoming increasingly prevalent in our everyday lives. Most people have laptops, tablets, smartphones, or some combination thereof. Even cars and some refrigerators have small computers in them. With all of this comes an increase in our knowledge of automation and artificial intelligence. We’ve already got machines to do our laundry and dishes for us, so that begs the question: what’s next?

Google has created a fleet of self-driving cars that are slowly hitting the streets. Will taxi-drivers soon be a thing of the past as well? While all this innovation is great to see, one must step back and consider the effect that this has on the American workforce. In the self-driving car example, thousands of taxi drivers that depend on the job to make a living would be out of a job. But the same thing happened to many independent seamstresses and cobblers with the advent of factories. With even more jobs being automated by these increasingly “intelligent” machines, is human labor destined to be completely replaced by machines? Futhermore, if we can create intelligent robots to do our work for us, should we?

I choose to reject sensationalist views of AI researchers and enthusiasts who claim that the rise of superintelligence will usher in an era of fear and tyranny when the machines seek to overtake the human race. On the other hand, I believe that autonomous robotic agents can be beneficial to us as a race. If the robots do end up taking over menial labor jobs as some claim, then this opens up new job fields to program and oversee these new intelligences. We will have moved to a more technologically advanced way of life.

Day 8: FIRST Tech Challenge

So I’ve been volunteering at a local high school’s robotics club for the past few months, and its been really interesting and informative. They are preparing to compete in the FTC tournament soon. One of the reasons that I decided to help with this club is because honestly, I’m kind of jealous. I went to high school in a very rural area and there were minimal opportunities for extracurriculars in mathematics and science. So I guess part of it is living vicariously a bit, but I also volunteered to help the students learn and get interested in a technological discipline.

The task that their robot must perform for the competition is, to put it simply, to pick up plastic rings from around a course and place them on a coat-hanger style rack in the middle of the course. Hanging rings higher or in certain patterns garners more points. Of course, there are other little things that one can do to gain points (One even involves completely lifting another robot off the ground!) but that is the main point of the competition. So they have been working on ideas for how to build something that can accomplish these tasks quickly and accurately.

They’ve been using the LEGO Mindstorms kit along with the Tetrix parts (also compatible with the NXT). I must admit, I am impressed by what these kids have been coming up with. It’s really cool to hear them tell me their ideas and then go and try them out. They currently have a robotic arm that can raise up and down to perform a task in the competition. The design and implementation has been all on them. While a few are doing it just as a thing to do after school, I’ve seen some real standouts. Several of the people I’ve been working with are very bright and motivated, and looking at going to college for a tech/engineering field. It makes me feel good to know that I worked with these people and helped them grow in their knowledge and confidence.

I’m looking forward to attending the competition (I think its in February) and seeing how my team performs. All in all, its been a really cool experience and I only wish I had the chance to do something like that when I was in high school.

Day 6: Mancala

To go with the theme of programs to solve simple (or sometimes, not so simple) games, I’d like to talk about the game of Mancala today. I grew up playing this game and its always kind of interesting to introduce to people. It involves moving piles of stones around a game board, and using logic and planning to gain the most stones on your side of the board. I was in my advisor’s office at school the other day, and I guess I’ve gotten my love of games and programming from her in some way. Her office is filled with puzzle books and she’s always walking around musing on some problem or other. I saw a mancala board sitting in her office a few days ago, and the idea came upon me to build a program that could function as an AI for Mancala.

To do this, there would have to be some sort of lookahead implemented to analyze possible future moves made by the opponent. While the rules are fairly simple, there are a few unusual things that can happen. It would be interesting to analyze the possible moves from each position, but yet incredibly complex. This is a completely short and untechnical post, but I got a bit distracted and busy today and HECK YEAH OBAMA!

Day 5: Sudoku Solving Program

So in an effort to get back on track with things to talk about, today I’m going to talk about another one of my ideas that have been tossing around in my head for a while. I really enjoy playing Sudoku games, and they have a fairly logical way that you go about solving them. Therefore, I had the idea to see if I could write a program that solves a given Sudoku puzzle.

The first iteration could be a fairly stupid brute force check that goes through each empty space, then starts trying numbers. It would have to check the row, column, and square. If a match was found, it would be inserted, otherwise an array of “possible answers” could be added. As we get more information, we need to modify these possible answers until it is down to one possible answer, and then it can be inserted as well. This is already sounding pretty complex, but its a stupid algorithm and doesn’t take much thought to run through.

To make something more complex, there are a variety of algorithms described here that could also be implemented. Of course, with any algorithm project, one has to take into account the complexity and accuracy of the algorithm and the tradeoffs that come along with that. Nonetheless, I think it would be a fun project to undergo. I am also told by my friend Nathan that this problem has something to do with a research of his, so maybe I’ll go confer with him about it.

Until next time, readers…

(If you’re wondering what this “Day 5” business is about, check out my blog post describing my writing challenge here .)