Wednesday, May 24, 2017

Collaborating to Win a Superbowl Party Game

The approaching NBA Finals reminded me of a game my friends and I play during the Superbowl. It's a little "betting" game to add some interest to the football game. A form is made with several prop bets. Each attendant will choose between one of two choices, many being over-under types. No one has to pay to play. There is no house. It's just a friendly competition to see who can guess the most correctly. Whoever wins the most "bets" right gets a small prize provided by the party host.

Now the lines for these over-under bets are made by Vegas oddsmakers and we get them from the Internet. They don't necessarily represent 50/50 odds for the over/under events. The goal for the oddsmakers is to get 50/50 money on the bets to minimize their risk. So the line represents the average perceived 50/50 odds point of the people who place bets. For my purposes today I'll ignore that and assume the odds are actually 50/50.

At the last Superbowl I brought some family to the party and the five of us filled out our forms. If my goal is not to win but to have someone in my group of five win, what strategy could we use in filing out our forms to maximize the probability that one of us wins? Again, I'll assume every bet on the form has 50/50 odds. We, as a group, also all fill out our forms together. (Or, equivalently, I could enter the contest multiple times.)

This year there were 12 bets on the form. The winner ended up getting 10 correct. The majority of participants got 3 or 4 right. I knew most people going were football fans and would have strong biases when they placed their bets. I figured I probably would have biases, too. So I decided to just use to make each betting decision for me. I ended up getting 6 right.

Suppose I tell my wife that I'll fill out her form. How should I fill it out? The exact opposite of my first form is what I would intuitively decide to do. Her score will be 12-MyScore. We'll come back to this strategy, later. For a group of five, however, it's not so simple.

Consider the outcome space. There are 2^12 or 4096 different ways the results could turn out. We would like the average "distance" from any of these outcomes to one of our five choices to be minimized. "Distance" would be defined as the hamming distance. So the optimal five choices will be placed in this outcome space to jointly minimize their average distance to all possible outcomes. (There's probably some prior research on this topic but I couldn't seem to find the right search term to find it.)

If we have only one choice, it turns out that any choice will do, i.e. any way you fill out the form will, on average, have the same average hamming distance to all possible outcomes. Since all outcomes are equally likely, this makes sense. The expected value of the number of correct bets will be, you guessed it, 6.

I wrote a simple simulator in C++ to find groups of choices (bit strings) that, as a group, minimize the average distance to all outcomes. I can't exhaustively go through all groups of five. That's because 4096 choose 5 is an enormous number (on the order of 10^15). Not so big that it couldn't be done by a super computer but it's too big for the computer and time that I have. So we'll sample the space randomly and find the best ones we can.

The first thing I found was that there are multiple groups-of-five that achieve optimality. This makes sense when you go back to the results of having just a single choice.

To introduce my next result, I would just like to remind you that the number of bits set (or number of bets that are over) follows a binomial distribution. It much more likely that between 5 and 7 bets will be over than that 2 or fewer will be. So when I looked at the number of bits set in each choice over many optimal groups, I found that the number of bits set for my optimal choices also followed a binomial distribution. This makes sense, too. If I can have multiple entries, I want the distribution of my entries to follow the distribution of the outcome space. (For five entries I have a pretty small sample size and perhaps just using the simulator to find an optimal group of five entries would be simpler than coming up with one on my own.)

For the future I'll have to take a look at the other extreme. What betting strategy results in the worst performance? What distribution does it follow? (The inverse of the binomial distribution?)

Also, how does the expected number of correct bets change with number of entries? Obviously this goes up with the number of entries but quantitatively how does it change? All for another day.

Friday, December 30, 2016

Two Games For One Light Strip

I saw a 1-D pong game on Hackaday some time ago. I thought it was just right for a project to work on in my spare time to give as a gift to my sister-in-law's family for Christmas. It was! It uses a PIC16F18855 microcontroller, a potentiometer to adjust brightness, big arcade buttons, and a WS2812b light strip (1 meter, 60 LEDs).

The linked project used an Atmel part but I wanted to try out a PIC part for a couple of reasons. First was because I had my free (to me) PIC programmer so... why not? Second was because of this Application Note (AN1606) from Microchip that describes using the Configurable Logic Cell (CLC) in a way to easily drive WS2811 LEDs. This was easily adapted to my use of the PIC16F18855 and WS2812b LEDs. Though instead of assembly I used the MPLAB Code Configurator to auto-generate my C code to configure the CLC and other peripherals.

The game is simple. Send the light over to your opponent. He must mash his button when the light is close to him (any of the 5 closest LEDs are lit) to return it back to you. You mash your button when the light comes close to you (again, the 5 closest LEDs) to return it to your opponent. If you don't press your button in time, you lose and your opponent gets a point. Depending on which of the 5 LEDs was lit when you pressed your button, the return speed of the light to your opponent will vary. The closer it was to the end of the strip, the faster the return speed; the further, the slower. So if you play well, it will make it difficult for your opponent to return your returns. If you hit too early, it will make it easier for opponent to send a fast one to you. Winning is first to 10 (win by 2) or first to 30. The score is shown after each point by lighting up the number of LEDs corresponding with each player's score. A green LED shows the "line," or the points the game is played to. This will move as the win-by-2 requirement comes into play. A dial on the side adjusts LED brightness.

But just one game? Surely there are more games you can play with two buttons and a strip of lights. There are! I also implemented (though not shown in the video) a "tug-of-war" game. There are two "lines" drawn using a red LED and a blue LED. Then a white LED starts in between these two. Every time you push your button, the white light moves forward. Every time your opponent presses his button, the white light moves backward. Where 1-D pong is about timing and precision, this one is about speed. It's just a button mashing game but it's pretty fun. I originally thought to use the entire strip but then you'd have to press your button as many times as your opponent plus 30. That's a lot. I changed it to be just 10 and sometimes that feels like a lot. The game typically stays in a deadlock until someone tires out. If you just won and are playing again with someone fresh, you'll probably lose. (Okay I'll probably lose. You could win 12 in a row, I'm sure.)

But just two games? Surely there are more games... Nope. That's it. Well, that's all I implemented, anyway. There probably are more but the creativity juice just isn't flowing right now. (But earlier you said "There are!" and not "There is!" I think you owe us another. (No.)) I thought about adding some sort of “secret” mode where you could use the brightness dial and the buttons to set the light strip to any color you wanted for “accent” lighting or something. I wasn’t really sure on it and I ran out of time so that didn’t happen.

My wife and I built the game using some poplar wood to mount it all to and to make boxes for the giant arcade buttons (they're so tall!). She's the better wood worker so I called on her for some help. I soldered it all together on some proto board but I'm pretty sure there was a short or something somewhere because once I put it all together (crammed it in the button box), the switch to change from 1-D pong to tug-of-war didn’t work. So my nephews and nieces only got 1-D pong and no tug-of-war. (Sad.) Making a PCB just for the game would help. It would definitely fit on a cheap-o 5cm x 5cm board that you can get for next to nothing nowadays. I also had some issues with crimp connectors. The far button’s LED wouldn’t light up (which it does when it’s that player’s turn to “serve”). It would work uncrammed from the box but would not after cramming. After attempting to fix both for some time, I gave up and shipped it as is. Lucky for me I have enough parts to make a second one. Time to start drawing up a PCB!

Look at all those wasted pins. The shame.

Ignore that I mixed red/white for power in one place... and reused red/white everywhere.
Another thing I would change was in the mounting of the light strip. We cut out a channel for the strip to sit in so the top was flush with the wood. Then we glued it down. I think that was a mistake. I’d use the plastic clips that are made just for these light strips and just screw down the clips. I hate glue.

The boxes for the buttons are very tall because the arcade buttons are tall. I’d like to find something with a lower profile next time. I figured arcade buttons ought to last a long time, though, and would be easy to repair if something were to happen. Tradeoffs (as always).

The rainbow animation at startup is okay but is kind of lame at lower levels of brightness. I should probably adjust the animation for maximum coolness (i.e. maximum wow-factor (i.e. maximum “take my money!”)) based on the set brightness level. (s/should probably/probably won’t/)

I used a PIC16F18855 because that was the chip used on my PIC programmer (the MPLAB Xpress board) and when I ordered chips I didn't want to find out my "something else" wasn't supported. This one I knew would work. Since ordering parts I've learned many more chips will work (see my previous post about that). I used less than half of the program memory and didn't come close to using all 28 pins. As is, I could use a PIC16F18324 (about 21 cents cheaper in quantity).

I even decided to be a grown up, get a GitHub account, and upload the code there. You can find it here. I don't expect anyone to improve it for me but I'm happy to collaborate.

Wednesday, October 19, 2016

(Almost) Free PIC Programmer (with limitations)

Microchip has made a $10 PIC board to showcase their online IDE, MPLAB Xpress. The board is called the... MPLAB Xpress Board. (Consequence: unhelpful search results!) How do you make it so an online IDE can program your PIC part? Make the programmer look like a USB mass storage device. Now you can (theoretically) use it on any computer the Internet.

I was lucky and was able to snag one of these board for free! They gave away 2000 of them. Free? I can't pass that up. I had never used PIC and never had any real interest. (8-bit? Pffft! But they do have DIP packages...) Did that stop me from getting something for free? No. No it did not. Well after playing with it and looking into all the neat peripherals that PIC parts have, I decided to make this board more useful. I would have put some pin headers on to be able to separate the programmer from the on-board target device but they didn't ask for my input (weird, right?). But they did put some breakout pads on the back of the board (which are pointed out in that linked-to Hackaday article). Obviously we can't have the programmer trying to program two chips at once. So I took the matter of cutting traces into my own knife-wielding hands. I just need to cut right here...

Oops. Wrong spot. (I may get a little impatient when I'm excited to try out an idea.) Actually right there would be better.

Too late now. Two of those five pads are disconnected because I didn't think twice. Luckily some current-limiting resistors provided a nice alternative place to solder some wires to. Crisis averted. A little hot glue to give some mechanical support to my wires and now I have a free PIC programmer!

The firmware for the programmer side is available on GitHub. Here's one drawback listed in the README: "The programming algorithm is currently supporting only the new 8-bit LVP-ICSP protocol common to the PIC16F188xx (5 digit) devices. It is also assuming a fixed row size of 32 words." So... that's a pretty small subset of devices you can program with this. (I count 7 parts that are PIC16F188xx. You want me to read datasheets to figure out if there's more? No thanks. (Okay. I looked at the PIC16F18325/45's datasheet. I'd guess it's compatible based on row size. But no more!)) But I got it for free so I'm not going to complain. And even if they update the firmware source, how am I supposed to update my programmer? (A PICKit 3. But if I had that...)

I even tried it out on a DIP packaged PIC16F18855. It works great! The programmer also has the necessary pull-up resistor for the MCLR line so you can program the chip all by itself in your breadboard.

It's not running in the picture but that LED will blink.
Those wires go to my hacked programmer.

Eventually I'm going to use my PIC16F18855 to drive a strip of WS2812B LEDs. That'll be for another post.

Other links:
MPLAB Xpress forum (for both the IDE and the board, I guess)
Board Schematic

Saturday, January 23, 2016

Running Asterisk with Google Voice on your Synology Diskstation

I run a Synology Diskstation network-attached storage (NAS) at home (specifically a model DS114). I use it primarily for backups but it is really a little server so you can do almost anything on it. This is especially true if you run packages written by the community (though Synology publishes very good ones, too). I run CrashPlan on it so things I store on it are backed up to "the cloud" automatically (see here and here for instructions). I've plugged in a cheap-o USB audio adapter, connected it to my stereo, and can run Shairport on it (originally I ran this but now run the SynoCommunity package). This lets me easily stream audio from my computer to my stereo (using TuneBlade). I also connect my USB printer to it so I can print wirelessly.

One thing I've often wanted to run on it was Asterisk. Asterisk is a program that manages telephone lines and services (especially VoIP lines). Synology officially provides an Asterisk package that even includes a web GUI (though Digium no longer recommends using it). The problem with this package, however, is that they don't include the chan_motif module, which is necessary for running Google Voice lines with it.

While ambitious me usually doesn't stick around too long when he shows up, he was around long enough to try to take the Asterisk source and Synology toolchains from the Synology Open Source Project and rebuild their package from source, this time including chan_motif. I remember getting stuck on building some dependencies for my platform and ended up stopping there.

Months later I decide to revisit this problem. Looking through SynoCommunity's repository for their spksrc tool, I was thinking that maybe this would allow me to more easily create my own Asterisk package. Further looking led me to find their basic instructions for using Debian Chroot (I liked these extended instructions, too). Oh, my. What is this?! It's running a second, parallel OS on your Diskstation. (I've run Optware on a PogoPlug v2 and on my Asus Router that had DD-WRT at the time (now Tomato) and I hated it. I can't remember why but I remember thinking it was such a pain in the neck. I have had zero desire to run it on my Diskstation from day one. That PogoPlug, by the way, lasted less than 18 months before I chucked it in the garbage. I don't miss it. Arch Linux. U-Boot. It all made me want to poke my eyeballs out. That was a long parenthetical.)


Well Debian offers their own package of Asterisk that does include the chan_motif module! No rebuilding from source necessary. (Just a simple 'sudo apt-get install asterisk' is all you neeed.) Now we're cooking with induction.

Now I've seen how things like this go and I am telling you right now that I will not become the go-to guy for support when you want to get Google Voice on Asterisk going on your Diskstation. This is what worked for me in early 2016. May this page go into the rubbish bin of irrelevance and be deemed out-dated not far into the future. I don't care! I have a life to live here, people. (Okay. Okay. I think they get it. Lay off on the attitude a little. (Phrases like "lay off on" make me love English.))

If you want instructions for getting Google Voice going on your Asterisk installation, you can start with Digium's wiki but I would recommend the excellent book Asterisk: The Definitive Guide, 4th Edition which covers it in Chapter 18 (beg your library to get it or if you have a Safari subscription, it's there, too). It's a good book for all things Asterisk.

Wednesday, January 13, 2016

Printing Every Powerball Lottery Number

I think gambling is fascinating. I think it's tempting and I abstain from it. I think it's morally wrong. Value comes from work. You don't get something for nothing in life (there's always a loss to someone).

Tonight the Powerball will play for a world record \$1.5 billion. Billion! That's insane. The odds are also insane. Powerball is played by choosing 5 of 69 numbers and then choosing 1 of 26 "powerballs." How many ways can the Powerball numbers be chosen? That's easy:

\binom{69}{5} \binom{26}{1}

which is:

\frac{69!}{5!(69-5)!} \cdot \frac{26!}{1!(26-1)!}

which is 292,201,338. That's a very big number. I know 1.5 billion is 5 times bigger but it's still a big number. Well let's consider the title scenario of printing out every single Powerball combination possible. Just what would that look like?

When I made a quick test print of different font sizes from 1.5 to 5.5 in half-point increments, I thought 3.5-point Courier New made for a nice size. That's a little more than 1 mm in text height. Making some adjustments to line spacing, page margins, and using 15 columns allowed me to put 2970 Powerball combos on a sheet of paper. If we print double sided we get 5940 combos per sheet of paper (enough combos for 57 years of twice-weekly playing). That means we'll need 49193 sheets of paper or 99 reams of paper! That weighs in at 492 lb. After toner is applied it's sure to weigh more than a quarter of a ton (sorry planet earth). Between me and the paper, I'm pushing the limit of what my Toyota Yaris is rated to carry. (Despite my wife's objection to having 10 cases of useless paper sitting around our house, I think it would be cool to have a copy.)

Walter Hickey wrote an excellent analysis for Business Insider of the expected value of a lottery ticket (written in Sept. 2013). He takes into account the possibility of sharing the jackpot (because more people buy tickets as the jackpot goes up in value) and the loss in value due to taking a lump sum. He does not factor in taxes, though. The short answer is that after taxes, it's never worth playing the lottery. This is no surprise.

The jackpot didn't get to \$1.5 billion by magic. It gets that high because people lose! That \$1.5 billion represents hundreds of millions of \$2 tickets. More tickets than there are combos! The odds truly are terrible. People will often say, "You have to play to win." I would say that the odds are so bad that not playing is as good as winning \$2 (or more!) twice a week for the rest of your life.

Here's a fun simulator (play as much as you want!):

Monday, January 4, 2016

My Not-quite White Space Radio System

2016 will be Merrick's Year of Communications. My goal is to write a blog post once a week. What will I write about? Communications! My previous post mentioned this. Now it's time to talk about the hardware I'll be using.

Communications is a lot more fun when it's wireless. (Consider "tied down," "strapped to my desk," and "the old ball and chain." Not fun.) But as much fun as wireless is, how can I perform wireless transmissions and receptions from my home computer with full control over the transmitted signal? Well a software-defined radio (SDR) would work perfectly for that.

Let's see. I'll just do a quick check here... Oh, I only need to spend nearly $700? No! Just over $400! Oh, wait. Here's one for about $300. Those are all awesome SDRs if you want to transmit. So what's the problem? I'm cheap. I know computers cost that much and I'll be using two of those but permission to purchase a $300 radio hasn't been granted by my local approving authority (i.e. wife).

How cheap? Like $3-eBay-FM-transmitter-direct-from-China cheap. At least for the receivers I'll be using some of those cool RTL-SDR receivers (that often cost less than $10).

Now I'm not dumb and I know that I'm really not going to be doing any modulation of the RF signal by using an FM transmitter. I'm not likely to get more than 10 kHz of bandwidth in the audio spectrum to play around in. So from a cost/bandwidth perspective, these $3 radios don't really match the SDRs I linked to above by an order of magnitude or so. But they're $3! Feeding myself today will cost more than that.

I'd get more bandwidth by just connecting the two computers with audio cables instead of going through the FM transmitter. But, again, it's wireless. And audio cables aren't that interesting. By using the FM transmitter I can make my channel model more noisy interesting.

The FM transmitters are the same ones you'd use to play audio from your phone to your car stereo. They operate under "47 CFR (Code of Federal Regulations) Section 15.239, and the July 24, 1991 Public Notice (still in effect)." They are supposed to have no more range than approximately 200 ft (for $3, I'm hoping for 20 ft). But I can operate them with no restrictions to content (e.g. encrypted) or broadcast duration.

I call this a "not-quite white space radio system" in the title of this post. If I use my FM transmitter in an unoccupied channel on the radio, I'm effectively using a "white space." Unlike actual TV band white space allocations, however, the FM band isn't allocated for white space radio by the FCC (probably because no one wants that space and no one is asking the FCC to do so).

Now I just have to wait for the slow boat from China to make it's way to American shores.

Monday, December 28, 2015

Installing VirtualBox Guest Additions in Fedora 23

It's been a while since I've done anything with digital signal processing (DSP) and I never ended up taking a formal digital communications course in college. So over the next year I have some plans to try out GNU Radio with some very inexpensive radio hardware (on the order of dollars to tens of dollars) to try building some simple digital communications lessons.

I am primarily a Windows user and GNU Radio is primarily a Linux tool. (There are instructions for building GNU Radio to run in Windows but today I'm not going to go there.) We'll discuss my hardware plans later but for now I'll say that primarily we'll be using the audio interface of the computer to move signals around. USB may get involved, too, but it will be secondary. With that in mind, I figure it's no problem if we use a virtual machine. I've decided to run Fedora 23 in VirtualBox.

I'm kind of a novice when it comes to managing Linux machines but that doesn't mean I can't do it. I wanted VirutalBox's Guest Additions installed to my x64 Fedora image but it failed when I tried to install it. After a little Binging (that will never sound as good as Googling) and sorting through my command history, here are the commands I ran to get things into a state where I could install Guest Additions.

  sudo dnf update
  sudo dnf install gcc
  sudo dnf install kernel-devel.x86_64
  sudo dnf install dkms
  sudo dnf install kernel-headers
  sudo dnf install gcc-c++
  sudo dnf update kernel
  # now install Guest Additions. Allow the "CD" to auto-run. Reboot again, I think.

With Guest Additions installed, the virtual machine now displays at the full resolution of my monitor, among other benefits.

Another problem: By default Fedora puts its logo in the bottom corner of your desktop. This eats up a surprising number of CPU cycles running in VirtualBox. Install gnome-tweak-tool to remove it.

  sudo dnf install gnome-tweak-tool

Then disable the background logo in the tweak tool (answer originally found here).

Now we can install GNU Radio and run the GNU Radio Companion.

  sudo dnf install gnuradio

Right now I am having issues with audio buffer underruns. I'm thinking I may have to move on to a live image or actually try to build GNU Radio for Windows. *Sigh.* At least my virtual machine fills my monitor...

I fixed my buffer underrun problem. I made sure the virtual machine's audio controller was ICH AC97 in the VirtualBox settings. Then in Fedora I opened up a terminal and typed 'aplay -L' to list all of the available audio devices. One is listed as:

    Intel 82801AA-ICH, Intel 82801AA-ICH
    Front speakers

That first line is what I typed into my GRC audio sink as "Device Name" parameter. With the sample rate at 44.1kHz I get no underrun errors (a repeating aUaUaUaUaU in GRC's console output). There's some clicks at the start of playback but that's something we can work with. Hooray!