War is a classic kids card game. I spent many an hour wiling away the time playing war growing up. Enough so that I actually developed a strategy for the game. A strategy for the game of war? That's crazy talk.
For those who've never encounter the game of war here are the rules. A standard deck of 52 cards is shuffled and split between two equal stacks which are then given to the two players. The players then turn over the top card of their stacks and the player with the higher rank card 'wins' and gets to take the two cards and place them at the bottom of their stack. If the cards end up being the same rank, then a 'war' occurs. The players each deal two cards face down (it doesn't really matter that they are face down. Variants of the game include dealing one card face down instead of two.) They then each deal a face up card and the player with the higher rank of these cards wins. If the ranks are the same, then another war ensues. If at any time during a war, a player runs out of cards, then the last card they can play is used as the face up card for the war (this could even be the card which started the war.) The goal, of course, is to be the person who ends up with all the cards (this is war, after all.)
So how in the world could there be a strategy for war? Well it all comes from the fact that when you win, you get to place cards at the bottom of the deck in an order which you get to choose. Of course if both players randomly place the winning bounty of cards onto the bottom of their deck, the game is symmetric and no one has an advantage. But what if you are playing against someone who randomly places cards at the bottom of the deck. Is there then a strategy which can give you an advantage?
War is a very simple card game for two players. Much like real war it's incredibly long and pointless. It's mostly a kids game, since it relies exclusively on luck of the draw. Like most card games it has plenty of regional variations, but the rules used on this site are the standard rules from Wikipedia. The game is played as follows. War simulator (the card game) in Python 3 Hey guys, I want to show off a simple accomplishment, get some general tips if you have them, and get some help modifying what I have. A friend and I created a program that would simulate a 2-player round of the card game War. In our version, a 'war' is three cards face down, not one like in the link. War - Card - Game. This repo will contain the code for war card game in python. War:- War (also known as Battle in the United Kingdom) is a card game typically played by two players. This is my python code for war card game. I'm struggling with implementing the idea of when you have a tie. Each player will place two cards down and the third card for both will determine who wins the 8 cards.
When I was a kid I came up with just such a simple strategy for winning the game of war. My idea was that wars were very important in the game of war (whoda thunk?) and in particular it was important to try to setup your cards in such a was as to win as many wars as possible. The strategy thus worked by attempting to make the cards as close as possible to the template high, low, low, high, low, low, high, etc. One can do this by keeping track of where you are in such a template and then everytime you win ordering your cards so as to best match this template. There is some arbitrariness in this idea: for example if you win and get two cards which should be low, low in the sequence, which one do you put first? One could arbitrarily break ties for this problem or one could use a fixed strategy there as well. Yeah, all good and such, but does this strategy really provide any advantage?
Well, the question is, does my childhood strategy actually provide any advantage against a player that is randomizing the cards they put at the bottom of their deck? Today after many years of procrastination I cranked out a little python code to test this. The code implemented the strategy in a manner such that for any given sequence of high/lows that it was trying to match, the cards were sorted in such a way that the high's were sorted in descending order and the lows in descending order. Thus if you win the cards 1,5,10,7,8,9,6,12 and were trying to match high, low, low, high, low, low, high, low the order would be 12,1,5,10,6,7,9,8.
And what are the results? Well it turns out that indeed this strategy does give you an advantage. After one million games of war, the player implementing this strategy won 548330 times. Okay, not a huge advantage, but not insignificant either.
But this got me thinking, what about other simple strategies? Suppose you follow a repeated template of high,low, for example? Or high,high,low? Note that because of the way I coded up the program there is sorting going on. Thus a high, high, template causes you to order your cards in increasing order and a low, low template causes you to order your cards in decreasing order. Here are the results of simulations of 100000 games:
| Template | Wins | Notes |
| [high] | 51336 | decreasing sort |
| [low] | 40632 | increasing sort |
| [high,low] | 42102 | |
| [hi,lo,lo] | 54854 | |
| [high,high,low] | 58190 | |
| [low,low,low,high] | 40653 | |
| [low,low,high,high] | 46947 | |
| [low,high,high,high] | 50196 |
An interesting high performing strategy on this list is the high,high,low strategy. It's not obvious to me why this strategy performs so well, but it gives you a pretty significant edge against a random ordering player.
So that's my basic strategy for winning the card game of war. So go out and defeat the average uninformed war player! Fame and fortune will certainly surely then be yours.
David Lightman: What is the primary goal?
Joshua: You should know, Professor. You programmed me.
David Lightman: C'mon. What is the primary goal?
Joshua: To win the game.
- Log in to post comments
Goals
- Learn how to use classes to implement linked lists and other abstract data types in Java
- Learn about building specialized data structures in Java
Submit
Submit LinkedList.java, Deck.java, WarGame.java,and a completed readme_war.txt using thesubmission link on the left.
Extra credit: submit a zip file named extra.zip thatcontains a complete version of your program (all .java files) based onJava generics where LinkedList is based on the GenericList.javainterface (described below).
Introduction
In this project, we will write a program to play a simple card gameknownas War.In War, a standard deck of 52 playing cards is shuffled and dividedevenly among two players (the user and the computer). Playerssimultaneously turn over the top card of their respective decks, andthe player with the high value card takes both cards, adding them tothe bottom of their deck. In the case of a tie (the two cardshave equal value), there is a war where players each place three cardsface down and then one card face up; the player with the higher valuetakes all (ten) cards. In the case of another tie, thisprocess repeats until there is a winner. For added complexity, aplayer may choose to shuffle their deck of cards before eachbattle. The game continues until one player is out ofcards. For more details,see War.
In playing the game, there are several piles of cards: the twoplayers' decks, and the piles of cards in the 'battle' by each player.Cards are continually moved between these different piles. Since thecards in the pile have a specific order, we will use a List torepresent these card piles.
In this assignment, you will implement two variations of the listAbstract Data Type (ADT):
- a linked list, exactly as we discussed in class.
- a new data structure known as a deck that is based on a linked list. Essentially, the deck is a queue of cards that can be shuffled.
You will also implement a WarGame class that runs the interactive Wargame.
We have already provided you with a skeleton for the LinkedList class,which you can download here:
Additionally, you will also need to download the following files forthis assignment:
Python Is This Your Card
Be sure to compile all of the .java files you downloaded.
The Card Data Structure
The Card object represents a single playing card, which has both arank and suit. Aces will be considered 'high'. The Card object usesthe following API:
Note that the Card object provides getters for the rank and suit,which cannot be changed once they are initialized by the constructor.It also provides a set of static final constants to represent facecards and the suits.Here is a simple example of how to use the Card object:
The Card class is complete as given -- you should not modify it incompleting the assignment.
LinkedList Abstract Data Type
You should start by implementing the LinkedList class, which shouldrepresent a singly linked list as discussed in class. In this case,it will be a list of Card objects. To get you started, we've provideda skeleton LinkedList.java.
The List Interface
is a specialtype of construct that defines a public API. Essentially it defines a set of public methods that a class whichimplements that interface must have, but it doesn't provide anyimplementation.- For example, a TV interface might specify methods: togglePower(), volumeUp(), volumeDown(), and setChannel(int n). Then, any class like PanasonicTelevision or SamsungTelevision that implements this interface must provide these public methods.
We have provided the file List.java that specifies the (minimal) setof public methods that your LinkedList class must contain. In orderto have Java enforce this automatically, the LinkedList class must bedefined as follows:
The implements keyword in Java allows us to specify the nameof an interface that the class must use, in this case, List. Thestandard LinkedList provides a number of other methods that you arenot required to implement in this assignment. For a full list ofthese methods for a standard LinkedList, you can refer to thejavadocs:http://docs.oracle.com/javase/6/docs/api/java/util/LinkedList.html.
Implementing LinkedList
You must complete the provided LinkedList.java skeleton. You must alsoimplement the inner class: Node. (Hint: Your node will need twofields: a next reference and a Card data element). Skeleton methodsand explanations for LinkedList are provided in the file.
Notes:
- Review the three *LinkedQueueOfDouble.java examples from lecture. They are all posted on the syllabus page. You are welcome to use sentinel nodes or not, and to use recursion or not in your own linked list methods.
- The add() method is overloaded in the List. One version, add(element), adds an element to the end of the list and always returns true. The other version, add(index, element), adds an element to a specific index of the list.
- Although it might seem odd to have add(element) always return true, this choice makes the List interface suitable for different types of lists. For example, it would also work for implementing a UniqueList where duplicate entries are not allowed. In the UniqueList, add(element)would not always return true, but in our case, it does.
- Several methods, such as get(index), take in an index and return an object. In situations where the index is invalid, it doesn't make sense for the method to signify this by returning null, since null is a valid value for an object (and could certainly be contained in the list). Instead, your implementation should throw an IllegalArgumentException (with an appropriately detailed message) when index is invalid.
- add(index, element) should work correctly if 0 <= index <= size(). For example, this would allow you to call add(0, new Card(Card.ACE, Card.SPADES)) on an empty list and have it insert the ace of spaces as the new head (and tail) element.
- In contrast to the above note, a node must already exist at the specified index for set(index, element) to work. Therefore, set(index, element) can't be used to add new nodes to a list.
- Your War Game program may not use all of the methods in the List interface, but your LinkedList class must still implement them. The reason for this is that we're writing a general LinkedList of cards that can be used in any program; those other programs may use LinkedList methods that are not necessary to write WarGame.
Hint: To get started implementing the LinkedList, start byimplementing the Node inner class, the constructor, add(), andget(). Then, use the unit testing code described below toensure that you can add items and print out the list. Once thesemethods are working, move on to implement the others.
Unit Testing LinkedList
Test your LinkedList implementation before continuing to the next partof the assignment. Copy the following code into the main function ofLinkedList to test add() and get().
You should see the following output when you run LinkedList.Add additional code to your main method to test the other methods ofLinkedList. If you do not have tests for your LinkedListimplementation, we cannot guarantee we can help you on later parts ofthe assignment.The submission script runs extensive testing on your LinkedListimplementation, so you should also try submitting yourLinkedList.java file before moving on to the next part of thisassignment. You can always re-submit it later, and the submissionscript testing may prove very useful for helping to identify problemsin your LinkedList implementation. Note that the online submissiontesting is not a substitute for doing your own unit testingin main(); the online tests only identify that you have aproblem in a particular method, but do not help you debug that problemlike your unit tests will.
Deck Abstract Data Type
Once you've completely finished and tested your LinkedList class, moveon to your Deck class.
The Deck object will represent complete or partial decks of cards.The deck will operate like a queue, allowing you to remove cards fromthe top of the deck and add cards to the bottom of the deck. It willalso allow you to shuffle the cards in the deck, randomizing theirorder.
Building the Deck from LinkedList
While we could completely re-implement this class from scratch, thebest way is to build the Deck off of LinkedList. The Deck classshould have a LinkedList of cards as a private field. The variousmethods for the Deck class will then call the corresponding methods onthe private LinkedList field to implement the functionality.
Hint: your Deck class should be much shorter than your LinkedListclass. By building Deck off of LinkedList, you gain much of thefunctionality you need with minimal effort.
Implementing Deck
Your Deck class must conform to the following API:
To test your Deck, copy the following code into your main method:When run, this should output all of the cards in the deck, with thelast card being a duplicate ace of spades.
Write a few other tests in Deck.main() to make certain that your Deckclass works.
Implementing shuffle().Shuffling a deck of cards works very much like selection sort.However instead of picking the smallest remaining card to swap intoposition, you should pick a random card. There is example code forshuffling an array in Section 1.4 of the textbook (and booksite).
Since you are shuffling a linked list, not an array, you can simplymove the cards into position; there is no need to swap. Moreover, youcan always move cards to the very front (or very back) of the array,rather than to position i as the array version does.
Your shuffle() implementation must be entirely linkedlist-based. You may not use arrays.
Testing shuffle(). Add a callto shuffle() immediately after the call to fill() inthe testing code above. Your deck should now print in random order,with an extra ace of spades at the end. You should get a differentrandom order each time you run your unit test.
The War Card Game Program
Your WarGame.java program should simulate a game of War, as describedin the Introduction. It should not take in any command linearguments. Each round of play, the user will have the option ofpressing the 'Enter' key to play a card against the computer or the'S' (or 's') key to shuffle the deck. The game is over when oneplayer runs out of cards. If there is a war, and one player hasfewer than four remaining cards, the other player wins.
You should not be using the Processing library for this assignment.You can read input from the user via StdDraw.nextKeyTyped(),just as in GuitarHero.
Here is an example of how your WarGame program should operate. Youmay enhance the text of the program as you like, but the interaction(keys the user can press and their effect) must be the same as in thisexample.
Extra Credit 1: Animating the game
Write a program, AnimatedWarGame.java that plays war anddraws and animates the cards. You may use either StdDraw orProcessing for this version; it's completelly up to you. Submit yourcode and any images in your extra.zip file. You should beable to find card images you like on the internet. Here is a linkto two sets of card images,but you can find many others. Make sure to credit the source of yourimages in your readme and in a comment in your .java file.
War Game In Python
Extra Credit 2: Java Generics
The LinkedList class we wrote above can contain only Card objects;however, it is often useful to implement data structures in a moregeneric way such that they can hold any type of data. Java providesGenerics specifically for this purpose.
War Python Code
For extra credit, modify your LinkedList class to be based upon theinterface GenericList.java instead ofList.java. The methods in GenericList are exactly the same as in List,but they are based on a generic type T that is specified when theLinkedList is declared and initialized. This will enable yourLinkedList to contain any type of object, not just Card objects. Youwill likely need to modify your other classes as well to enable themto use the generic form of the LinkedList.
War Card Game Python Code
War Card Game Python Source Code
If you do the extra credit, you will submit two versions of theassignment: the original (non-generic) version of all files as normal,and an extra.zip file containing new versions of all three .java files(LinkedList.java, Deck.java, WarGame.java)modified to work with the generic LinkedList. Even if one or more ofthese files are unchanged from your non-generic version, you shouldstill include it in extra.zip.