How Many Hands of Euchre Can Be Played? Part 2

I had posted this regarding the number of possible hands of euchre:

https://plus.google.com/+DenisMcLaughlin/posts/eFzsnEBS3T7

At the end, there is this calculation regarding the number of possible ways a (4 player) euchre hand can be played:

1*(5^4) * 4*(4^4) * 4*(3^4) * 4*(2^4) * 4*(1^4))

This was an overestimate, however, since it assumes that players following the lead can play any of the cards in their hand. In reality, players can only follow with a subset of their cards, since they must follow the lead suit if they can. So, for example, while the above calculation shows the number of ways to play the first trick as:

1*(5^4)

meaning that there is a fixed leader and each of the 4 players can play any of their 5 cards, a more accurate representation of the number of ways to play the first trick would be:

1*(5*(5*R1)^3)

which says that there is a fixed leader who can play any of their 5 cards, followed by the remaining 3 players who can play one of 5*R1 of their cards, where R1 is the ratio of cards in their hand which can be legally played. So if, on average, a following player can only choose from half of the cards in their hand to legally follow in the first trick, R1 would be 0.5.

We can extend this to the second trick in the hand with this:

4*(4*(4*R2)^3)

This says the second hand can be lead by any one of 4 players, that leader can freely play one of their 4 remaining cards, and each of the other 3 players can choose from 4*R2 of their cards. As with R1, R2 is the ratio of playable cards in the second trick. Similarly, we can set up an equation for the third trick, with R3 representing the ratio of playable cards, and an equation for the fourth trick, with R4 representing the ratio of playable cards. For the fifth trick the ratio will be R5, but in practice this will always be 1 since there is only card left to play in the final trick. Altogether, the equation showing the number of ways a 4 player euchre hand can be played is:

1*(5*(5*R1)^3) * 4*(4*(4*R2)^3) * 4*(3*(3*R3)^3) * 4*(2*(2*R4)^3) * 4*(1*(1*R5)^3)

Determining the values of R1 through R5 analytically is difficult, but it's possible to Monte Carlo this calculation by simply playing a large number of games and measuring the ratio of playable cards for each following player in each trick. The euchre player software discussed here does this:

https://plus.google.com/+DenisMcLaughlin/posts/g6yk6Gehnxr

That code currently only implements random (legal) play, so it is not playing strategically. However, based on the random play, the measured ratio of playable cards in each trick for following players can be seen with the --stats option:

Follow Ratio (by trick)
0.47 / 0.57 / 0.68 / 0.82 / 1.00

This shows that the ratio of cards that can be played in the first trick is 0.47 of the total: since there are 5 cards in the hand at that point, that means the average number of playable cards in a following hand in the first trick is (5*0.47) or 2.35. Similarly for the second trick, an average of 0.57 of the 4 cards in players' hands can be played, 0.68 of the 3 cards on the third trick, 0.82 of the 2 remaining cards on the fourth trick, and 1.00 of the last card on the fifth trick.

Substituting these ratios for R1 through R5 in the above equation gives:

1*(5*(5*0.47)^3) * 4*(4*(4*0.57)^3) * 4*(3*(3*0.68)^3) * 4*(2*(2*0.82)^3) * 4*(1*(1*1)^3)

This Google spreadsheet uses these values to recalculate the number of playable hands of euchre here:

https://docs.google.com/spreadsheets/d/1KNStpy2w9dmemeT1gfbHMtncN1WTM9G5L7fw0VdxXoY

With these ratios, it reduces the total number of euchre hands that can be played from 5.35e25 to 1.89e23, which is a reduction by about 300.

The statistical computation of R1 through R5 via the Monte Carlo method is compromised by the mechanism, since the player strategy in the euchre software is random. A more intelligent player algorithm would strategically discard specific cards to reduce the probability that they will have to follow suit and can instead play trump on a non-trump lead. However, this would only adjust the R2, R3, and R4 values (since no strategy can affect R1, and R5 is always 1), and the biggest reduction in possible plays comes from the R1 factor. When a more intelligent player algorithm is developed, these values can be revisited to compare.

Network Euchre Server and Client

I've been working on a network euchre server and client. The server implements a normal set of euchre rules, and can support one game with 4 players at a time. The client emulates 4 players, which interact with the server in order to play a game.

Server: euchred
The server is written in C, and is based on a version I wrote in 1999, with parts reworked as I wrote the client package. The server code is hosted on GitHub, and can be cloned with this command:

git clone git@github.com:Thump/euchred

Client: peuchre
The client package is written in Python, and can emulate up to 4 players. (It can also do fewer, so a manual client could be used with peuchre in order to allow a human player to play against peuchre's emulated players.) The peuchre code can be cloned with this command:

git clone git@github.com:Thump/peuchre

Building It
The euchred package can be built with these commands from inside the cloned source directory:

make

The binary can be found in src/euchred

The peuchre package doesn't need to be built, it's just an executable script in the root of the peuchre source directory, ./peuchre.

Running It
The server can be run from the euchred source directory with:

./src/euchred

It will open a listen socket on port 1234, and wait for clients to connect

The client can be run from the peuchre source directory with:

./peuchred

Player Logic
By default, peuchre will instantiate 4 player objects based on the Player object in the randomplayer.py file. This implements a player with the following behaviour:

• always orders, never goes alone
• never defends alone
• when ordered up, it will drop a random card from its hand in place of the card being ordered
• when offered to lead, it will lead a random card
• when offered to follow, it will follow with a random legal card

It's clearly not a very smart algorithm, but it has the benefit of being easy to code, and can hopefully produce some interesting results.

New Player Logic
The mechanics of the client-server interaction for each player is in the EuchrePlayer object, in the euchreplayer.py file. New player logic can be created by sub-classing this object, as the Player object in the randomplayer.py file does. A new player class must meet these requirements:

• regardless of the name of the file, the object inside the file must be called Player
• the object must implement the following methods:

# returns one of ORDER, ORDERALONE, or PASS
def decideOrderPass(self):

# returns a card from self.hand to drop when ordered up
def decideDrop(self):

# returns either DEFEND or DEFENDPASS
def decideDefend(self):

# returns a card from self.hand to lead play
def decidePlayLead(self):

# returns a card from self.hand to follow play
def decidePlayFollow(self):

In this way, more intelligent players can be developed using peuchre. A new player logic file called foo.py can be passed to peuchre via the --team1 or --team2 command line switch:

./peuchre --team1 foo

Note that you need to remove the .py extension from the filename when passing it to the --team1 or --team2 switches.

Stats
With no options, the peuchre client will create 4 player objects, run a game, then delete the players, re-create them, run another game, etc. Unless limited by the --numgames option, it will continue looping and running games.

The normal output from the peuchre client is a stream of log messages showing the interaction with the euchred server:

root@thistle 368> ./peuchre
2016-07-22 18:42:45 :: This is peuchre
2016-07-22 18:42:45 :: p0t1 g0h0t0 : join successful
2016-07-22 18:42:45 :: p1t2 g0h0t0 : join successful
2016-07-22 18:42:45 :: p2t1 g0h0t0 : join successful
2016-07-22 18:42:45 :: p3t2 g0h0t0 : join successful
2016-07-22 18:42:45 ::
2016-07-22 18:42:45 :: game: everyone is joined, sending start 0
2016-07-22 18:42:45 ::
2016-07-22 18:42:45 :: p2t1 g0h0t0 : cards: Jc Tc 9c Th Js
2016-07-22 18:42:45 :: p2t1 g0h0t0 : I will order Qh to p1t2
2016-07-22 18:42:45 ::
2016-07-22 18:42:45 :: p1t2 g0h0t0 : cards: Ac Qc Qd Td Ah
2016-07-22 18:42:45 :: p1t2 g0h0t0 : gonna drop: Ac

The peuchre client collects stats from various parts of the game as it runs. These stats include:

• games/s
• hands/s
• % of possible hands seen
• % of hands ending euchre
• % of hand playable at each trick

When run with the --stats option, the peuchre client will not show the stream of log messages, and will instead show a live view of these stats:

Peuchre Stats ( 0d 00:02:08 ) Team 1: randomplayer Team 2: randomplayer

Games:
Total: 48
Games/s: 0.37

Hands:
Total: 493 Euchres: 297
Hands/s: 3.83 %euchres: 60.24
Hands/g: 10.27

Call Hands:
Total: 493 Max Reps: 2
Unique: 488 Avg Reps: 1.01
%cover: 2.18

License

Both euchred and peuchre are licensed under GPL version 2.

How Many Hands of Euchre Can Be Played

Euchre is a 4 player team-based trump card game. Each of the 4 players begins a hand with 5 cards chosen from a deck of 24, a trump suit is selected by one of the players, and then play begins. A hand is played as a series of tricks: each player plays one card per trick, and thus there are 5 tricks per hand. To play a trick, a card is led by a selected player, and then the other players must follow with a card of the same suit if they have one, or they can otherwise play any card in their hand. Each card is ranked by its value and suit, and the player who played the strongest card wins the trick and leads for the next trick. At the end of the hand, if the team that called trump has won all 5 tricks they score 2 points, if they've won 3 or 4 tricks they score 1 point, and if they've won fewer than 3 tricks, the opposing team scores 2 points. The first team to a total of 10 points over successive hands wins the game.

How many possible euchre hands can be dealt?

If we deal 5 card hands to each of 4 players, the number of possible dealt hands is:

(24 choose 5)(19 choose 5)(14 choose 5)(9 choose 5)

which is 1.25e14, or roughly 125 trillion unique euchre hands dealt.

How many ways can a euchre hand be played?

Once the hand is dealt, a trump suit is chosen. There are 4 ways trump can be called:

- one of the 4 players can call trump: this results in a 4 player hand
- one of the 4 players can call trump alone (ie. play without a partner): this results in a 3 player hand
- one of the 4 players can call trump and an opponent can defend alone (ie. play without a partner): this also results in a 3 player hand
- one of the 4 players can call trump alone and an opponent can defend alone: this results in a 2 player hand

There are 8 possible ways to call trump in a 4 player hand: each of the 2 teams can choose from 4 suits. (We need only consider the choice by teams, since for a 4 player hand, it doesn't matter which of the team members actually chooses trump, the possible plays remain the same.)

There are 16 possible ways to arrive at a 3 player hand via a go alone: 4 players, each of whom can choose to go alone in one of 4 suits. Similarly, there are 16 possible ways for a defend alone to occur: 2 teams which can choose from 4 suits, with 2 opposing players who can each choose to defend alone. (There can be a rule restricting defending alone after passing, which I'm ignoring: it's not a common rule and it only reduces the number of possible 3 player defend alone hands from 16 to 12.) So there are 32 unique ways to call trump which results in a 3 player hand.

There are 32 possible ways to call trump in a 2 player hand via a go alone and defend alone: 4 players, each of whom can choose from 4 suits alone, with 2 opposing players who can choose to defend alone.

So looking at the number of unique ways to call trump, we have:

- 8 unique ways to call trump in a 4 player hand
- 32 unique ways to call trump in a 3 player hand
- 32 unique ways to call trump in a 2 player hand

Once trump is selected in a 2, 3, or 4 player hand, play begins with the leader playing a card, and then each remaining player playing one card in turn. For the first trick of the hand, the leader is pre-determined (the first participating player left of the dealer), while for subsequent tricks the leader can be any of the players, depending on who won the previous trick.

The leader can freely choose to play any card in their hand. The remaining players must follow this card's suit if they can: if the leader plays a heart and the next player has one or more hearts, then that player must play one of those hearts. If a player does not have any of the led suit, they can choose any of their cards to play. Whether a player has to follow or not affects the hand permutations, but it's difficult to determine this analytically. Thus I'm going to assume a player never has to follow, which will mean this calculation will give an over-estimate on the number of unique ways to play a hand. Once I have statistical data on the follow probability, I can re-analyze.

For the first trick in a 4 player hand, there are 5 possible cards for the leader to play, and then each subsequent player can follow with any of their 5 cards (per the above simplification). So the number of unique card combinations for the first trick is 5^4. For the second trick, there are 4 possible players to lead, each of whom can lead one of 4 cards, with each subsequent player choosing from their own set of 4 cards, making the total number of combinations for the second trick 4(4^4). Similarly, there are 4(3^4) combinations for the third trick, 4(2^4) for the fourth, and 4(1^4) for the fifth. In general, these terms can be read as:

(#leaders)(#cards ^ (#players))

Altogether, the number of unique card combinations for a 4 player hand multiplied by the number of ways a 4 player hand can be set is:

8(1(5^4))(4(4^4))(4(3^4))(4(2^4))(4(1^4))

which is 4.25e11, or roughly 425 billion ways to play a 4 player hand of euchre.

Considering the possible combinations for a 3 player hand of euchre multiplied by the number of ways a 3 player hand can be set, we get:

32(1(5^3))(3(4^3))(3(3^3))(3(2^3))(3(1^3))

which is 4.48e9, or about 4.48 billion.

And for a 2 player hand of euchre, the number of play combinations multiplied by the number of ways a 2 player hand can be set is:

32(1(5^2))(2(4^2))(2(3^2))(2(2^2))(2(1^2))

which is 7.37e6, or about 7.37 million.

To arrive at the total number of euchre hands that can be played, we take the number of unique dealt euchre hands and multiply by the number of ways a euchre hand can be played:

1.25e14(4.25e11 + 4.48e9 + 7.37e6)

which is 5.35e25, or about a 53 trillion trillion different played hands of euchre.

There are a number of over-estimates in this calculation: as discussed, we have not accounted for players having to follow, and there will be hands in which card distribution and trump selection will rule out particular players from ever leading, reducing the number of play combinations. However, this works as an upper bound on the number of euchre hands that can be played.

A Google spreadsheet with these calculations is here:

https://docs.google.com/spreadsheets/d/1KNStpy2w9dmemeT1gfbHMtncN1WTM9G5L7fw0VdxXoY/edit?usp=sharing

Update Android SDK Targets

Soo, you're looking to try out some android development? Well good for you! There are heaps of guides, but I'm going to put here the short answers to stuff I needed to know.

First, go get the Android SDK tools:

http://developer.android.com/sdk/index.html

 Install them, and then run:

tools/android update sdk

Click "Update All..." and you're golden!

Oh noes, you see this error:


Failed to fetch URL http://dl-ssl.google.com/android/repository/repository.xml, reason: Network is unreachable

To fix that, do this:

echo 0 > /proc/sys/net/ipv6/bindv6only

Walla!

Bluetooth Headphones with Stepmania

Maaaaaybe, you play Stepmania. Lovely Stepmania. However, you can't bother folks with the driving thumping beat, so you want to wear headphones. Lovely headphones. But wait! You can't wear wired headphones while dancing! So you want to wear wireless headphones. Bluetooth headphones even. Lovely bluetooth headphones. So how is such a thing done?

To begin, we start with a working Debian system, because that is god's chosen distribution. Lovely Debian.

You need some bluetooth packages, specifically:

bluez
bluez-alsa
libbluetooth3

You need to have a bluetooth adapter in your system, and you'll need to know the bluetooth adapter ID:

root@thorn 1> hcitool dev
Devices:
hci0 00:02:76:09:69:4A

We'll need that bluetooth adapter ID a little later.

And, of course, you need some bluetooth headphones: I'm using Motorola S9-HD headphones, others should work.

Ok, make sure the bluetooth daemon is running:

root@thorn 2> ps -ef | grep bluetoothd
root 5342 5263 0 00:53 pts/16 00:00:00 grep bluetoothd

And we turn on the headphones, and put them in pairing mode. For the S9-HD headphones, they automatically go into pairing mode when turned on (and unpaired), indicated by the LED remaining a solid blue.

First, to confirm that the bluetooth adapter can see the headphones, we query the list of pairable devices that you can see with:

root@thorn 3> hcitool scan
Scanning ...
00:0D:FD:2D:51:88 Motorola S9-HD

This means your computer can see the headphones, and that the bluetooth ID of those phones is 00:0D:FD:2D:51:88. Yay! Then we connect them like this:

root@thorn 4> hcitool cc 00:0D:FD:2D:51:88
Can't create connection: Input/output error

Oh noes! Something is wrong! The reason is that you need to tell your bluetooth adapter what the pin code is. One way is to run the bluetooth-agent, with the (common) pin code of 0000:

root@thorn 5> bluetooth-agent 0000

With this, when bluetoothd attempts to connect, it will use that pin code. However, it's a pain in the ass to have to run that, so instead we stick that code into a configuration file. The configuration file is:

/var/lib/bluetooth/ADAPTERID/pincodes

and the format is:

DEVICEID PIN

So, if our adapter bluetooth ID (shown with the hcitool dev command) is 00:02:76:09:69:4A, and the device bluetooth ID (shown with the hictool scan command) is 00:0D:FD:2D:51:88, then the file to store the pin code is:

/var/lib/bluetooth/00:02:76:09:69:4A/pincodes

and the line in that file showing the pin for the headphones is;

00:0D:FD:2D:51:88 0000

Once that is set up, we should be able to connect:

root@thorn 6> hcitool cc 00:0D:FD:2D:51:88

Hmm, I don't know how to query connected devices though. hcitool con seems like it should show something, but it doesn't. Hmm.

Anyway, now that we've connected our bluetooth device, we add a bluetooth clause to the ALSA config file, ~/.asoundrc:

pcm.bluetooth {
type bluetooth
device 00:0D:FD:2D:51:88
}

Make sure you change the device bluetooth ID as needed.

Now, you can test this out with mplayer:

mplayer -ao alsa:device=bluetooth foo.mp3

Ok, finally, we modify the Stepmania config file, ~/.stepmania/Save/preferences.ini, changing the SoundDevice line:

SoundDevice=bluetooth

Once that is done, running Stepmania should bring the sound through the headphone. Violet!

Automatically sourcing non-default .vimrc

You love your .vimrc, it's like a warm blanket on a cold snowy evening. Howeeeever, sometimes you're working on strange systems, and you just want to temporarily use your .vimrc without disturbing the normal .vimrc. So you copy your .vimrc to a special name (".vimrc-denism", say), and then ... well, you want to source it automatically, of course. So you set the following environment variable:

export VIMINIT="source ~/.vimrc-denism"

Done!

Enabling remote XDMCP in GDM

Suppose you're running a Gnome system, and you have GDM, but need to have it respond to XDCMP requests. By default (on the version of Redhat Enterprise Linux I'm using), GDM doesn't listen to XDMCP:

root@foo 1> lsof -i:177
root@foo 2>

:(

To fix this:

• run gdmsetup
• click the Remote tab
• change the Style tab from "Remote login disabled" to "Same as Local" (or either of the Plain options)
• click the Close button
• run gdm-stop
• run gdm-restart

root@foo 4> lsof -i:177
COMMAND PID USER FD TYPE DEVICE SIZE NODE NAME
gdm-binar 4996 root 3u IPv4 14035 UDP *:xdmcp

Once I had done this, I had further problems (on some systems) where the login banner still wouldn't show. I tracked this down to the systems missing the IPv4 localhost entry in the /etc/hosts file. Adding this line:

127.0.0.1 localhost.localdomain localhost

seemed to fix that.