Final Blog Post: Ninety-Nine (Game)

Introduction:

For my semester project I decided to make a card game called Ninety-Nine.  I wanted to make the program for Android and use the Monte Carlo search algorithm for the AI.

After doing some research I decided to change my AI algorithm.

Algorithm:

The algorithm is a simple algorithm, it sorts its hand based on the strategic value and chooses the first legal card.  If the presorted hand is KH 7S 9C then the sorted hand would be 7S 9C KH, if the score plus the potential card is less than or equal to 99 then it plays it if not it moves onto the next card.  If none of the cards are legal it returns the first card.  After doing some testing I found that this algorithm does a fairly good job of playing the game.

 

Gameplay:

At the beginning of the game, three tokens are distributed to each player. Each hand, three cards are dealt to each player, and the player to the left of the dealer takes the first turn. He chooses one of the cards in his hand, places as a discard pile, calls out its value, and then draws a new card. The player to his left then chooses one of her cards and places it on the discard pile, adds its value to the previous card and calls out the new total. If a player forgets to draw a new card before the next player plays, that player must remain one card short for the remainder of the hand. Play proceeds in this manner until a player cannot play without making the total value greater than ninety-nine. That player must turn in one of his or her tokens, all cards are then collected and a new hand is dealt. Any player without tokens loses and is out of the game, while the last player remaining with token wins.

 

Above is a screenshot of the current game.  Player 1 is the human player and Player 2 is the AI.  After each card is played it prints who played what card and updates the score.  When it is the human players turn it prints out the players cards and asks them to choose a card.  It will keep asking them to choose a card until it finds a matching card.

Scoring

4 value is 0 and play is reversed

9 value is 0

10 value is +10 or -10

Jack and Queen values are +10

King sets the total to 99

Ace value 1 or 11

The rest are face value

Android:

I have the logic part figured out and the next thing that I want to complete is the Android side.

The picture is the concept of what I want the app to show.  It displays the players name, tokens remaining, the hand (shows the cards of the human player and backs for AI), the deck, the current score, the top card of the discard pile, and an arrow showing whose turn it is.

List of things to be done with the game:
Game Mechanics:
– Increase the number of players
– Allow users to pick number of opponents
– Allow users to play against friends
– Add different levels of AI difficulty

AI section:
– Fine tune the easy AI algorithm
– Add different values of cards based on number of players
– Add levels of difficulty (experiment with algorithms)

Conclusions:

The game was fun to program, but I wish that I had more time to work on it before the end of the semester.  I plan to continue work on the game during the summer.  I spent a little too much time trying to decide on the AI algorithm and implementing it.  My source code can be found here.  Unzip the file and import the project into Eclipse.

 

References: 
http://users.dickinson.edu/~braught/courses/cs132f01/classes/code/DeckOfCards.src.html  – modified for my DeckOfCards class

http://users.dickinson.edu/~braught/courses/cs132f01/classes/code/CardSuit.src.html – used for my CardSuit class

http://users.dickinson.edu/~braught/courses/cs132f01/classes/code/CardRank.src.html – used for my CardRank class

http://users.dickinson.edu/~braught/courses/cs132f01/classes/code/PlayingCard.src.html used for my PlayingCard class modified to include the strategic value of a card

http://www.jfitz.com/cards/ used for the card images

Project Update (4/22/2013)

I fixed the Concurrent Modification Exception, it was caused by using a for(PlayingCard c : hand) deck.add(hand.remove(c)). Now it is while(!hand.isempty()) deck.add(hand.remove(0)).  After fixing this I was able to run the program without it crashing.  

A new bug is that the players are not being dealt a new hand when a player loses.  Because of this, if a human loses then they are down a card.  The other new bug is that the computer will not play the special cards that it has if the score is in the 90’s.  I believe that this is caused by adding the rank of the card to the score (i.e. the King’s rank is 13 the score is 90 90+13 > 99 so the valid card is not valid).  I plan on changing this by checking the value of the card and returning it back.

Project Background

Ninety-nine is a simple card game based around addition. It uses one or more standard decks of Anglo-American playing cards in which certain ranks have special properties, and can be played by any number of players. During the game, the value of each card played is added to a running total which is not allowed to exceed 99. A player who cannot play without causing this total to surpass 99 loses that hand and must forfeit one token.

Gameplay

At the beginning of the game, three tokens are distributed to each player. Each hand, three cards are dealt to each player, and the player to the left of the dealer takes the first turn. He chooses one of the cards in his hand, places as a discard pile, calls out its value, and then draws a new card. The player to his left then chooses one of her cards and places it on the discard pile, adds its value to the previous card and calls out the new total. If a player forgets to draw a new card before the next player plays, that player must remain one card short for the remainder of the hand. Play proceeds in this manner until a player cannot play without making the total value greater than ninety-nine. That player must turn in one of his or her tokens, all cards are then collected and a new hand is dealt. Any player without tokens loses and is out of the game, while the last player remaining with token wins.

Special Card Values

4 value is 0 and play is reversed

9 value is 0

10 value is +10 or -10

Jack and Queen values are +10

King sets the total to 99

Ace value 1 or 11

Creating the playing cards

http://users.dickinson.edu/~braught/courses/cs132f01/classes/class27.html

Card images

http://www.jfitz.com/cards/

Project Update (4/16/2013)

The AI algorithm is now finished.  It sorts its hand based on the strategic value and chooses the first legal card.  If the presorted hand is KH 7S 9C then the sorted hand would be 7S 9C KH, if the score plus the potential card is less than or equal to 99 then it plays it if not it moves onto the next card.  If none of the cards are legal it returns null.  I found a bug in the program, whenever the program calls the new hand method it has a Concurrent Modification Exception.  This week the plan is to solve the bug and continue to polish the game.

Project Update (4/7/2013)

I finished the sorting method.  I looked at using an evaluation function, Monte Carlo search, and sort the hand by strategic value and choose the first legal card.  I decided on having the program sort the cards and choose the first legal card.  I came to this decision because the evaluation function would be vary complex, some cards increase in value and others decrease in value based on the score and cards in hand.  To get the correct probability for the Monte Carlo search algorithm I would have had to have it count the cards that were already played, the number of players, and how many cards that each player has.  As a result, I choose the sort and choose algorithm which is similar to how I play the game.  I am now finishing up the AI algorithm and plan to start the Android side.

Project Update (3/30/2013)

The classes CardSuit, CardRank, DeckofCards, and PlayingCard where originally implemented by Grant Braught and can be found at http://users.dickinson.edu/~braught/courses/cs132f01/classes/class27.html. Worked on putting the players into an ArrayList, a player is an object that contains a name, a number of tokens, an ArrayList containing PlayingCards, and an identifier to check if the player is a human player or a computer player. Also added a pile where the cards that the players play are stored. In the event that the deck is empty then the pile is shuffled and used as the new deck. Currently I’m working on sorting the cards in the players hand after that is done I am going to start working on the search algorithm for the computer player.