"Hot Game Show Riddler, gameshow.cpp" - Views: 317 · Hits: 317 - Type: Public

// GameShow.cpp : Defines the entry point for the console application.
// Jon Wiesman, somedisagree.com

#include "stdafx.h"
#include <stdlib.h>
#include <time.h>
#include <cmath>

#define PRECISION "%.8f"

double RandDouble()
{
    return (double)rand() / (double)RAND_MAX;
}

double GetScore(double thresh)
{
    double score = RandDouble();
    if(score >= thresh)
        return score;
    return RandDouble();
}

int GameShow(double aThresh, double bThresh)
{
    double a = GetScore(aThresh);
    double b = GetScore(bThresh);

    if(a > b)
        return 0;
    if(b > a)
        return 1;

    return -1;
}

double MCGameShow(int trials, double a, double b, bool verbose = false)
{
    int aWins = 0;
    int bWins = 0;

    for(int i = 0; i < trials; i++)
    {
        int res = GameShow(a, b);
        if(res == 0)
            aWins++;
        if(res == 1)
            bWins++;
    }
    double pct = (double)aWins / (double)(aWins + bWins);
    if(verbose)
    {
        printf("MC: With A " PRECISION " and B " PRECISION ", A wins " PRECISION "%%.\n"
            , a, b, pct * 100.0);
    }
    return pct;
}

double AOverB(double a, double b, bool verbose = false)
{
    double dPct = 0.5;
    if(a > b)
    {
        double dOddsOver = (a - b) / a;
        dPct = dOddsOver + (1 - dOddsOver) * 0.5;
    }
    else if(a < b)
    {
        dPct = 1 - AOverB(b, a);
    }
    if(verbose)
    {
        printf("Math " PRECISION " over " PRECISION " = " PRECISION "\n", a, b, dPct);
    }
    return dPct;
}

double AWinPct(double a, double b, bool verbose = false)
{
    if(a == b)
        return 0.5;

    double odds1 = a * b; // (a < thresh, b < thresh)
    double odds2 = (1 - a) * b; // a > thresh, b < thresh
    double odds3 = a * (1 - b); // a < thresh, b > thresh
    double odds4 = (1 - a) * (1 - b); // a > thresh, b > thresh

    double aWins1 = 0.5;
    double aWins2 = a + (1 - a) * 0.5;
    double aWins3 = (1 - b) * 0.5;
    double aWins4 = AOverB(1 - b, 1 - a);

    double pct = odds1 * aWins1 + odds2 * aWins2 + odds3 * aWins3 + odds4 * aWins4;
    if(verbose)
    {
        printf("Math: With A " PRECISION " and B " PRECISION ", A wins " PRECISION "\n", a, b, 100.0 * pct);
    }
    return pct;
}

double FindNash(bool verbose = false)
{
    double a = 0.5;
    double inc = 0.1;
    while(true)
    {
        double pctInc = AWinPct(a + inc, a, verbose);

        if(pctInc > 0.5)
        {
            a = a + inc;
        }
        else 
        {
            double pctDec = AWinPct(a - inc, a, verbose);
            if(pctDec > 0.5)
            {
                a = a - inc;
            }
            else
            {
                inc /= 10.0;
                if(inc < 0.000000001)
                    break;
            }
        }
    }
    if(verbose)
    {
        printf("Nash rejection rate = " PRECISION "\n", a);
    }
    return a;
}

double FindNashMC(bool verbose = false)
{
    const int trials = 100000;
    double a = 0.5;
    double inc = 0.1;
    while(true)
    {
        double pctInc = MCGameShow(trials, a + inc, a, verbose);

        if(pctInc > 0.5)
        {
            a = a + inc;
        }
        else 
        {
            double pctDec = MCGameShow(trials, a - inc, a, verbose);
            if(pctDec > 0.5)
            {
                a = a - inc;
            }
            else
            {
                inc /= 10.0;
                if(inc < 0.000000001)
                    break;
            }
        }
    }
    if(verbose)
    {
        printf("Nash rejection rate = " PRECISION "\n", a);
    }
    return a;
}

int _tmain(int argc, _TCHAR* argv[])
{
    srand((unsigned int)time(NULL));

    double amc = FindNashMC(true);
    
    double a = FindNash(true);
    
    printf("\nComparing Nash rejection rate vs. 50%% via math and Monte Carlo:\n"); 
    AWinPct(a, 0.5, true);
    MCGameShow(10000000, a, 0.5, true);

    return 0;
}