\documentclass{article}
\usepackage[english]{babel}
\usepackage{amsmath,amssymb,graphicx}

%%%%%%%%%% Start TeXmacs macros
\catcode`\<=\active \def<{
\fontencoding{T1}\selectfont\symbol{60}\fontencoding{\encodingdefault}}
\catcode`\>=\active \def>{
\fontencoding{T1}\selectfont\symbol{62}\fontencoding{\encodingdefault}}
\newcommand{\tmem}[1]{{\em #1\/}}
\newcommand{\tmmisc}[1]{\thanks{\textit{Misc:} #1}}
\newcommand{\tmname}[1]{\textsc{#1}}
\newcommand{\tmop}[1]{\ensuremath{\operatorname{#1}}}
\newcommand{\tmverbatim}[1]{\text{{\ttfamily{#1}}}}
%%%%%%%%%% End TeXmacs macros

\begin{document}

\title{
  Finding slime chunks in Minecraft 1.20.2
  \tmmisc{\tmverbatim{v0.0.1}}
}

\author{Steven Baltakatei Sandoval}

\date{2023-10-08}

\maketitle

\begin{abstract}
  For {\tmname{Minecraft}} \tmverbatim{1.20.2}, an equation is provided to
  calculate the probability of finding a slime chunk within $n$ chunks. A
  table is provided that lists acceptable probabilities of finding a slime
  chunk and the corresponding number of chunks that must be checked.
\end{abstract}

\section{Background}

{\tmname{Minecraft}} is a sandbox video game developed by {\tmname{Mojang}}, a
game development studio owned by {\tmname{Microsoft}}. As of 2023-10-09, the
{\tmem{Java Edition}} of the game is at version \tmverbatim{1.20.2}. The
game's virtual environment consists of a 3-dimensional world in which the
landscape and physics-like interactions utilize voxels known as ``blocks''.
The position of each block is defined by three integer coordinates on a
cartesian grid: $x$, $y$, and $z$. The four cardinal directions are defined
as: north ($- z$), south ($+ z$), east ($+ x$), and west ($- x$). Elevation is
defined as: up ($+ y$) and down ($- y$). The game engine divides the world
into groups of blocks known as ``chunks'' which are volumes defined by $16
\times 16$ areas of blocks in the $xz$ plane, extending up and down for all
$y$. Chunks themselves form a non-overlapping contiguous 2-dimensional
cartesian grid in the $xz$ plane.

This game world is populated with dynamic non-voxel entities known as
{\tmem{mobs}} with positions defined by three floating point numbers that map
to the 3-dimensional block grid. One particular mob of interest is the
{\tmem{slime}}. Any particular chunk has a small probability, $p_s$, of being
capable of randomly generating (i.e. {\tmem{spawning}}) slimes at $y \leqslant
40$ according to a spawning algorithm. Players have an interest killing slimes
because they drop useful items upon death. Therefore, players have an interest
in identifying chunks that are capable of spawning slimes.

However, often players lack the random number seed that defines the
procedurally generated environment, including which chunks are designated as
slime chunks. A player may determine whether a chunk is a slime chunk or not
by excavating a significant amount of underground space below $y = 40$ and
seeing if slimes occasionally spawn or not on the ground in that volume.
However, excavation of blocks in {\tmname{Minecraft}} is a time-consuming
activity requiring significant in-game resources. Therefore, a method is
desired to estimate the number of chunks that must be checked and associated
probability of finding a slime chunk.

\section{Methodology}

\begin{eqnarray}
  p_{\text{s}} & = & 0.1  \label{eq ps}
\end{eqnarray}
Equation \ref{eq ps} gives the probability of a chunk having a slime (i.e.
10\%) which is defined by the game code. To find the probability of at least
one of multiple chunks (i.e. $n$ chunks) being a slime chunk, the problem may
be broken down into simpler cases. In {\tmname{Minecraft}}, one may assume the
algorithm that determines whether any particular chunk is a slime chunk does
so independently for every chunk. Therefore, a tree of binary events may be
drawn that describes all possible outcomes.

An event is when a chunk is checked for the slime generating property. For $n
= 2$ events, the probability tree (see Figure \ref{fig n2-binary-tree})
results in four possible outcomes in terms of the states $s_i = 0$ (chunk
$s_i$ is not a slime chunk) or $s_i = 1$ (chunk $s_i$ is a slime chunk):

\

\begin{figure}[h]
  \raisebox{-0.5\height}{\includegraphics[width=7.94967532467532cm,height=4.46225239407058cm]{20231009T0144+00..slime_chunk_probability_v0.0.1-1.pdf}}
  \caption{\label{fig n2-binary-tree}A probability tree of two binary events,
  resulting in four possible outcomes.}
\end{figure}



The question ``How many outcomes result in at least one chunk being a slime
chunk?'' is the same as asking ``How many of the $\{ s_1, s_2 \}$'s have at
least a single $1$ in them?''. In the simple case of $n = 2$, the answer is 3
of the 4 outcomes: $\{ 0, 1 \}$, $\{ 1, 0 \}$, $\{ 1, 1 \}$ . The fourth
outcome, $\{ 0, 0 \}$, results in no slime chunks.

However, in order to answer the original question ``What is the probability of
at least one chunk being a slime chunk?'', final outcome probabilities must be
calculated. This may be done for each outcome by tracing a path from the tree
root to the outcome's leaf, multiplying together the all the relevant
probabilities at each branch point.

\begin{figure}[h]
  \raisebox{-0.5\height}{\includegraphics[width=9.93290043290043cm,height=4.46225239407058cm]{20231009T0144+00..slime_chunk_probability_v0.0.1-2.pdf}}
  \caption{\label{fig n2-prob-tree}A probability tree describing two events
  with probabilities of each outcome.}
\end{figure}

Figure \ref{fig n2-prob-tree} lists the individual probabilities for each
outcome. Therefore, the answer to the original question is the sum of the
probabilities of the three outcomes: $\{ 0, 1 \}$, $\{ 1, 0 \}$, $\{ 1, 1 \}$:
\begin{equation}
  P_{\text{slime}} = p_{\{ 0, 1 \}} + p_{\{ 1, 0 \}} + p_{\{ 1, 1 \}} = (1 -
  p_s) \cdot p_s + p_s \cdot (1 - p_s) + p_s \cdot p_s \label{eq pslime-hard}
\end{equation}
However, since the probability of all four outcomes must sum to $1$, a simpler
method for calculating $P_{\text{slime}}$ is:
\begin{eqnarray}
  P_{\text{slime}} & = & 1 - p_{\{ 0, 0 \}}  \label{eq pslime-simple}\\
  & = & 1 - (1 - p_s) \cdot (1 - p_s) 
\end{eqnarray}
Equation \ref{eq pslime-simple} says you don't have to calculate and sum up
probabilities of nearly every single outcome; instead, you only have to
calculate the probability of the single outcome where you never get a single
slime chunk. In other words, if one knows the probability of {\tmem{not}}
getting a slime chunk, then the remaining probability is that of getting at
least one slime chunk. In the $n = 2$ example, the probability of never
getting a single slime chunk is $p_{\{ 0, 0 \}}$ which is the probability of
failing to get a slime chunk twice. For higher $n$ cases, $p_{\{ 0, \ldots, 0
\}}$ still only involves multiplying the same $(1 - p_s)$ figure again and
again, one for each event $n$.
\begin{eqnarray}
  P_{\text{slime}} (n = 2) & = & 1 - (1 - p_s)^2 \\
  P_{\text{slime}} (n = 3) & = & 1 - (1 - p_s)^3 \\
  P_{\text{slime}} (n = 4) & = & 1 - (1 - p_s)^4 \\
  & \vdots &  \nonumber\\
  P_{\tmop{slime}} (n) & = & 1 - (1 - p_s)^n  \label{eq pslime-simple-n}
\end{eqnarray}
Therefore, Equation \ref{eq pslime-simple-n} is the equation defining
$P_{\text{slime}} (n)$, the probability of $n$ randomly selected chunks
containing at least $1$ slime chunk among them.

This equation may be useful in order to minimize the amount of work required
to find a slime chunk. Slimes can spawn at elevations below $y = 40$, but they
require open space that must be excavated. In order to reduce excavation work,
an equation can be used to estimate the number of chunks that must be prepared
in order to achieve an acceptably high probability of finding a slime chunk.
\begin{eqnarray}
  P_{\text{acc}} & < & P_{\text{slime}} (n) \\
  P_{\text{acc}} & < & 1 - (1 - p_s)^n  \label{eq pacc-of-n}
\end{eqnarray}
Where:
\begin{eqnarray*}
  P_{\text{acc}} & : & \text{Acceptable probability of finding a slime
  chunk.}\\
  P_{\text{slime}} (n) & : & \text{Probability of finding a slime chunk among
  $n$ chunks.}\\
  p_s & : & \text{Probability of a single chunk being a slime chunk.}\\
  n & : & \text{The number of chunks}
\end{eqnarray*}
Solve Equation \ref{eq pacc-of-n} for $n$:
\begin{eqnarray}
  P_{\text{acc}} & < & 1 - (1 - p_s)^n \nonumber\\
  P_{\text{acc}} - 1 & < & - (1 - p_s)^n \\
  (- 1) \cdot \left( P_{\text{acc}} - 1 \right) & < & - (1 - p_s)^n \cdot (-
  1) \\
  1 - P_{\text{acc}} & > & (1 - p_s)^n \\
  \text{ln}  \left( 1 - P_{\text{acc}} \right) & > & \text{ln}  ((1 - p_s)^n)
  \\
  \text{ln}  \left( 1 - P_{\text{acc}} \right) & > & n \cdot \text{ln}  (1 -
  p_s) \\
  \frac{\text{ln}  \left( 1 - P_{\text{acc}} \right)}{\text{ln}  (1 - p_s)} &
  < & n \cdot \frac{\text{ln}  (1 - p_s)}{\text{ln}  (1 - p_s)} \\
  \frac{\text{ln}  \left( 1 - P_{\text{acc}} \right)}{\text{ln}  (1 - p_s)} &
  < & n \\
  n & > & \frac{\text{ln}  \left( 1 - P_{\text{acc}} \right)}{\text{ln}  (1 -
  p_s)}  \label{eq n-of-pacc-ps}
\end{eqnarray}
For example, in the case of $P_{\text{acc}} = 0.95$, the number of chunks that
must be checked is:
\begin{eqnarray}
  P_{\text{acc}} & = & 0.95 \\
  n & > & \frac{\text{ln}  \left( 1 - P_{\text{acc}} \right)}{\text{ln}  (1 -
  p_s)} \nonumber\\
  n & > & \frac{\text{ln}  (1 - 0.95)}{\text{ln}  (1 - 0.1)} \\
  n & > & 28.43316 \ldots \\
  n & \gtrsim & 29 
\end{eqnarray}
In other words, in order to find a slime chunk with at least 95\% probability,
one must check at least 29 chunks. In {\tmname{Minecraft}} terms, that's a
roughly $5 \times 6$ chunk area. For $P_{\text{acc}} = 99.7\%$ probability, 56
chunks are required (roughly a $7 \times 8$ chunk area):
\begin{eqnarray}
  n & > & \frac{\text{ln}  (1 - 0.997)}{\text{ln}  (1 - 0.1)} \\
  n & > & 55.13586 \ldots \\
  n & \gtrsim & 56 
\end{eqnarray}
\begin{table}[h]
  $\begin{array}{L.rc}
    \hline
    P_{\text{acc}} & n & \text{Area}\\
    \hline
    1.000 \ldots & \infty & \infty\\
    0.99999 & 109 & 10 \times 11\\
    0.997 & 56 & 7 \times 8\\
    0.950 & 29 & 5 \times 6\\
    0.900 & 22 & 5 \times 5\\
    0.750 & 14 & 4 \times 4\\
    0.500 & 7 & 3 \times 3\\
    \hline
  \end{array}$
  \caption{\label{tbl pacc-n-area}The number of chunks $n$ that must be
  excavated in order to find a slime chunk with at least probability of
  $P_{\text{acc}}$, according to Equation \ref{eq n-of-pacc-ps}. An
  approximate area of chunks is provided. The calculations are valid for
  {\tmname{Minecraft}} version \tmverbatim{1.20.2}.}
\end{table}

\section{Conclusion}

The number of chunks, $n$, to be checked for the slime generation property in
{\tmname{Minecraft}} is Equation \ref{eq n-of-pacc-ps}, a ratio of logarithms
that is a function of $P_{\text{acc}}$, the accepted probability of any of the
chunks being a slime chunk and $p_s$, the probability of any particular chunk
being a slime chunk. Table \ref{tbl pacc-n-area} gives a list of various
values of $n$ and $P_{\text{acc}}$ for {\tmname{Minecraft}} version
\tmverbatim{1.20.2}.

\end{document}
