A demonstration of Jupyter Notebook

dq6-prob-treasure.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ドラクエ 6 - 戦闘終了時にお宝を入手する確率を計算する\n",
    "\n",
    "本稿ではオリジナル版ドラクエ 6 における一度の戦闘終了時の、敵側からお宝を入手する確率の計算法について考察する。\n",
    "また、Jupyter Notebook のレッスンを兼ねるものでもある。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基本的事実\n",
    "### C2B091: お宝入手シーケンス\n",
    "味方パーティーが敵方のお宝を入手したことになる事象を全て列挙する。実際のプログラムは大体このような処理を行う：\n",
    "\n",
    "0. メンバー 1 が盗んだ\n",
    "+ メンバー 1 が盗まず、かつメンバー 2 が盗んだ\n",
    "+ メンバー 1 も 2 も盗まず、かつメンバー 3 が盗んだ\n",
    "+ メンバー 1 も 2 も 3 も盗まず、かつメンバー 4 が盗んだ\n",
    "+ 魔物が宝箱を落とした\n",
    "+ [else] 何もお宝が得られなかった\n",
    "\n",
    "説明の都合上、魔物が宝箱を落としたケースを先に議論する。\n",
    "それから、味方メンバーによる盗みのケースを議論する。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C2B13F: 落とされたことによるお宝入手確率\n",
    "魔物が宝箱を落とす確率は 8 段階に定義されている。この確率の基になる定数がプログラムのアドレス C2B1C3 に定義されている。\n",
    "以降の議論では、便宜上これらの定数をお宝定数を呼ぶことにする。\n",
    "\n",
    "```text\n",
    "                        // COMMENT\n",
    "C2/B1C3:\t0000        // +1 =    1\n",
    "C2/B1C5:\t0700        // +1 =    8\n",
    "C2/B1C7:\t0F00        // +1 =   16\n",
    "C2/B1C9:\t1F00        // +1 =   32\n",
    "C2/B1CB:\t3F00        // +1 =   64\n",
    "C2/B1CD:\t7F00        // +1 =  128\n",
    "C2/B1CF:\tFF00        // +1 =  256\n",
    "C2/B1D1:\tFF0F        // +1 = 4096\n",
    "```\n",
    "\n",
    "ここでは詳しく説明しないが、固定した魔物に対して（個体ではなくクラスにより）この定数が一意に決まる。\n",
    "例えば必ず「ちいさなメダル」を入手できる「なげきのきょじん」は 0x0000 であり、\n",
    "なかなか「はかいのてっきゅう」を入手できないことで知られる「エビルフランケン」は 0x0FFF となる。\n",
    "\n",
    "敵方の魔物が宝箱を落とす確率を $p_d$ とおこう。この値をどう評価すればよいのかを見ていく。\n",
    "\n",
    "とあるサブルーチンで次のような振る舞いをするものがある：\n",
    "\n",
    "* 受け取った 2 バイトの数に 1 を加えた数 `a` を\n",
    "* 範囲 $[0, 0x10000)$ にある数のいずれかランダムに決めた値だけ乗じて 4 バイト長の数を生成し、\n",
    "* その上位 2 バイトを 2 バイト長の数として返す。\n",
    "\n",
    "プログラムコードでは、このサブルーチンの引数に上の表から取った定数を与えて呼び出し、戻り値がゼロでないことを以って宝箱を落としていったことにしている。平たく言うと、この定数に対応する確率表を下のように表現できる：\n",
    "\n",
    "$$p_d \\in \\left\\{1, \\frac{1}{8}, \\frac{1}{16}, \\frac{1}{32}, \\frac{1}{64}, \\frac{1}{128}, \\frac{1}{256}, \\frac{1}{4096}\\right\\}$$\n",
    "\n",
    "分かりやすく言うと、\n",
    "（味方パーティーに盗賊が一人もいなくて）倒した魔物にお宝が設定されているときには、\n",
    "魔物に対応する上述の確率の基になる定数の設定もされていて、\n",
    "ここに記した 8 通りのいずれかの確率で入手イベントが発生する。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### C2B09A: 盗んだことによるお宝入手確率\n",
    "次に、一人の味方メンバーが敵方の魔物から宝物を盗む確率 $p_t$ を考える。\n",
    "議論を簡単にするため、次のことを仮定しておく：\n",
    "\n",
    "* 戦闘終了時に馬車の外に味方パーティーメンバーが 4 名いる\n",
    "* どのメンバーも職業が盗賊であり、職業レベルがいずれも $a$ である\n",
    "* どのメンバーも戦闘終了時に「しに」「まひ」「ねむり」のいずれの状態でもない\n",
    "\n",
    "現在就いている職業が盗賊であり、\n",
    "かつ盗賊レベルが $a$ であるようなパーティーメンバー一人が対象の魔物からお宝を盗む確率\n",
    "$p_t$ を調べよう。\n",
    "\n",
    "* とあるサブルーチンにお宝定数を 4 倍した値を渡して、\n",
    "* 範囲 $[0, 0x10000)$ にある数のいずれかランダムに決めた値だけ乗じて 4 バイト長の数を生成し、\n",
    "* その上位 2 バイトを 2 バイト長の数として戻り値として得る。\n",
    "\n",
    "* この乱数的数と職業レベルを比較し、職業レベルのほうが大きければ盗んだことにして処理を終了する。\n",
    "* 乱数のほうが大きければ、次のメンバーについて同様の乱数生成および大小比較を行う。誰も盗んだことにならなければ処理を終了する。\n",
    "\n",
    "というシーケンスなので、\n",
    "\n",
    "* メンバーの盗賊としての職業レベルを $a$, \n",
    "* 魔物のお宝定数を $c$\n",
    "\n",
    "とおくと、\n",
    "\n",
    "$$p_t = \\min \\left\\{ \\frac{a}{4c + 1}, 1 \\right\\}$$\n",
    "\n",
    "として扱ってよい。ここで $a = 1, .., 8$ であり、$c$ は後ほど述べる定数配列 C2B1C3 の魔物クラスから決まるいずれかの値である。\n",
    "$c = 0$ のときには盗賊レベルが 1 であっても盗んだことになるので、右辺を 1 として扱いたいので便宜上 $\\min$ を入れてあるだけだ。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 基本的な定数を計算する\n",
    "\n",
    "これまでに出てきた定数を Python を利用してコード化する。とりあえず NumPy をインポートしよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "np.set_printoptions(formatter={'int':hex})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "お宝定数の配列 C2B1C3 を配列オブジェクト `C` として表現する。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0x0, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0xfff])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C = np.array([0x0000,\n",
    "              0x0007,\n",
    "              0x000F,\n",
    "              0x001F,\n",
    "              0x003F,\n",
    "              0x007F,\n",
    "              0x00FF,\n",
    "              0x0FFF,], dtype=int)\n",
    "C"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "この `C` から直ちに魔物が宝箱を落とす確率を得られる。これを `P_d` としよう。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  1.00000000e+00,   1.25000000e-01,   6.25000000e-02,\n",
       "         3.12500000e-02,   1.56250000e-02,   7.81250000e-03,\n",
       "         3.90625000e-03,   2.44140625e-04])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P_d = 1 / (C + 1); P_d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "盗賊レベルが 1 である盗賊メンバーがお宝を盗む確率を `P_t` とする。\n",
    "これは `min` を使わずに済み、次のように定義できる。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  1.00000000e+00,   3.44827586e-02,   1.63934426e-02,\n",
       "         8.00000000e-03,   3.95256917e-03,   1.96463654e-03,\n",
       "         9.79431929e-04,   6.10463342e-05])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "P_t = 1 / (4 * C + 1); P_t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ここで、盗賊レベルが `n` である盗賊メンバーが盗む確率は、この値を `n` 倍して 1 と比べて小さいほうを取ることで得られる。Python のコードとしては `P_t[P_t > 1] = 1` なり `np.clip(P_t, 0, 1)` なりすればよいだろう。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##  「はかいのてっきゅう」獲得確率計算例\n",
    "盗賊レベルが最大であるような盗賊職のメンバー 4 人からなるパーティーがエビルフランケンと戦い、\n",
    "戦闘を通常勝利で終了した際に「はかいのてっきゅう」が得られる確率を計算する例を示す。\n",
    "ここで\n",
    "\n",
    "* `p_d` をエビルフランケンが宝箱を落とす確率、\n",
    "* `p_t` を盗賊レベル $a = 8$ のメンバーの一人がお宝定数 $c = 0x0FFF$ で宝箱を落とす魔物からモノを盗む確率、\n",
    "* リスト `P` を上述の事象それぞれの確率\n",
    "\n",
    "と置く。Python で簡単な計算をして各確率を評価すると次のようになる。\n",
    "まず職業レベル `a` とお宝定数 `c` を定義する："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a, c = 8, C[7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`p_d` と `p_t` をそれぞれ定義する："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.000244140625, 0.00048837067334106586)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p_d = P_d[7]\n",
    "p_t = min(8 * P_t[7], 1)\n",
    "p_d, p_t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 戦闘終了時に鉄球が入手できる確率を計算したい場合\n",
    "\n",
    "事象 1. から事象 5. の確率を全部加算して、その値を 1 から引いたほうが早い。\n",
    "戦闘終了後、盗賊の誰かが盗んだか、エビルフランケンが宝箱を落としたかのいずれかが起こる確率を `p` と置く。\n",
    "すると次のように確率の値を計算できる："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.0021957161735115527, 0.99780428382648845)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p = 1 - (1 - p_t)**4 * (1 - p_d)\n",
    "p, 1 - p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "盗賊レベル最大の 4 人パーティーでエビルフランケンと戦ったときに「はかいのてっきゅう」を獲得する確率は、\n",
    "概算で 0.22% 程度の値であることがわかった。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 戦闘終了時にお宝を入手できる確率表を作成する"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "「はかいのてっきゅう」以外にも、より一般的な次の状況における戦闘終了時のお宝入手確率を表にまとめておく。つまり：\n",
    "\n",
    "* お宝定数の全 8 通りについて計算する\n",
    "* パーティー内のアクティブな盗賊人数が 0 から 4 までの場合を全て計算する\n",
    "  ただし、そのような盗賊の盗賊レベルは一律最大値 8 とする（ここまで場合分けするには紙幅が足りない）\n",
    "  \n",
    "NumPy の配列計算機能を利用すると、コード量がかなり軽くなる："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "num_members = np.arange(0, 5) # 0 to 4\n",
    "\n",
    "prob_d = 1 / (C + 1)\n",
    "prob_t = np.clip(a / (4 * C + 1), 0, 1) # a == 8\n",
    "\n",
    "PT, N = np.meshgrid(prob_t, num_members)\n",
    "PD, N = np.meshgrid(prob_d, num_members)\n",
    "\n",
    "prob_table = 1 - ((1 - PT) ** N * (1 - PD))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "確率表のデータが得られたので、各成分を百分率の形式で出力してみよう。\n",
    "表の横軸と縦軸は魔物のお宝定数と有効盗賊人数とにそれぞれ対応する："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[100.000%  12.500%   6.250%   3.125%   1.562%   0.781%   0.391%   0.024%]\n",
      " [100.000%  36.638%  18.545%   9.325%   4.675%   2.341%   1.171%   0.073%]\n",
      " [100.000%  54.117%  29.228%  15.128%   7.689%   3.876%   1.945%   0.122%]\n",
      " [100.000%  66.774%  38.509%  20.560%  10.608%   5.386%   2.714%   0.171%]\n",
      " [100.000%  75.940%  46.574%  25.644%  13.435%   6.873%   3.476%   0.220%]]\n"
     ]
    }
   ],
   "source": [
    "percent_formatter = lambda x: '{:>8.3%}'.format(x)\n",
    "np.set_printoptions(formatter={'float_kind':percent_formatter})\n",
    "print(prob_table)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 参考文献\n",
    "* [ドラクエ6　盗みの確率](http://dq6.org/nusumi.html)\n",
    "* [【盗賊】 - ドラゴンクエスト大辞典を作ろうぜ！！第三版 Wiki*](http://wikiwiki.jp/dqdic3rd/?%A1%DA%C5%F0%C2%B1%A1%DB)\n",
    "* [解析・計算式 | ドラゴンクエスト6 攻略・解析](http://gamecentergx.at-ninja.jp/dq6/analyze.html)\n",
    "* [(SFC) ドラゴンクエスト6 - 盗むの確率](http://gamecentergx.blog.fc2.com/blog-entry-1301.html)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

気になっていたところは修正した。
「とあるサブルーチン」については深く追究できなそうだ。

参考文献追加。いずれも職業レベルの +1 の解釈が正しいのか気になる。
プログラム内の $C2B103 の INC はキャラクターのつよさウィンドウに表示される★の数と一致させるための +1 のはずだ。

確率表を作成した。