gacha_probability.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "gacha_probability.ipynb",
      "provenance": [],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sr229/gacha-prng/blob/main/gacha_probability.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2dAjjFZLNnYU"
      },
      "source": [
        "## Jupyter Notebook to Calculate Gacha Probabilities in Python"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "zjw7KiDKNuUA"
      },
      "source": [
        "## What is this about?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x8xjncdjNxmt"
      },
      "source": [
        "This specific Notebook is used to calculate probabilities for Gacha games on N times of iterations. It was built to facilitate checking the probability of getting a ideal roll based on the number of iterations and attempts a user has made.\n",
        "\n",
        "We look on two factors that affects how a roll's outcome:\n",
        "\n",
        "- Time-based: some gacha games instead of using a fixed UID seed would use the server time as a seed. This allows it to be a bit more unpredictable however it still maintains it's usual predictability having a fixed rate and a relatively non-cryptographically secure PRNG.\n",
        "\n",
        "- Fixed seed-based: this is the most usual implementations seen in gacha games. They either use the UID or a internal identifier of the user to get your roll. Since we're using a predictable non-secure PRNG, this is the most predictable kind of method usually used and employed by games. Probability is considered constant as well since the seed is never changing."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F9IzvHnnOqL5"
      },
      "source": [
        "## The Algorithm"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "K2YIx6T4OtlZ"
      },
      "source": [
        "This gacha probability notebook uses the Subtractive Pseudo-Random Number Generator used by C#.\n",
        "\n",
        "Quoting [RosettaCode](https://rosettacode.org/wiki/Subtractive_generator):\n",
        "> A subtractive generator calculates a sequence of random numbers, where each number is congruent to the subtraction of two previous numbers from the sequence.\n",
        "\n",
        "The reason this was picked because a large majority of the games currently that has gacha elements are based on Unity C#, and we can assume some of them uses client-side PRNG (however most gacha games have server side PRNG)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ghOSQdaPPVBl"
      },
      "source": [
        "## The code"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iVPmAGiu7Nf2"
      },
      "source": [
        "from random import random\n",
        "from matplotlib import pyplot as plt\n",
        "import time\n",
        "import statistics\n",
        "from numpy import sqrt,empty,array,average,set_printoptions\n",
        "from numba import jit\n",
        "import sys\n",
        "\n",
        "set_printoptions(threshold=sys.maxsize)"
      ],
      "execution_count": 1,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nrjGPvlG97Mz"
      },
      "source": [
        "import os\n",
        "os.environ['NUMBAPRO_LIBDEVICE'] = \"/usr/local/cuda-10.0/nvvm/libdevice\"\n",
        "os.environ['NUMBAPRO_NVVM'] = \"/usr/local/cuda-10.0/nvvm/lib64/libnvvm.so\""
      ],
      "execution_count": 2,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "rVLu-DSb7aYJ",
        "outputId": "22b3095c-d466-4adc-8376-daf5d61fb1d0",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "import collections\n",
        "\n",
        "\"\"\"\"\n",
        "Implements the Subtractive PRNG used by C#: https://rosettacode.org/wiki/Subtractive_generator#C.2B.2B.\n",
        "seed is used to define a new generation for the PRNG. A new call of the srand function is always either a new generation based on that seed alone.\n",
        "\n",
        ":param seed: the seed used for generation. It has to be a value within 1-10^9. Keep in mind this parameter is not persisted between calls. One function call has its own instance.\n",
        "\"\"\"\n",
        "def srand(seed):\n",
        "    r = collections.deque(maxlen=55)\n",
        "    s = collections.deque(maxlen=55)\n",
        "    m = 10**9\n",
        "    s.extend([seed, 1])\n",
        "    s.extend((s[n-2] - s[n-1]) % m for n in range(2, 55))\n",
        "    r.extend(s[(34 * (n+1)) % 55] for n in range(55))\n",
        "    for _ in range(219-54):\n",
        "        r.append((r[0] - r[31]) % m)\n",
        "    while True:\n",
        "        r.append((r[0] - r[31]) % m)\n",
        "        yield r[54]\n",
        "\n",
        "# Verify our SPRNG works\n",
        "x = srand(1029202)\n",
        "print(next(x))"
      ],
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "521657541\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aNZfOus79OSw"
      },
      "source": [
        "\"\"\"\n",
        "Calculates the probability between N times of iterations.\n",
        ":param seed: the seed used by the PRNG to calculate the rate of roll. This could be any positive integers from 1 to 10^9.\n",
        ":param rate: the rate of the roll. By default it uses 0.02.\n",
        ":param iterations: the N amount of iterations to perform to check for a probability\n",
        ":param total_samples: the amount of total samples to check against.\n",
        "\"\"\"\n",
        "# We're using Numba to speed up our increments, since the LLVM opcodes is going to help us alot.\n",
        "@jit(parallel=True, forceobj=True)\n",
        "def get_probability(seed, rate, rate_increment, iterations, total_samples, debug=False):\n",
        "\n",
        "    tl_mean_list = []\n",
        "\n",
        "    prng = srand(seed)\n",
        "    s = 0\n",
        "    start = time.time()\n",
        "\n",
        "    while s < iterations:\n",
        "        trial_list = []\n",
        "        a = 0\n",
        "\n",
        "        while a < total_samples:\n",
        "            trial = 1\n",
        "            x = next(prng) / 10**9\n",
        "            rate_current = rate\n",
        "            while x > rate_current:\n",
        "                trial += 1\n",
        "                x = next(prng) / 10**9\n",
        "                if trial > 50:\n",
        "                    rate_current += rate_increment\n",
        "\n",
        "            a += 1\n",
        "            trial_list.append(trial)\n",
        "\n",
        "        eee = sum(trial_list) / iterations\n",
        "        tl_mean_list.append(eee)\n",
        "        s += 1\n",
        "\n",
        "        if s % 100 == 0 and debug is True:\n",
        "            endf = time.time()\n",
        "            print('progress =','%.2f' % (s*100/iterations),'% (time =','%.2f' % (endf-start),'s)')\n",
        "\n",
        "    return tl_mean_list"
      ],
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vLkJjQIjPbSP"
      },
      "source": [
        "### Probability calculation using a fixed seed\n",
        "\n",
        "The following example plots the probability at 10000 iterations at a fixed rate of 0.02."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4a90poJ4Av1m"
      },
      "source": [
        "# Number of iterations\n",
        "N = 10000\n",
        "# Sample Size\n",
        "sN = 10000\n",
        "\n",
        "# Execute. Keep in mind it may take a while for the function to complete since it's going through a large number of iterations.\n",
        "tl_mean_list = get_probability(102927162, 0.02, 0.02, N, sN)\n",
        "\n",
        "var = statistics.variance(tl_mean_list)\n",
        "\n",
        "print('mean =',sum(tl_mean_list)/sN)\n",
        "print('variance =',var)\n",
        "print('sd =',sqrt(var))\n",
        "\n",
        "fig, ax = plt.subplots(figsize = (10,7))\n",
        "ax.hist(tl_mean_list, bins = 50)\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NDbB0oB7SU7C"
      },
      "source": [
        "### Probability calculation using the Unix time\n",
        "\n",
        "The following example plots the probability at 10000 iterations at a fixed rate of 0.02 but using the ever changing [Unix time](https://en.wikipedia.org/wiki/Unix_time) as our seed."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vnN3r4kbSU7G"
      },
      "source": [
        "# Number of iterations\n",
        "N = 10000\n",
        "# Sample Size\n",
        "sN = 49\n",
        "\n",
        "# Execute. Keep in mind it may take a while for the function to complete since it's going through a large number of iterations.\n",
        "tl_mean_list = get_probability(int(time.time()), 0.02, 0.02, N, sN)\n",
        "\n",
        "var = statistics.variance(tl_mean_list)\n",
        "\n",
        "print('mean =',sum(tl_mean_list)/sN)\n",
        "print('variance =',var)\n",
        "print('sd =',sqrt(var))\n",
        "\n",
        "fig, ax = plt.subplots(figsize = (10,7))\n",
        "ax.hist(tl_mean_list, bins = 50)\n",
        "\n",
        "plt.show()"
      ],
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2Hcxja7sTd6M"
      },
      "source": [
        "## Credits\n",
        "\n",
        "These works are created as a collaboration of the following people:\n",
        "\n",
        "- [SurfChu85](https://twitter.com/SurfChu85)\n",
        "- [Ayane Satomi](https://github.com/sr229)\n",
        "- [Eyenine](https://twitter.com/Eyenine_i9)\n",
        "- [KaidenFrizu](https://github.com/KaidenFrizu)"
      ]
    }
  ]
}