A utility package for a reinforcement learning study of Hironaka's game of local resolution of singularities and its variation problems.
This quick tutorial provides a short demonstration of some key classes in this repo.
There are 2 ways to start a proper Reinforcement Learning training:
-
(TL;DR, clone this Google Colab file, forget what I say below and start your adventure)
DQNTrainer
is a quick implementation combining my interfaceTrainer
withstable-baseline3
's DQN codes. It runs in 3 lines:from hironaka.trainer.DQNTrainer import DQNTrainer trainer = DQNTrainer('dqn_config_test.yml') trainer.train(100)
Of course, for this to work you need to
- set up the system path so that Python can import those stuff;
- copy the config file
dqn_config_test.yml
from.test/
to your running folder.
-
When you are here in the project folder and
requirements.txt
are met (or create a venv and runpip install -r requirements.txt
), try the following:python train/train_sb3.py
It starts from our base classes
Host, Agent
, goes through the gym wrappers.gym_env.HironakaHostEnv, .gym_env.HironakaAgentEnv
, and ends up usingstable_baseline3
's implementations. In this particular script, it uses theirDQN
class. But you can totally try other stuff likePPO
with corresponding adjustments.
Some of our experimental results are documented here: https://github.com/honglu2875/hironaka-experiments
For ML and RL specialists, hopefully the Quick Start already gives you a good idea about where to start. In addition, please check out
For math-oriented viewers or ML experts who are intrigued about the background story, please feel free to continue with:
- What is a resolution of singularity
- What is Hironaka's polyhedral game
- Variations of Hironaka's game
- Further topics
All versions of the game consist of 2 players. They operate in a non-symmetric fashion. To emphasize the
difference, let us call Player A the "host", player B the "agent". For every turn the game has a state
, the host makes
a move, and the agents makes a move. Their moves change the state
and the game goes into the next turn.
A state
is represented by a set of points
- The host chooses a subset
$I \subset {1,2,\cdots, n}$ such that$|I|\geq 2$ . - The agent chooses a number
$i\in I$ .
The pair state
becomes terminal state
, where the set of terminal states
are defined in each version
slightly different ways.
Defining the reward function is an open-ended question. But our goal is:
- The host needs to minimize the game length (to stop in finite steps is already a challenge).
- The agent needs to maximize the game length.
Therefore, the most straightforward reward function for a host is 1 if game.ended else 0
. For agent, we switch around
to 1 if not game.ended else 0
. There are more (e.g., step reward:=number of points killed for host). But experiments
have been telling us to focus on the original one.
Fix a pair of host and agent. Given an integer
This ratio directly relates to the cumulative rewards for host and agent
exists, it would be an important measure for the pair of host and agent:
- if
$\rho$ is high, the host is strong; - if
$\rho$ is low, the agent is strong.
The existence of the limit is not proven, but empirically
For the detailed structure of the repo, please check out the README starting from the hironaka package. But we would like to draw ML and RL researcher's attention to this submodule first:
This is directly related to the current progress of the model training. I hope the codes and comments are self-explanatory.
Now the big question is, how is this game related to some fundamental questions in pure math, or specifically, algebraic geometry.
An affine algebraic variety
is the common zero locus of polynomial equations. Affine varieties play central role in mathematics, physics and biology.
Affine varieties cut out by one polynomial equation are called affine hypersurfaces. E.g
We can think of varieties as "shapes in affine spaces", and at a generic point
The set
at a is of rank smaller than
Resolution of singularities is a classical central problem in geometry. By resolution we mean that we substitute the original,
possibly singular
The celebrated Hironaka theorem asserts that such resolution exists for all
For example, the blowup of a point in a plane replaces the point with the projectivized tangent space at that point. The geometric picture looks like the following:
(The lecture note where I took the screenshot from. This picture ultimately came from our beloved textbook: Algebraic geometry by Robin Hartshorne)
The most famous and general result concerning resolution of singularities was given by Heisuke Hironaka in 1964 He proved that the resolution of singularities can be achieved by a sequence of blowups
if the characteristic of the base field is zero.
This beautiful and fundamental work was recognized with a Fields medal in 1970. Recently, Villamayor and, independently, Bierstone and Milman have clarified the process of resolution of singularities in characteristic zero, explicitly describing the algorithmic nature of the resolution process.
Using de Jong's deep ideas, simple proofs of Hironaka's theorem have been discovered by de Jong and Abramovich and by Bogomolov and Pantev.
The latest big progress in approaching a simple resolution algorithm was achieved by Abramovich-Tempkin-Vlodarczyk and independenty by McQuillen, who came up with a simple stacky presentation using weighted blow-ups.
In the literature, there appear at least 11 proofs for Hironaka's celebrated theorem on the resolution of singularities of varieties of arbitrary dimension defined over fields of characteristic zero. These proofs associate invariants to singularities, and show that certain type of blow-ups improve the invariant.
We can interpret resolution as a game between two players. Player A attempts to improve the singularities. Player B is some malevolent adversary who tries to keep the singularities alive as long as possible. The first player chooses the centres of the blowups, the second provides new order functions after each blowup.
[definition] & [examples]
[definitions]
The formulation of the resolution as a game goes back to Hironaka himself. He introduced the polyhedra game where Player A has a winning strategy, which provide resolution of hypersurface singularities. He formulated a "hard" polyhedra game, where a winning strategy for Player A would imply the resolution theorem in full generality, but such winning strategy does not necessarily exist. Later Hauser defined a game which provided a new proof of the Hironaka theorem.
Certain modified version of the game, due to Bloch and Levine provide solutions to the moving cylcles problem. Finally, recent work of Berczi shows that a restricted weighted version of the Hironaka game provides closed integration formulas over Hilbert scheme of points on manifolds.
This project started out with this basic version of the game (see the link for the rules). It is a simplified version of Hironaka's original polyhedra game.
This version of the Hironaka game was suggested by Hauser. A simple winning strategy was given by Zeillinger. The existence of winning strategy proves the resolution theorem for hypersurfaces.
The rules:
-
states
: A finite set of points$S\subset\mathbf{N}^n$ , such that$S$ is the set of vertices of the positive convex hull$\Delta={S+\mathbf{R}^n_+}$ . -
state change
: Given the pair$(I,i)$ chosen by the host, for$x=(x_1,\cdots,x_n)\in\mathbb Z^n$ we define$T_{I,i}(x)=(x_1',\ldots, x_n')$ where
The new state
-
terminal states
: a state$S$ is terminal if it consists of one single point.
In short, the host wants to reduce the size of
This is the original Hironaka game from 1970. A winning strategy for the host was given by Mark Spivakovsky in 1980, which proved the resolution theorem for hypersurfaces.
The rules:
-
states
: A finite set of rational points$S \subset \mathbf{Q}^n$ , such that$\sum\limits_{i=1}^n x_i>1$ for all$(x_1,\ldots, x_n)\in S$ , and$S$ is the set of vertices of the positive convex hull$\Delta={S+\mathbf{R}^n_+}$ . -
move
: The host chooses a subset$I \subset {1,2,\cdots, n}$ such that$|I|\geq 2$ and$\sum\limits_{i\in I}x_i\ge 1$ for all$(x_1,\ldots, x_n)\in S$ . The agent chooses a number$i\in I$ . -
state change
: Given the pair$(I,i)$ chosen by the host, for$x=(x_1,\cdots,x_n)\in \mathbb Z^n$ we define$T_{I,i}(x)=(x_1',\ldots, x_n')$ where
The new state
-
terminal states
: a state$S$ is terminal if it consists a point$(x_1,\ldots, x_n)$ such that$\sum\limits_{i=1}^n x_i \le 1$ .
The hard polyhedra game was proposed by Hironaka in 1978. Hironaka has proved that an affirmative solution of this game would imply the local uniformization theorem for an algebraic variety over an algebraically closed field of any characteristic. Mark Spivakovsky showed that Player A does not always have a winning strategy
The rules:
-
states
: A finite set of rational points$S \subset \mathbf{Q}^n$ , such that$\sum\limits_{i=1}^n x_i>1$ for all$(x_1,\ldots, x_n)\in S$ , the denominators are bounded by some fix$N$ , and$S$ is the set of vertices of the positive convex hull$\Delta={S+\mathbf{R}^n_+}$ . -
move
: The host chooses a subset$I\subset {1,2,\cdots, n}$ such that$|I|\geq 2$ and \sum\limits_{i\in I}x_i\ge 1$ for all$(x_1,\ldots, x_n)\in S$ . The agent chooses some element$i\in S$ and modifies the Newton polygon$\Delta$ to a set $\Delta^$ by the following procedure: first, the agent selects a finite number of points $y=(y_1,\ldots, y_n)$, all of whose coordinates are rational numbers with denominators bounded by $N$ as above, and for each of which there exists an $x = (x_1, \ldots, x_n)\in \Delta$ which satisfy some basic relations. $\Delta^$ is then taken to be the positive convex hull of $\Delta \cup {selected \quad points}$. -
state change
: Given the pair$(I,i)$ chosen by the host, for$x=(x_1,\cdots,x_n)\in \mathbb Z^n$ we define$T_{I,i}(x)=(x_1',\ldots, x_n')$ where
The new state
-
terminal states
: a state$S$ is terminal if it consists a point$(x_1,\ldots, x_n)$ such that$\sum\limits_{i=1}^n x_i \le 1$ .
In 2012 Hauser and Schicho introduced a combinatorial game, called Stratify. It exhibits the axiomatic and logical structure of the existing proofs for the resolution of singularities of algebraic varieties in characteristic zero. The resolution is typically built on a sequence of blowups in smooth centres which are chosen as the smallest stratum of a suitable stratification of the variety. The choice of the stratification and the proof of termination of the resolution procedure are both established by induction on the ambient dimension.
In 2021 Berczi introduced the Thom game, which is a weighted version of the Hironaka game. It has a winning strategy, and every run of the game provides a blow-up tree, which encodes a formula for Thom polynomials of singularities, answering long-standing question in enumerative geometry.
The rules:
-
states
: A pair (S,w), where: S is a finite set of points$S \subset \mathbf{N}^n$ , such that$S$ is the set of vertices of the positive convex hull$\Delta={S+\mathbf{R}^n_+}$ ;$w=(w_1,\ldots, w_n)\in \mathbf{N}^n$ is a weight vector associating a nonnegative integer weight to all coordinates. -
move
: The host chooses a subset$I \subset {1,2,\cdots, n}$ such that$|I|\geq 2$ and$\sum\limits_{i\in I}x_i\ge 1$ for all$(x_1,\ldots, x_n)\in S$ . The agent chooses an$i\in I$ such that$w_i$ is minimal in${w_j: j\in I}$ . -
state change
: Given the pair (I,i) chosen by the host, for$x=(x_1,\cdots,x_n)\in \mathbb Z^n$ we define$T_{I,i}(x)=(x_1',\ldots, x_n')$ where
The new state
-
terminal states
: a state$S$ is terminal if it consists of one single point, and
In 2020 Abramovich-Tempkin-Vlodarczyk introduced a new resolution algorithm, based on weighted blow-ups. It significantly simplifies the resolution process and uses intrinstic invariants of singularities which improve after each blow-up.
[]