A game of numbers

Question

There's a deck with 20 disks, each disk is numbered from 1 to 20

The game involves 2 players, one with only even-numbered disks and one with only odd ones. The rules of the game is as follow:

1) Every round, each player draws a disk from their hand.

2) The player with the greater-number disk wins the round.

3) The game continues, until there's no disk left. The player wins more rounds win the game.

I have just made this game up, so i wanna ask something: If two players draw their disks randomly, what's the probability that the odd-number player will win? Draw? Lose?

Answer 1

Speaking purely from experience, I would be surprised if there is a polynomial time algorithm to find the answer to your question. So I wrote an exponential time algorithm to find the answers. Here are the results.

• Probability even player wins: $6584094720000/13168189440000=0.5$.
• Probability of a draw: $4755012595200/13168189440000\approx0.361098$.
• Probability odd player wins: $1829082124800/13168189440000\approx0.138902$.

Here is also for every possible lead, the possibility that, at the end of the game, the odd player has said lead.

• Lead $-10$: $3628800/13168189440000\approx0.000000275573$.
• Lead $-8$: $3675974400/13168189440000\approx0.000279156$.
• Lead $-6$: $173601792000/13168189440000\approx0.0131834$.
• Lead $-4$: $1651800729600/13168189440000\approx0.125439$.
• Lead $-2$: $4755012595200/13168189440000\approx0.361098$.
• Lead $0$: $4755012595200/13168189440000\approx0.361098$.
• Lead $2$: $1651800729600/13168189440000\approx0.125439$.
• Lead $4$: $173601792000/13168189440000\approx0.0131834$.
• Lead $6$: $3675974400/13168189440000\approx0.000279156$.
• Lead $8$: $3628800/13168189440000\approx0.000000275573$.

I calculated these values with dynamic programming on all possible states of the game.

#include <iostream>
#include <vector>

int main(){
    int N = 10;
    int set_count = 1 << N;
    // dp[p1][p2][10+x] := amount of ways for player 1 to end with a lead of x when the players start with the sets p1 and p2.
    std::vector<std::vector<std::vector<long long>>> dp(set_count, std::vector<std::vector<long long>>(set_count, std::vector<long long>(2 * N + 1)));
    dp[0][0][N] = 1;
    for (int p1 = 0; p1 < set_count; ++p1) for (int p2 = 0; p2 < set_count; ++p2){
        int s = __builtin_popcount(p1);
        if (s == 0 || s != __builtin_popcount(p2)) continue;
        for (int prev_x = N - s + 1; prev_x <= N + s - 1; ++prev_x)
                for (int i = 0; i < N; ++i) if (p1 & (1 << i)) for (int j = 0; j < N; ++j) if (p2 & (1 << j)){
            if (i <= j) dp[p1][p2][prev_x - 1] += dp[p1 & ~(1 << i)][p2 & ~(1 << j)][prev_x];
            else dp[p1][p2][prev_x + 1] += dp[p1 & ~(1 << i)][p2 & ~(1 << j)] [prev_x];
        }
    }
    long long win = 0, draw = dp[set_count - 1][set_count - 1][N], lose = 0;
    for (int lead = -N; lead < 0; ++lead) win += dp[set_count - 1][set_count - 1][N + lead];
    for (int lead = 1; lead <= N; ++lead) lose += dp[set_count - 1][set_count - 1][N + lead];
    long long total = win + draw + lose;
    std::cout << "total: " << total << std::endl;
    std::cout << "win: " << win << ' ' << (long double) win / total << std::endl;
    std::cout << "draw: " << draw << ' ' << (long double) draw / total << std::endl;
    std::cout << "lose: " << lose << ' ' << (long double) lose / total << std::endl;
    for (int lead = -N; lead <= N; ++lead){
        long long x = dp[set_count - 1][set_count - 1][N + lead];
        std::cout << lead << ' ' << x << ' ' << (long double) x / total << std::endl;
    }
    return 0;
}