To finish EPGY Traveler you have 2 options:

• Use Dijkstra's algorithm, just settle for having the last edge be potentially sub-optimal
• Do a brute-force expansion of all possibilities

Take a screen shot and write about the algorithm you used.

(Deliverable) Take your Lab 4 proofs (from yesterday) and construct a PDF using latex. Write a blog post where you upload and link to this file and discuss the fine line between the study of Algorithms and the study of AI. If you couldn't figure out how to do the proofs, ask someone to show you… or just do your best. This isn't an algorithms class, so it's no biggie.

Make sure your storing all your stuff in Google Drive under the appropriate days!

Starter Code: http://epgyaisession2.wordpress.com/latex/

https://www.sharelatex.com/

This lab has three parts: Finite State Machine, Game Rendering, Opponent AI

Objective: to create an AI that plays blackjack like the card-counting superstar that it is

Warning: don't spend too much time on the parts that don't matter!

Please work in groups, ESPECIALLY if someone doesn't know the game.

Basic project specifications:

• you are only using one deck of cards
• AI is the dealer
• AI ONLY knows what is faced-up and its own hand
• Your AI must have a name

1. sketch out a Finite State Machine, like we discussed in class
2. Create an enumerated variable called gameState
3. enumerate your desired states of the game
4. The player must be able to do the two basic moves
   1. hit
   2. stay
5. The game will keep going
   1. until the player quits or
   2. 10 games have been played
6. After the game ends you must display some measure of the AI's performance
   1. This can be on the game screen or in the console

1. Read up on the rules of blackjack or choose a partner that knows the game well
2. We don't want to get more complicated than hit/stay
3. The game is only AI vs one player
4. The AI will be allowed the same options
5. You do not need to draw the shapes on the cards they can simply be
   1. GRects that have a GLabel which can read “Q Hearts”
   2. Red/Black Colors, if you are into that sort of thing
   3. I'd avoid any animations more than you need
   4. Make sure the player knows which card is faced up/down
   5. Make sure the player does not see what card is faced down for the AI
6. Make sure the AI does not know more than what is allowed in blackjack

1. Your AI must have a name
2. Your AI must not be dumb
3. Your AI is allowed to count cards

If you need it:

http://www.stanford.edu/~bholtz/AIClass/ExampleCode/ACMGraphics.zip

(Deliverable) Make sure you are saving everything in a zip folder in Google Drive. Write a blog post about your AI, titled your AI's name, and take a screen shot of it in all it's gambling genius.

Apparently in Vegas Black Jack, the dealer hits until 17. If you want to do it like that then that's fine. You can have 2 AI's play each other or have your AI play the human user of your program.

“Las Vegas games are played with two decks and the House must hit on hands less than soft 17 (17 involving an Ace) and must stand on hands of 17 or greater.”

Feel free to work on these together.

There are 1000 cars that must travel from town A to B. There are two possible routes that each car can take (see the Figure): the upper route through town C or the lower route through town D. All roads are one-way as indicated by the arrow (so this is a directed graph).

Let x be the number of cars traveling on the edge A-C, and let y be the number of cars traveling on the edge D-B. The travel time for each car on the edge A-C is x/100, and the travel time for each car on the edge D-B is y/100 (so, for example, if x=800 and y=200, then each car needs 8 minutes to drive down the A-C edge, and each car needs 2 minutes to drive down the D-B, because of the amount of traffic). The travel time per car on the edges C-B and A-D is 12 minutes regardless of the number of cars using these edges (because these are roads with many lanes).

Each driver wants to select a route to minimize his travel time. All drivers must make simultaneous choices.

(a) Explain why any solution with x=500 and y=500 is a Nash equilibrium

(b) Explain why there are no other Nash equilibria.

Next, the government decides to build a new super-fast (one-way) road from C to D. It takes 0 minutes to go from C to D with this new road, regardless of the number of cars using this road. Now, the cars have a third way of going from A to B, namely the path A-C-D-B.

© Explain why the previous Nash equilibria (where half of the drivers use the route A-C-B and the other half use the route A-D-C) are no longer Nash equilibria.

(d) Consider the solution where all drivers use the new route A-C-D-B. Show that this is a Nash equilibrium.

(e) Is the solution where all drivers use the new route A-C-D-B socially optimal? Explain why or why not.

A seller auctions a case of rare wine. There are two bidders. Each bidder is interested in the wine for his or her personal consumption, and they don’t plan to resell the wine. Therefore, the amount at which their value the item can be assumed to be independent, and they are private (i.e., they don’t know each others value). The action is a sealed-bid second-price auction (and, if both bidders make the same bid x, then the winner is selected at random, and pays the price x).

(a) Explain (in two or three sentences) why, for each of the two bidders, bidding the exact amount each bidder values the item is a dominant strategy.

(b) Suppose each bidder values the wine either at 10 or at 20, with equal probability. What is the expected amount that the seller will receive from this auction?

“sealed-bid” means that the bidders must make a bid without knowing the other bidder’s bid. “second-price” means that the highest bidder wins the item but he pays the second-highest bid (so if the bids are 10 and 20, then the person bidding 20 wins but pays only 10). The payoff for a bidder is defined as 0 if he doesn’t get the item, and if he gets the item, it’s the difference between the amount he pays and the amount at which he values the item. So if he values the item at 30 but pays 10 then the payoff is +20.

The tragedy of the commons is a game (in the sense of Game Theory) with many players. It can be viewed as a variant of Prisoner's Dilemma, and it is symbolic for social issues related to sustainability and overexploitation. The story (as originally described by Garrett Harding), is about herders that keep their cows on a common pasture.

We define the tragedy of the commons here as a game with 10 players.The players are herders that each have a number of cows, which they keep on a common pasture. Each player (i.e., each herder) can either play “fair share” or “one extra cow”. In the solution where everybody plays “fair share”, everybody gets 10 points. If a player plays “one extra cow” he gets 2 extra points added to his payoff, but at the same time, all other players get 1 points subtracted from their payoff (due to overgrazing of the pasture). So, for example, if all 10 herders would play “one extra cow”, then each player would get a payoff of 10 + 2 - 9 = 3 points.

In this exercise, we consider only pure strategies (no mixed strategies). A solution, therefore, consists of a choice of strategy for each of the ten players.

This game has exactly one socially optimal solution. Which one is it, and why is there no other socially optimal solution?

In the basic six-degrees-of-separation question, people usually ask whether most pairs of people in the world are connected by a path of at most six edges in the social network, where an edge joins two people if they know each other on a first-name basis. In this question, we consider some different ways of defining the network. Suppose we ask each person in the world to rank the thirty people they know best, in descending order, i.e., starting with the person they know the best (we assume that each person is able to think of 30 people to list).

We now construct two graphs:

• the “Close-friend” graph in which there is a directed edge from each person to the first 10 friends on their list, and
• the “Distant-friend” graph in which there is a directed edge from each person to the ten friends listed in position 21-30 on their list.

Let C be the average number of people you can reach in at most six steps starting from any person in the Closefriend graph. Let D be the average number of people that can be reached in at most six steps from any person in the Distant-friend network.

(a) Explain why C and D must be less than 1,200,000. Hint: first ask yourself how many people you could reach in one step. Then in two steps, etc. In practice, C and D turn out to be much less than 1,200,000.

(b) Research shows that D is larger than C. Give an explanation for this.

Suppose 20% of my email is spam. Also, 5% of all spam that I get contains the phrase “check this out” in the subject line. On the other hand, only 1 percent of non-spam emails contains the same phrase in the subject line. If I receive an email containing the phrase “check this out” in the subject line, what is the chance that it is spam?

In other words, compute the conditional probability P(A|B) where A means that an email being spam and B means that it contains the phrase “check this out” in the subject line. (Bayes Rule)

In this question, you are asked to compute PageRank values of the nodes in a network, using only one iteration of the Basic PageRank Update Rule. To keep things simple, we are not using the Scaled PageRank algorithm, but instead only the simpler Basic PageRank algorithm (the one without the scaling). We consider the following network:

(a) Compute the PageRank of the nodes after the first two iterations of the Basic PageRank Update Rule. As a matter of fact, it can be shown that, as the number of applications of the Basic PageRank Update Rule becomes larger, the PageRank values for the nodes will converge the following limit values: 4/13 for node 1, and 2/13 for node 2, and 4/13 for node 3, and 3/13 for node 4. (b) Show that these limit values form an equilibrium (a.k.a., a fixed point) for the Basic PageRank Update Rule. © Explain why it is not surprising that node 4 end up having a higher PageRank value than node 2.