Sigbovik 2019#
the association for computational heresy presents
a record of the proceedings of
SIGBOVIK 2019
the thirteenth annual intercalary robot dance party in celebration of
workshop on symposium about 26th birthdays; in particular, that of
harry q. bovikcover art by chris yu
cover art by chris yu
cover art by chris yu
cover art by chris yu
carnegie mellon university
pittsburgh, pa
april 1, 2019
i
SIGBOVIK
A Record of the Proceedings of SIGBOVIK 2019
ISSN 2155-0166
April 1, 2019
Copyright is maintained by the individual authors, though obviously
this all gets posted to the Internet and stuff, because it's 2019.Permission to make digital or hard copies of portions of this work for
personal use is granted; permission to make digital or hard copies of
portions of this work for classroom use is also granted, but seems
ill-advised. Abstracting with credit is permitted; abstracting with
credit cards seems difficult.Additional copies of this work may be ordered from Lulu; refer to
http://sigbovik.org for details.ii
SIGBOVIK 2019
Message from the Organizing Committee
Greetings friends, colleagues, and complete strangers. It is with
great pride that we welcome you to the 0xDth annual Special Interest
Group on Harry Q. Bovik, held in celebration of Harry Q Bovik's
10somenumberbiggerthan2th birthday. Normally this is where we, the
"committee", would wax poetic about features added1, records broken,
and facts fun. However, this year, we have decided to take the highly
efficient and not at all lazy route of delegating the task of writing
this message to committee members of the past. A sort of temporal
passing of the buck, one might say. Thus I present to you, in reverse
chronological order, some messages.• "Best conference I have chaired so far, also the question mark is
implicit at the end of all the survey
questionspunctuationisfortheweak" --- General Chair 2019• "much as even mentioned in the paper; well, that will teach me to
forget punctuation at the end of my survey questions, won't it?" ---
General Chair 2018• "SIGBOVIK, for those with a special interest in groups-BOVIK. Like
many special interests, I consider it clinically significant." ---
General Chair 2017• "I wish all conferences were as easy to get into prestigious as
SIGBOVIK" --- General Chair 2014• " 'i'm sorry i derelicted my duties to promote sigbovik on twitter
this year but i see you have 30ish submissions already even without me
so HRMPH WHO NEEDS ME um i mean well done!' " --- General Chair 2012
(note: 40ish actually, end note)• "SIGBOVIK is exactly what I had in mind. ---Edgar Allen Poe" ---
General Chair 2008 • "I like to bovik bovik" --- General Chair 2007And with that, the papers.
1Despite my noble intention to dispatch with the labored, formulaic
frontmatter of yestersyear, I was thwarted by a proceedings chair who
insisted that I add an explanation of the unwittily-named "unwitting
participation ribbon" ( ), an unwelcome brand we've affixed to each
paper determined after careful scrutiny to have included a genuine
artifact, thereby furthering the admirable causes of open science and
fruitful procrastination.iii
iv
- Academic Games
Gamification 3 1 Aumann agreement by combat . . . . . . . . . . . .
. . . . . . . . . . . . . 4 2 Monetization of development tools for
fun and profit . . . . . . . . . . . . . 6Let's get this party started! 11 3 Elo World: A framework for
benchmarking weak chess engines . . . . . . . . 12 4 A formal
treatment of k/n power-hours . . . . . . . . . . . . . . . . . . . .
25 5 Eventually consistent partying . . . . . . . . . . . . . . . . .
. . . . . . . . 29Survival advice from a computer scientist 33 6 Survival in chessland
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7
Optimizing The Sacrifice . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 44 8 Abusing the RPM package manager to compile software . .
. . . . . . . . . 49Security and privacy 53 9 CVE-2018-90017117 . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 54 10 Orchhit: User-oblivious
social networking . . . . . . . . . . . . . . . . . . . 55Machine learning 59 11 Color- and piece-blind chess . . . . . . . .
. . . . . . . . . . . . . . . . . . . 60 12 Dimensionality-reducing
encoding for classification of Pythagorean engendered numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 66 13 emojizip: A text compression system based on
pictogram-kiloword equivalence 69 14 Meta-meta-learning for neural
architecture search through arXiv Descent . . 77 15 Towards automatic
low hanging fruit identification for the steering of ML
research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 81
: Architecture: Faster and hotter 85 16 Turing-complete chess . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . 86 17 NaN gates
and flip FLOPS . . . . . . . . . . . . . . . . . . . . . . . . . . .
98 18 HonestNN: an honest neural network "accelerator" . . . . . . . .
. . . . . . 103 19 Simultaneous microwaving architectures: An
efficient scheme for multiplate
- heating . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
- . . . . . . . . 109 20 Precise ECG platform on modern processors . . .
- . . . . . . . . . . . . . . . 114
Chess 119 21 Is "Dicong Qiu. Is this the shortest SIGBOVIK paper?
From 2018 SIG BOVIK paper" the shortest SIGBOVIK paper? . . . . . . .
. . . . . . . . . 120 22 Is this the tiniest SIGBOVIK paper ever? . .
. . . . . . . . . . . . . . . . . 121 23 No, this is the tiniest
SIGBOVIK paper ever. . . . . . . . . . . . . . . . . . 122 24
Revisiting the shortest SIGBOVIK paper / The revised shortest SIGBOVIK
paper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 123 25 On the shortness of SIGBOVIK papers . . . . . .
. . . . . . . . . . . . . . . 128- 1
Simple in theory 131 26 A sublinear approximation method for
np-hardproblems on limited hardware 132 27 Simple theoretically
practical complexity theory . . . . . . . . . . . . . . . . 134Languages 137 28 A formal semantics of Befunge . . . . . . . . . . .
. . . . . . . . . . . . . . 138 29 LATEL: A Logical And Transparent
Experimental Language . . . . . . . . 144 30 GullyNet: Our time will
come . . . . . . . . . . . . . . . . . . . . . . . . . . 150Error-correcting codes 153 31 On double-sided QR codes . . . . . . .
. . . . . . . . . . . . . . . . . . . . 154 32 Novel defense against
code theft using properties of Fibonacci series . . . . 160 33
Error-detecting RLIRFO data structures for the win . . . . . . . . . .
. . . 163Measurement studies 169 34 Applications of Standard ML at Google . .
. . . . . . . . . . . . . . . . . . 170 35 93% of paint splatters are
valid Perl programs . . . . . . . . . . . . . . . . . 174 36 A survey
and projection of SIGBOVIK trends . . . . . . . . . . . . . . . . .
182Back to the future 187 37 Need more RAM? Just invent time travel! .
. . . . . . . . . . . . . . . . . . 188 38 WICCAN: (deep) learning
directly from the future . . . . . . . . . . . . . . 19439 On CLI-based Renderers: In which we investigate the utility of
rendering teapots in a command line . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 200
40 SpaceF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 202
: Pop culture 203
41 Which ITG stepcharts are bracket-jumpiest?: In which they milk the
+A bor ing follow-up paper to "Which ITG stepcharts are turniest?"
titled, "Which ITG stepcharts are crossoveriest and/or
footswitchiest?", series for all its worth in publication count af . .
. . . . . . . . . . . . . . . . . . . . . . . . 20442 The computational theory of Lord Voldemort's dark magic . . . . . .
. . . . 212 43 All you need is dogball . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 215 44 On the time complexity of the
verification of the factorization of 267-1 . . . 2212
Gamification
1 Aumann agreement by combat
Travis Hance
Keywords: Aumann agreement, combat, agents
2 Monetization of development tools for fun and profit Albin
Eldst˚al-Damlin
Keywords: monetization, micro-transactions, free-to-play, gamification 3
1
Abstract
Aumann Agreement by Combat
Travis Hance
methodology, they will be able to come to agreement through a
sequence of statements.
The celebrated Aumann's Agreement Theorem [2] shows that two
rational agents with the same priors on an event who make different
observations will always converge on the same posteri ors after some
civilized conversation over tea. Furthermore, they will come to agree
even if they do nothing other than simply state their posteriors over
and over again.However, this protocol is widely criticized for being too bor ing. We
therefore introduce a more exciting alternative, which we name Aumann
Agreement by Combat.1 Introduction
Informally, Aumann's Agreement Theorem [2] states that two honest
Bayesian agents can come to agreement by stating their priors over and
over again. (Here, the term agent simply means "a person who observes
things and has opinions." However, it is more exciting to imagine them
as secret agents, so we will do so for this paper.)
To take example from Aumann's paper, suppose the agents are
investigating the fairness of a particular coin (say, a very rare coin
involved in a museum heist). We will call the agents A and B, but of
course they are secret agents, so what names these letters stand for
is a mystery. The coin is parameterized by a value p, the probability
that it will land heads when it is flipped. Each agent begins with the
same prior, in this example the uniform prior of p over the interval
[0, 1], because the uniform prior is a reasonable prior to assume
about a coin that one knows nothing about.If A flips the coins and sees heads, then her Bayesian calcu lation
will conclude that the probability of the next flip being heads will
be ⅔. If B flips and sees tails, they he will think the probability
is ⅓. They are now in disagreement. However, if these agents then
meet in a tavern to discuss, then A needs merely to state that her
probability is ⅔, and B will conclude that she must have seen heads
in his single flip. With all of that information, she now concludes
that the probability of another flip being heads will be ½.
Observers will assume that these numbers are all part of a secret
code, but A will understand that B has computed the true probability,
and she will update her probability to ½ as well. Both agents are
now in agreement.Of course, this scenario assumed that both agents knew that the other
would be flipping the coin only once. In more com plicated scenarios,
the agents may have variable methods of observation, for example, they
might flip multiple times, in which case their observations should be
weighted more, or they might not. Still, as long as they have the same
priors on said
1
Unfortunately, this methodology of merely stating opinions is boring.
Furthermore, everybody knows that the goal of arguing is not to reach
the truth, but rather to win. Therefore, we have developed a new
protocol, Aumann Agreement by Combat that alleviates these problems.2 Aumann Agreement by Combat Our new protocol works as follows.
1. Agents A and B start with the same priors.
2. A and B each go out and make observations.
3. A and B meet to discuss the probability of some event E. Each
agent has some initial estimate of the probability of E.4. Players alternate in turns, continuing until their estimates
match. On each turn, an agent has a choice to either:• State their current estimate of E. The other player must use
Bayesian reasoning to update their own estimate.• Declare COMBAT. The agents will fight it out, and at the end, the
loser will adopt the winner's estimate as their own.The COMBAT phase has no rules. Any player is free to try to win by any
means necessary, and they are encouraged to employ all of their wit
and resources to the fullest extent. In the base rules, the battle
ends when one player loses consciousness, although the players may
also agree to a different ending condi tion, such as getting a flag to
one's base, death, or the outcome of a poetry competition.
With this definition in place, we come to our main theorem.
Theorem 1. After an execution of the Aumann Agreement by Combat
protocol, both agents will agree on the correct proba bility of the
event E.Proof. Might makes right.
3 Complexity Analysis
In [1], Aaronson analyzes the complexity of Aumann Agree ment,
showing that O(1/\"2) bits of communication are suffi cient to agree
within \".4
An advantage of our new protocol is that the analysis is much simpler.
The COMBAT phase might take an arbitrary amount of time and resources,
depending on the strategies that the agents employ. They might stake
the COMBAT phase on the outcome of an intergalactic war, for example.
Therefore, there is no complexity bound on time, space, communication,
energy, or anything else.4 Conclusion
We expect that many scholars will welcome this formalization of the
game that they already try to play.References
[1] S. Aaronson. The complexity of agreement. In Proceedings of the
Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05,
pages 634--643, New York, NY, USA, 2005. ACM.[2] R. J. Aumann. Agreeing to disagree. Ann. Statist.,
4(6):1236--1239, 11 1976.25
Monetization of Development Tools for Fun and
2
Profit
Albin Eldstal-Damlin ˚ Your Company Here Reasonable rates apply
albin@legit.name
Abstract---In this paper we propose methods and strategies to raise
profit from freely available and open-source development toolchains such
as GCC. We illustrate techniques to maximize player developer
engagement and drive further purchases once the system is in place.
Index Terms---monetization, microtransactions, free-to-play,
gamification
# i n c l u d e \<v e ct o r > # i n c l u d e \<al g o rit h m >
u si n g s t d : : v e c t o r ; u si n g s t d : : f i n d ;
i n t main ( )
{
i n t a ;
Typeset using LATEX-Gold free trial
I. INTRODUCTION
In the past decade, monetization of free content has become a leading
business strategy for companies in a range of tech industries such as
computer games and mobile apps. A wide variety of techniques have been
developed and refined to drive users to continuously pay for additional
content, either
v e ct o r \< v e c t o r \<i n t > > v ;
v e ct o r \< v e c t o r \<i n t > >:: c o n s t i t e r a t o r i
t = s t d : : f i n d ( v . b e gi n ( ) , v . end ( ) , a ) ; }
Listing 1. A program with confusing errors
~Visit http://www.latex-gold.or~g
in a storefront fashion or using a more randomized "loot box" approach.
This has caused a surge of "Freemium" titles, requiring no up-front
purchase and recouperating development costs by selling in-game items.
A previously untapped market segment is that of software development
tools, such as compilers, static analysis tools, debuggers, etc. Many
of these are available either free of charge or under an open-source
license, making them perfect candidates for freemium-style
monetization.
In this paper, we examine g++, the C++ compiler of the GNU Compiler
Collection (GCC). Consulting its manual [1], we find that the standard
distribution comes with an ample selection of options and switches; this
suggests that there is room for expansion.
We explore the possibilities of adding microtransactions to the g++
frontend.II. USER MOTIVATION
The first problem is convincing the user to enter the ecosys tem, taking
the step from Libre to Freemium. To entice, we must introduce a killer
feature that is not available elsewhere. What sets a killer feature
apart from a regular feature is that the killer feature is unique and
indispensable. This feature can be entirely cosmetic (such as a novel
output decoration), but it is preferable to give the user some
qualitative improvement. To come up with such a feature, we identify a
common problem users have with our chosen product and devise a solution.
In the case of g++, a common complaint is the verbosity and obscurity
of some error outputs. In many small- and mid sized codebases, a typo
can lead to error messages exceeding the size of the code!
Furthermore, it isn't always clear to thenovice programmer what the cause is of these pages of output. Listing
1 shows an example of an STL type error [2], with the full error
message from g++ in appendix A.A good candidate for a killer feature, then, is error output of
improved quality, readability and accuracy. The implemen tation of
such a feature is beyond the scope of this article.
III. INTERMISSION
If you have a software project, monetization effort or just want to
show off pictures of your cats to the world, you need a website. Don't
have any coding skills? Don't know where to start? Check out
SquarePeg, one of the world's leading providers of all-in-one web
hosting solutions. SquarePeg lets you effortlessly create your site
using one of four beautiful templates. It's as easy as drag-and-drop.
Almost nothing to install, almost nothing to update, almost ever!
Visit http: //www.squarepeg.com/sigbovik for 20% off your first
purchase today!
IV. IN-TOOL CURRENCY
A key technique to drive purchases is an intermediate single purpose
currency, which can either be earned by using the tool or directly
purchased for real-life money. Such a currency serves to disconnect
the actual cost of offered add-ons from the apparent cost, in addition
to locking in a greater amount of real-world money by inconvenient
exchange rates.In our examples, we introduce the g++-specific "L2 Cash" (L$) and
present all purchase options to the user (except for L$ itself) in
L$.The user is rewarded in small amounts of L$ for various normal use of
the software (for example 1L$ per 10 seconds6
spent compiling code) as well as extraordinary achievements (compile
with substantial changes without errors on the first try? 1L$ per 10
lines of code!).
Another avenue for monetization is to sell ad-space and reward the user
for being exposed to advertising. Targeting g++ opens the
non-traditional option of modifying the stan dard library, for example
by randomly including advertising in printf() output in exchange for
L$.
V. SUITABLE FEATURES
Traditionally, premium add-ons can be divided into three categories
along a spectrum: Cosmetic, Convenience and Pay to-Win. The special
nature of a compiler also offers a fourth option which is useful to
us: Non-standard language features.
Cosmetic features do not alter the user's experience, only the apperance
of some elements. In an online game, this may be a special player avatar
or some rare piece of equipment that nevertheless does not afford the
player any advantage. There are relatively few possibilities for a
purely cosmetic add-on to a productivity tool such as a compiler.
Convenience features can automate or simplify otherwise tedious tasks,
saving the user time but not otherwise providing any competitive edge.
An example might be automation of grinding, mindless mass-production
work. In a development setting, this is akin to well-crafted
preprocessor macros and automatic generation of boilerplate code.
Pay-to-Win features directly improve a user's chance of success. In a
competitive game, this may be a stronger weapon or a higher-capacity
backpack. These features are generally ill received, as they are
perceived to throw off the balance of the game. Since development tools
are usually single-player, or cooperative multiplayer, these features
are better thought of as productivity-enhancements.
Non-standard language features offer an avenue for lock in, by luring
the user into writing programs that will not work without our premium
add-ons. This is ideal for monetization, and a particularly good feature
could even warrant recurring payment. We will also exploit features like
this for licensing reasons, detailed in Section VII.
VI. USER INTERFACE
The most obvious way to expose new extensions to the user is via
command-line switches. We use the + prefix to show features that can
be purchased, together with their price.albin@SquarePeg:∼$ g++ --help
Usage: g++ [options] file...
Options:
...
-pass-exit-codes Exit with highest error code from a phase
Premium Features:
+nice-errors Provide human-readable output (500L$)
A common optimization is to sneak the premium options in among the
free ones, to make them more difficult to ignore.albin@SquarePeg:∼$ g++ --help
Usage: g++ [options] file...
Options:
...
-pass-exit-codes Exit with highest error code from a phase
+nice-errors Provide human-readable output (500L$)
To drive conversion rate, however, it is useful to advertise the
available options more strongly. A color hint is a good start.albin@SquarePeg:∼$ g++ --help
Usage: g++ [options] file...
Options:
...
-pass-exit-codes Exit with highest error code from a phase
+nice-errors Provide human-readable output (500L$)
At the end of every output, we append the user's current account
balance. This provides a reminder that the player is earning while
they play. Of course, we also remind them how to easily increase their
account balance.albin@SquarePeg:∼$ g++ --help
Usage: g++ [options] file...
Options:
...
-pass-exit-codes Exit with highest error code from a phase
+nice-errors Provide human-readable output (500L$)
Balance: 1210L$
+cash=[amount] Add additional L$ to account ($2.99 / 100L$)
Another well-known strategy is to provide tiered pricing, i.e. a
better exchange rate for bulk currency purchase. By identifying
beginners (more likely to make small purchase) and power-users (more
likely to make bulk purchases), we can gently nudge them toward a
transaction.albin@SquarePeg:∼$ g++ --help
Usage: g++ [options] file...
Options:
...
-pass-exit-codes Exit with highest error code from a phase
+nice-errors Provide human-readable output (500L$)
Balance: 10L$
+cash=100 Additional 100L$ to account ($2.99)
+cash=1000 Additional 1000L$ to account ($25.99) \<- Most
popular +cash=5000 Additional 5000L$ to account ($39.99)+cash=10000 Additional 10000L$ to account ($69.99) \<- Best deal
VII. SKIRTING OPEN-SOURCE LICENSING
g++ is released under the GNU General Public License (GPL), which
requires that any modification or addition is also released under the
same license. To counteract this, we devise a strategy for compliance
with the letter of the license while side-stepping the spirit.By ensuring that our premium features are implemented with heavy
reliance on our own non-standard language fea tures, we prevent the
spread of our proprietary modules to non paying users. By extension,
if we also hide the documentation of these non-standard features
behind our pay-wall, we inhibit non-paying users trying to port the
released source code to free tools.
REFERENCES
[1] G. Project, "Gcc manual: Invoking gcc."
https://gcc.gnu.org/onlinedocs/
gcc-8.1.0/gcc/Invoking-GCC.html#Invoking-GCC, 2018.[2] Kebs, "Code golf entry."
https://codegolf.stackexchange.com/a/10470, 2016.7
APPENDIX A
TYPICAL G++ OUTPUT
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s t l a l g o b a s e . h : 7 1 : 0 ,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l i t e r
a t o r . h : 8 6 6 : 5 : n ot e : t e m p l a t e a r g um e nt d e d
u c t i o n / f rom / u s r / i n c l u d e / c++ / 7 . 3 . 1 /
v e c t o r : 6 0 ,s u b s t i t u t i o n f a i l e d :
f rom e x pl o d . cpp : 1 :
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s t l a l g o b a s e . h : 7 1 : 0 ,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / p r e d e f i
n e d o p s . h : I n i n s t a n t i at io n o f ' b o ol gnu
cxx : : o p s : :f rom / u s r / i n c l u d [e]{.underline} / c + + / 7 . 3 . 1 / v e
c t o r : 6 0 ,I t e r e q u a l s v a l \< Value >:: o p e r a t o r ( ) ( I t e r
a t o r ) [ wit h I t e r a t o r = gnu cxx : :f rom e x pl o d . cpp : 1 :
n o r m a l i t e r a t o r \<s t d : : v e ct o r \<i n t >*,
s t d : : v e ct o r \<s t d : : v e ct o r \<i n t > > >; Val ue =
c o n s t i n t ] ' :[/]{.underline} u s r / i n c [l]{.underline} u d e / c + + / 7 . 3 .
1 / b i t s / p r e d e f i n e d o p s . h : 2 4 1 : 1 7 : n ot e : '
s t d : : v e c[t]{.underline} o r \<i n t >' i s n ot d e r i v e d
/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l a l g o
. h : 1 2 0 :14 : r e q u i r e d f rom ' R a n d o m A c c e s
s It e r at o r s t d : :f rom ' c o n s t gnu cxx [:]{.underline} : n o r m a l i t e r a t o
r \< I t e r a t o r , C [o]{.underline} nt ai n e r >'
- f i n d i f ( R a n d om
Ac c es sIt e r ato r, R a ndom A c c e s sI~~t e r at o r , P ~~re d i c a t e , s t d- :
{ r [e]{.underline} t u r [n ]{.underline}* i t == M value
; }r a n d o m a c c e s s
it e r a t o r tag ) [ wit h R a n
d o m A c c e s s It e r at o r = gnu cxx : : n o r m a l i t e r a t
o r \<s t d : :˜ ˜ [˜]{.underline} ˜ ˜ ˜ ˆ ˜ ˜ ˜ [˜]{.underline} ˜ ˜ ˜ ˜ ˜ ˜
v e ct o r \<i n t >*, s t d : : v e ct o r \<s t d : :
v e ct o r \<i n t > > >; P r e d i c a t e = gnu cxx : : o p s : :
- I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
- . 3 . 1 / x8[6]{.underline} 64−pc−li n u x [−g]{.underline}nu /
- [b]{.underline} i t s / c[++]{.underline} a l l o c a t o r . h : 3 3
- 0 , / u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / p r e d
e f i n e d o p s . h : 24 1: 1 7 : n ot e : mi s~m~atc he
dt y p e s ' c o n s t s t d : : v e ct o r I t e r e q u a l s v
a l \<c o n s t i n t >] 'f rom / u s r / i n c l u d e / c + + /
7. 3 . 1 / b i t s / a l
l o c a t o r . h : 4 6 ,\< [T]{.underline}p , All oc >' and ' c o n s t i n t '
I n f i l e i n [c]{.underline} l u d
e[d]{.underline} f rom / u
s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l a l g o b a
s e . h : 7 1 : 0 ,/ u s r / i n c l u d e
/c + +/ 7. 3 . 1 / b i t s / s t l
a l g o . h : 1 6 1 : 2 3 : r e q u i r [e]{.underline} d f rom ' I t
e r a t o r s t d : : f i n d i f ( f rom / u s r [/]{.underline} i n
c l u d e / c + + / 7 . 3 . 1 / v e c t or: 6 1 ,/ u s r
/i n c l ude / c + + / 7 . 3 . 1 /bi t s / s
t l i t e r a t o r . h : 1 1 2 4: 5: n ot e :ca n d i d a
t e : t e m p~~l a~~t e \<cla s s I t e r a t o r >
{ r e t u r n * i t == M v~a~lue ; }[f ro]{.underline}m / u [s r]{.underline} / [i]{.underline} n
cl
u d e / c++ / 7 . 3 . 1 / v e c t o r : 6 0 ,I t e r a t o r , I t e
r at o r , P red i c a t e )[ct o r f rom e x ~p~l o d . cpp : 1 :
w~~it h I t e r a t o r = gnu cxx : : n o r m a l i t e r a t o r \<s
t d : : v ~~eb o ol s t
d :: o p e r ato r== ( c o n s t s t d : :
m o v e i t e r a t o r\<I t era t o r L>&, c o n s
ts t d : : m o v e i t e r a t o r \< ˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜˜˜ ˜
˜ ˜ ˜ ˜ ˜f rom e x ~p~l o d . cpp : 1 :
\<i n t >*, s t d : : v e ct o r \<s t d : : v e ct o r \<i n
t > > >; Pre d i c a t e = gnu cxx : : o p s : : I t e r e q
u a lsv a l \< / u s r / i n [c]{.underline} l u d e / c + + / 7
. 3 . 1 / e x t / n e w a l l o c a t o r . [h]{.underline} : 1 5 5 :
5 : n ot e [:]{.underline} c a n [d]{.underline} i d a t e
[:]{.underline} t e m pl [a]{.underline}t e \<c [l]{.underline} a s s
[Tp]{.underline}> b o ol I t e r a t o r L >&)I n f i l
ei n c l u d e d f rom / u s r / i n clu d e
[/]{.underline} c + + / 7.3 . 1 / v e c t o r : 61 :0 ,
- / u s r / i n c l u
de / c + + / 7 . 3 . 1 / b i t s / p r e d e- f
i ne d o p s . h: 24 1 : 1 7 : n ot e:'st d :- v
e c~~t o r \<i n ~~t>'is n o~~t d~~ e r i v e d c o n
s t i nt>] 'gnu cxx : : o p e r a t o r == ( c o n [s]{.underline} t g~n~u
c[x]{.underline}x : : n e w a l l [o c]{.underline} a t o r \<
[T]{.underline}p>&, c o n s t gnu cxx : : n e w a l l o c a t o r \<
o p [e]{.underline} r a t o r == ( c o n s t m o v e i t e [r
a]{.underline} tor \< I t e r a t o r [>]{.underline}& x ,f rom e x [p]{.underline}l o d
.cpp:1 [:]{.underline}f rom ' c o
ns t s t d : : r e v e r s e i t e rat orI
\<t e ra t o r >'/ u s r / i n c l u
d e/ c ++/ 7 . 3 . 1 / b i t s / s t l
a l go. h: 39 [0]{.underline} 7: 28 : r e q u i r
e df rom ' I I t e r s t d :: fi n d(I I t e r , I I
t e r [T]{.underline}p>&)ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
/ u s
r/ i n c [l u d]{.underline} e / c + + [/]{.underline} 7
[.]{.underline} 3 . 1 / bit s / a l l o c a t o r . h : 1 5 2 :
5 : n ot e : c a n d i dat e : t e m pl at e \<c l ass
[T]{.underline}p>bo ol s t d : : { r e t urn *
i t == M value ; }, c o n
s t
Tp[&]{.underline}) [ wit h [I]{.underline} I t e r = gnu cxx : : n o r m a l i t e r a t o r \<s t d : : v e ct o r \<i n t >*,
s t d :: ve ct o r \<s t d o p [e]{.underline} ra to r ==
( con[s]{.underline} tn e w a l [l o]{.underline} c a t [o
r]{.underline} \< [T]{.underline}p[>&]{.underline}, c o n s t n e w a
l l o c a t o r \< [T]{.underline}p>&)/ u s r /
inc l ud e / c ++/7. 3 . 1 / b
[i]{.underline} ts /s t l i t [e]{.underline} r ator
. h : 1 1 2 4 : 5 : [n]{.underline} ot e : t e [m]{.underline} p l a t
e a r g um e nt ded u c t i o n / o per a t o r == ( c o n
st s t d: :al lo c at or\<T~p1~>&, c o
ns t s td: : a l l o c a tor \< Tp1>&)
- ˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜
˜˜ ˜ ˜ ˜: v e ct o r \<i n t > > >; Tp = i n
t] 'ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
s u b s t i t u t i o n f a i l e d :
o p e r a t o r == ( c
on s t a l l o c a t o r \<
[T]{.underline}p>&, c o n s t a l l o [c]{.underline} a t o r \<
[T]{.underline}p>&)I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c
[+]{.underline} + / 7 . 3 . 1 / b i t s / s t l a l g o b a
[s]{.underline} e . h : 6 7 : 0 ,e x pl o d . cpp : 1 2 : 4 2 : r e q u i r e d f rom h e r e
/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / e x t / n e w a l
l
o c a t o r . h : 1 5 5 : 5 :not e : t e m p l a t e a r g um e
nt d e d u c t i o n / I n f i l e i n c l u d e d f rom / u s r / i n
[c]{.underline} l u d e / c + + / 7 . 3 . 1 / b it s/ s t lag o b a s e . h : 7 1 : 0 ,
l
ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
f rom / u s r / i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r : 6
0 ,
/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / p r e d e f i
n edo p s . h : 2 4 1 : 1 7 : e r r o r : n~o~ match f o r ' o
p e r a t o r == ' ( o p e r a n d s u b s t i t u t i o n f a i l e d
:f rom / u s r / i n c l
ud e / c + + / 7 . 3 . 1 / v e c t o r :
6 0 ,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / a l l o
c
a t o r . h : 1 5 2 : 5 : n ot e : t e m p l a t e a r g um e nt d e d
u c t i o n / s u b s t i t u t i o n f rom e x pl o d . cpp : 1 :t y p e s a r e ' s t d : : v e ct o r \<i n t >' and ' c o n s t i n
t ' )I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s t l a l g o b a s e . h : 7 1 : 0 ,
f a i l e d :
f rom e x pl o d . cpp : 1 :
/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l i t e r
a t o r . h : 2 9 9 : 5 : n ot e :ca n d i d a t e : t e m pl at
e \<c l a s s I t e r a t o r > { r e t u r n * i t == M
value ; }f [r]{.underline}om / u s r / i
nc l u d e / c + + / 7
[.]{.underline} 3 . 1 / v e c t o r : 6 0 ,/ u s r /
i nc l u d e /c++/ 7 . 3 . 1 / b i ts
/ p r e d e f i n e d o p s . h : 2 4 1 : 1 7 : n ot e : ' s t d : : v
e ct o r \<i n t>' i s n ot d e r i v e d I n f i lei n c
l u dedfrom / u s r / i n c l u d e / c + + /
[7]{.underline}. 3 . 1 / b i t s [/]{.underline} s t l a l g o b
a s e . h : 7 1 : 0 ,b o ol s
td : : o p e rat or== ( c o n s t s t d : :
r e v e r s e i t e r a t o r \< I t e [r]{.underline} a t o r >&, c
o n s t s t d : : r e v e r s e i t e r a t o r \< ˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜
˜ ˜ ˜ ˜ ˜ ˜ ˜f rom e x pl o d [.]{.underline} cpp : 1 :
f rom ' c o n s t s t d : : m o v e i t e r a t o r \< I t
er a t
o r L >'
I t e r a t o r >&)
f rom / u s r / i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r : 6
0 ,
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e
/c + +
/ 7 . 3 .1/ b i t s / s t l a l g o b a s e . h : 6 7 : 0 ,
- /
us r / i n c l u d e / c [+ +]{.underline} / 7 . 3 . 1- [/]{.underline} b i [t]{.underline} s / p r e d e f i n e d o p s . h
- 2 4 [1]{.underline} : 1 7 : n ot e : ' s t d : : v e ct o r \<i n t
>' i s n ot d e r i v e d { r e t u r n * i t == M value ;
}f rom e x
p[l]{.underline} o d . cpp : 1 :o p e r a t o r == ( c o
n st r e v ersei t e r a t o
r \< Ite r a t o r >& x ,f rom / u s r / i
nc lu[d]{.underline} e / c + + / 7 .
[3]{.underline} .1/ v e c t o r : 6 0 [,]{.underline}f rom ' c o n s t gnu cxx :
:n e w a l l o cat o r \<
[T]{.underline}p>'˜ ˜ ˜ [˜ ˜]{.underline} ˜ ˆ ˜ [˜]{.underline} ˜ ˜ ˜ ˜
˜˜ ˜ ˜/ u s r / i n c l u d e / c +
+ /7 . 3.1 / b i t s / p r
ed e f i n e d o p s . h : 2 4 1 : 1 7 : n ot e : ' s t d : : v e
ct o r \<i n t >' i s n ot d e r i v e d
ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
f rom e x pl o d . cpp : 1 :
{ r e t u r n * i t == M value ; }
I n f i l e i n [c]{.underline} l [u]{.underline} d e d f
r[o]{.underline}m / u s r / i n c l u d e / c ++/ 7 . 3 . 1 / b
i t s / s t l a l g o b a s e . h : 6 7 : 0 ,f rom ' c
o ns t s t d:: all o c a [t]{.underline} o
r \< Tp1>'/ u s r / i n c l u d e / c +
+ / 7. 3 . 1 /bi ts/ s
t l i t e r [a]{.underline} t o r . h : 2 9 9 : 5 : n ot e :t em
p l a t e a r g um e nt d e d u c t i o n / / u s r / i n c l u d e /
c + + / 7. 3. 1 / b i ts/st l i [t e]{.underline} r
a tor . h : 8 5 9 : 5 : n ot e : c a n did a t e : t e m
pl at e \<c l a s s I t e r a t o r L , ˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
[˜]{.underline} ˜f rom / u
sr/i n cl ud e / c + + / 7 . 3 . 1 / v e c
t o r : 6 0 ,{ r e t u r n * i t == M v~a~lue ; }
s u b s t i t u t i o n [f a]{.underline} i l e d :
c l a s s I t e r a t o r R
,c l a s sCo nt ai n e r > b o
ol gnu cxx : : o p e r a t o r == ( c o n s t gnu cxx : : I n f i [l
e]{.underline} i n c l u de df rom / [u]{.underline}sr / i
n c l u d e / c + + / 7 [. 3]{.underline} . 1 / [v]{.underline} e c t
o r : 6 4 : 0 ,f ro~~m e~~ x pl o d . cpp : 1 :
˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜
˜˜ ˜ ˜ ˜ ˜
- I n f i l e
i nc l u d e d f rom / u s r/i n c l u d e /- c + + / 7 . 3 .
1 /b i ts/ s t l a l g o b a s e . h : 7 1- 0 ,
n o r m a l i t e r a t o r \< I t e r a t o r L , C o nt ai n e r
>&, c o n s t gnu cxx : : n o r m a l i t e r a t o r \< I t e r a t
o r R , [f r]{.underline}om e x pl o d . [c]{.underline}pp :
[1]{.underline} :/ u s r /
i nc l u d e / c ++/ 7 . 3 . 1 / b i t s/s
t l i t e r a t o r . h : 1 1 1 8: 5: no~~t e : c ~~a nd i
d a t e:t e m pl at e\<~~c l a s s I t e r a t o r L , I n fc l u d
i l e i n c l u d e d f rom / u s r / i ~~ne/ c + + /
7 . 3 . 1 / v e ct or : 61: 0 ,
C o nt ai n e r >&)
- f rom / u s r / i n c l u d
e/ c++ / 7 . 3 . 1 / v e c t o r - 6
0,
- / u s r / i n c l u d e / [c]{.underline} + + / 7 . 3 . 1 / b i t s /
- s t l v e c t o r . h : 1 5 9 6 : 5 : n ot e : c a n d i d
- [a]{.underline} t e : t e m p[l a]{.underline}t e \<c l a s s
- [T]{.underline}p , c l a s s c l a s s I t e r a t o r R > b o ol s t
- [d]{.underline} : : o p e r a t o r == ( c o n s t s t d : : m o v e i
- t e r a t o r \< I t e r a t o r L >[&]{.underline}, c o n s t s t d
- : f rom e x pl o d . c~p~p : 1 :
f rom e x pl o d . cpp : 1
:o p e r a t o r == ( c o
ns t n o r m a l i t e r at or \<
I t e r a t o r L , C o nt ai n e r>&lh s ,All oc> b o ol [s t]{.underline} d [: :]{.underline} o p e
[r]{.underline} a t o r == ( c o [n]{.underline} s t s t d : : v e
c[t]{.underline} o r \< [T]{.underline}p , All [oc]{.underline} >&, c
o n s t s t d : : v e ct o r \< [T]{.underline}p , All oc m o v e i t
e r a to r\< I t e r ato r R >&)/ u s
r/ i n c l u de/ c + +/ 7. 3 . 1 / bit s
/ a l l o c a[t]{.underline}o r . h : 1 4 6 : 5 : n ote: c
and i da te : t e m pl at e \<c l a s s [T]{.underline}1 ,
c l a s s [T]{.underline}2> / u s r / i n clu d e / c + + / 7 .
3. 1/ bit s / pre d e f i n e dop s . h : 2 4
1 : 17: n o~t~ e : ' st d: : v e ct o r \<i n t >' i s
n ot der i v edˆ ˜ ˜ ˜ ˜˜˜ ˜
>&)
o p e r a t o r == ( c o n s t m o v e i t e r a t o r \< I t e r a
t o r L >& x ,
b o ol s t d : : o p e r a t o r == [(]{.underline} c o n
st s t
d [:]{.underline} : al lo c a t o r \< Tp1~>&~, c o n s t s t
d : : a l l o c a t o r \< [T]{.underline}2>&) f rom ' c o n s t s t
d : : r e v e r s e i t e rat o r \< I t era t o r >'/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l i t e
ra t o r . [h]{.underline} : 859 : 5 : n ote:te
m p l a t e a r g um e nt d e d u c tio n / o p e r a t o r == (
c o n s t v e c~~t [o]{.underline}~~ r \< [T]{.underline}p ,A~~ll)
oc>& x , c o n s t v e ct o r \< [T]{.underline}p , All oc>& ~~yˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
o p e [r a]{.underline} t o r == ( [c]{.underline} o [n]{.underline} s
t a l loc at or \< [T]{.underline}1>&, c o ns ta l
l o c a t o r \< [T]{.underline}2>&){ r e t u r n * i t == M value ; }
s u b s t i t u t i o [n]{.underline} f a i l e d :
ˆ ˜ ˜ ˜
˜ ˜ ˜˜/ u s r / i n
c l ud e / c ++/7. 3 . 1 / b i t s / s
t l i t e r a t o r . h : 1 1 1 8 : 5 : n ote: t e m p l a t e a
r g um e nt d e d u c t i o n / ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + +
/7 . 3 . 1 / b i t s / s t l a l g o b a s e . h : 7 1 : 0 ,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l v e c t
o r . h : 1 5 9 6 : 5 [:]{.underline} n ot e : t e m p l a t e a r g
um e nt d e d u c t i o n / s u b s t i t u t i o n f a i l e d :/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / a l
lo c
a t o r . h : 1 4 6 : 5 : n [ot]{.underline} e : t e m p l a t e a r g
um e nt d e d u c t i o n / s u b s t i t u t i o n I n f i l e i n c
l u d e d f rom / u s r / i n c l u d e/c + + / 7 . 3 . 1 / b i
t s / stl a l g o b a s e . h : 6 4 : 0 ,f rom / u s r / i n c l u d e / c
++ / 7 . 3 . 1 / v e c t o r :
6 0 ,s u b s t i t u t i o n f a i l e d :
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b it s/ s t l a l g o b a s e . h : 7 1 : 0 ,
f a i l e d :
f rom / u s r / i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r : 6 0 ,
f rom e x pl o d . cpp : 1 :
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s t l a l g o b a s e . h : 7 1 : 0 ,f rom / u s r / i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r
[:]{.underline} 6 0 ,I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s tla l g o b a s e . h : 7 1 : 0 ,f rom e x pl o d . cpp : 1 :
/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / p r e d e f i
n e d o p s . h : 2 4 1 : 1 7 : n ot e : ' s t d : : v e ct o r \<i n
t >' i s n ot d e r i v e d f rom / u s r / i n c l u d
[e]{.underline} / c + + / 7 . 3 . 1 / v e c t o r : 6 0,f rom e x pl o d . cp~p~ : 1 :
f rom / u s r / [i]{.underline} n c l u
de / c + + / 7 . 3 . 1 /
v e c t o r : 6 0 ,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l p a i r
.h : 4 4 3 : 5 : n ot e : c a n d i d a t e : t e m pl at e \<c l
a s s [T]{.underline}1 , c l a s s [T]{.underline}2> f rom ' c o n s
t gnu cxx : : n o r m a l i t e r a t o r \< I t e r a t o r L , C o
nt ai n e r >'f rom [e x]{.underline} pl o d
.cp[p]{.underline} : 1 :
- / u s r / i n c l
u de / c++ / 7 . 3. 1/ b i ts- / p r e d e f i n e d o p s . h : 2 4 1 : 1
7: n ot e : ' s t d :- v e ct o r
\<~~i n t >' i s n ~o~t d e r i v e d f rom ~~ex
pl o d . c~p~p : 1 :c o n s t e x p r
b oolst d : : op er a t o r ==
(c o n s t s t d : : p a i r \< [T]{.underline}1 ,
[T]{.underline}2>&, c o n s t s t d : : p a i r \< [T]{.underline}1 ,
[T]{.underline}2>&) { r e t u r n * i t == M value ; }f
rom' c o n s t s t d : : m o v e i t e r a t o r \< I t e r a t
o r L >'/ u s r / i
n cl u d e / c++/7 . 3 . 1 /
[b]{.underline} i t s/[p]{.underline} r e d e f [i
n]{.underline} edo p s . h : 2 4 1 : 1 [7]{.underline} : n
o[t]{.underline} e : [' s]{.underline} t d : : v e ct o r \<i n t >'
i s n ot d e r i v e d o p e r ator== ( c ons t p a
i r \< [T]{.underline}1 , [T]{.underline}2>& x,c o n s t p a i
r \< [T]{.underline}1 , [T]{.underline}2>& y )˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
{ r e t u r n * i t == M valu~e~ ; }
f rom ' c o n
s ts t d : :al loc a t o r \< Tp1>'ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
I n f i l e i n c l u d e d f rom / u s r / i
nc lud e /
c + + / 7 . 3 . 1 / b i t s / s t l a l g o b a s e . h : 6 7 : 0 ,˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
{ r e t u r n * i t == M valu[e]{.underline} ; }
/ u s r / i n c l u d e / c + + [/]{.underline} 7 . 3 . 1 / b [i
t]{.underline} s [/]{.underline} s t l p a i r . h : 4 4 3 : 5 : n ot
e : t e m p l a t e a r g um e nt d e d u c t i o n / s u b s t i t u
t i o n f ro~m~ / u s r /inc lu d [e]{.underline} /
c + + / 7 . 3 . 1 / v e c t o r : 6 0 ,I n f i l e i n c l
u de d f ro~~m /~~ u s r/i n c l u d e
/ c + + / 7 . 3 . 1 / b i t s / s t l a l g o b a s e . h : 6 7 : 0 ,
f a i l e d :
˜ ˜ ˜ ˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
f rom e x pl o d . cpp : 1 :
f rom / u s r / i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r : 6 0 ,
I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s [/]{.underline} s t l a l g o b a s e . h : 6 7 : 0
,I n f i l e i n c l u d e d f rom / u s r / i n c l u d e / c + + / 7
. 3 . 1 / b i t s / s t l a l g o [b]{.underline} a s e . h : 7 1 : 0
,/ u s r / i n c l u d e / c + + / 7 . 3 . 1 / b i t s / s t l i t e r
a t o r . h : 8 6 6 : 5 : n ot e : c a ndi d a t e : t e m pl at
e \<c l a s s I t e r a t o r , f rom e x ~p~l o d . cpp : 1 :f rom / u s
r/ i n c l u d e / c + + / 7 . 3 . 1 / v e c t o r :
6 0 ,f rom / u s r / i n
cl u d e / c + + / 7 . 3 . 1 / v e c t o r :
6 0 ,c l a s s C o nt ai n e r > b o ol gnu cxx : : o p e r a t o r == ( c
o n s t gnu cxx : : n o r m a l i t e r a t o r \< I t e r a t o r , /
u sr/ i n c l u d e / c + + / 7 . 3. 1/ b its / s t
l i t e r a t o r . h : 3 3 7 : 5:n ote: c a nd id a
t e : tem pl at e \<cla s s I t e r a t o r L , f rom
ex plod . cpp:1 :f rom e x p~~l o d~~ . c~pp~ : 1 :
C o nt ai n e r >&, c o n s t gnu cxx : : n
or m a l i t e r a t
o r \< I t e r a t o r , C o nt ai n e r >&)c l a s s I t e r a t o
r R>bo ol st d: : o p e r
at o r == ( c o nst s t d : : r e ver s e i t e r a t
o r \< I t e r a t o r >&, c o n s t s t d : : / usr / i n c l
u d e / c + +/7 . 3 . 1/ bi t s/p r e d ef i n
e d o p s.h : 2 4 1 : 1 7:n ot e : 'st d : :ve
ct o r \<i n t>' i s n ot d e r i v e d o p e r a t o r == ( c o
ns t n o r m a l i t e r a t o r \< I t e r a t o r , C o nt ai n
e r>& l h s,r e v e r s e i t e
r at o r \< It er a t o r R >&)f rom ' c o n s t s
td :: pa i r \< ~[T]{.underline}~1 ,
[T]{.underline}2>'
ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
o p e r a t o r == ( c o n s t r e v e r s e i t e r a t o r \< I t
e r a t o r L >& x , ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜
{ r e t u r n * i t == M value ; }
- / u s r / i n [c l u]{.underline} d e / c + [+]{.underline} /
- [7]{.underline} . 3 . 1 / b i t s / s t l i t e r a t o r . h : 3 3 7
- 5 : n ot e : t e m p l a t e a r g um e nt d e d u c t i o n / ˜ ˜ ˜
˜ ˜ ˜ ˆ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜s u b s t i t u t i o n f a i l e d :
8
CONFIDENTIAL COMMITTEE MATERIALS
{width="1.000485564304462in"
height="1.000485564304462in"}
SIGBOVIK 2019 Paper Review
Paper 1: Monetization of Development Tools
for Fun and Profit
ReviewIt Free
Rating: [Wait remaining: 2h35m; Reveal Now: [25R$]]{.underline}
Confidence: [Upgrade Your Review Experience With Confidence Levels:
[75R$]]{.underline}This paper has been reviewed using ReviewIt Free, a service of
ReviewIt enterprises. ReviewIt Free provides the same great review
feedback to authors as ReviewIt Enterprise, ReviewIt Premium, ReviewIt
Pro, ReviewIt Gold, and ReviewIt Solid Gold with a few limitations:• first, all reviews begin with this block of text and a short but
mandatory advertisement;• second, authors that wish to immediately view a numerical summary
score of their review can do so for a small micro-payment -- the score
will otherwise be revealed several hours after the review release, but
before the committee needs it to make accept/reject decisions;• third, the reviewer confidence rating is also available for a larger
micropayment.These limitations ensure that ReviewIt enterprises can continue to
provide great reviews to all our customers. We have carefully
considered all of our micropayments and decided that any diffuse
negative influence they may have on the progress of science is
certainly more than made up for by the concentrated positive influence
they have on the balance in our wallets.
+-----------------------------------------------------------------------+
| > Ad-Blocker Detected! No review text displayed. Please disable your |
| > ad-blocker so that we can force you to watch a five minute |
| > edutisement from PraegerU; monthly subscribers don't need to watch |
| > these advertise ments. |
+=======================================================================+
+-----------------------------------------------------------------------+
Hey authors, not happy with your review results? Upgrade your
reviewing experience with these extra features: • Proper grammar,
spelling, and complete sentences. [[100R$]]{.underline}• No statements of opinion couched as fact. [[200R$]]{.underline}
• Sensible feedback that considers that paper authors are people, too,
and are generally making a good-faith effort to move science forward.
[currently unavailable]• Specific, constructive feedback. [[10000R$]]{.underline}
• Re-roll the review hoping for better drops. [submit the paper next
year]9
10
Let's get this party started!
3 Elo World: A framework for benchmarking weak chess engines Dr. Tom
Murphy VII Ph.D.Keywords: pawn, horse, bishop, castle, queen, king
4 A formal treatment of k/n power-hours
Christian Clausen
Keywords: power hour, 2 girls 1 cup, formalized drinking game 5
Eventually consistent partyingVeit Heller
Keywords: party system design, buzz factor, SIGBOVIK
11
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
3
Elo World, a framework for benchmarking weak chess engines
DR. TOM MURPHY VII PH.D.
CCS Concepts: • Evaluation methodologies → Tour naments; • Chess →
Being bad at it;Additional Key Words and Phrases: pawn, horse, bishop, castle, queen,
king
ACH Reference Format:
Dr. Tom Murphy VII Ph.D.. 2019. Elo World, a framework for
benchmarking weak chess engines. 1, 1 (March 2019), 13 pages.
https://doi.org/10.1145/nnnnnnn.nnnnnnn1 INTRODUCTION
Fiddly bits aside, it is a solved problem to maintain a numeric skill
rating of players for some game (for example chess, but also sports,
e-sports, probably also z-sports if that's a thing). Though it has
some competition (suggesting the need for a meta-rating system to
compare them), the Elo Rating System [2] is a simple and e ective
way to do it. This paper is concerned with Elo in chess, its original
purpose.The gist of this system is to track a single score for each player.
The scores are de ned such that the expected outcomes of games can be
computed from the scores (for example, a player with a rating of 2400
should win 9/10 of her games against a playerCopyright © 2019 the Regents of the Wikiplia Foundation. Appears in
SIGBOVIK 19119 with the title in ation of the Association for
Computational Heresy; IEEEEEE! press, Verlag-Verlag volume no.
0x40-2A. 1600 rating points.Author's address: Dr. Tom Murphy VII Ph.D., tom7@tom7.org. 2019.
Manuscript submitted to ACHwith a rating of 2000). If the true outcome (of e.g. a tournament)
doesn't match the expected outcome, then both player's scores are
adjusted towards values that would have produced the expected result.
Over time, scores thus become a more accurate re ection of players'
skill, while also allowing for players to change skill level. This
system is carefully described elsewhere, so we can just leave it at
that.The players need not be human, and in fact this can facilitate running
many games and thereby getting arbitrarily accurate ratings.The problem this paper addresses is that basically all chess
tournaments (whether with humans or com puters or both) are between
players who know how to play chess, are interested in winning their
games, and have some reasonable level of skill. This makes it hard to
give a rating to weak players: They just lose every single game and so
tend towards a rating of −∞.1 Even if other comparatively weak
players existed to participate in the tournament and occasion ally
lose to the player under study, it may still be dif- cult to
understand how this cohort performs in any absolute sense. (In
contrast we have "the highest ever human rating was 2882," and "there
are 5,323 play ers with ratings in 2200--2299" and "Players whose
ratings drop below 1000 are listed on the next list as 'delisted'."
[1]) It may also be the case that all weak players always lose to
all strong players, making it un clear just how wide the performance
gap between the two sets is. The goal of this paper is to expand the
dy namic range of chess ratings to span all the way from extremely
weak players to extremely strong ones, while providing canonical
reference points along the way.1Some organizations don't even let ratings fall beneath a certain
level, for example, the lowest possible USCF rating is 100.12
2 ELO WORLD
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}The player is deterministic
Elo World is a tournament with dozens of computer players. The computer
players include some tradi tional chess engines, but also many
algorithms cho sen for their simplicity, as well as some designed to be
competitively bad.
The fun part is the various algorithms, so let's get into that. First,
some ground rules and guidelines:• No resigning (forfeiting) or claiming a draw. The player will only
be asked to make a move when there exists one, and it must choose a
move in nite time. (In practice, most of the players are extremely
fast, with the slowest ones using about one second of CPU time per
move.)• The player can retain state for the game, and ex ecutes moves
sequentially (for either the white or black pieces), but cannot have
state mean ingfully span games. For example, it is not per mitted to
do man-in-the-middle attacks [4] or learn opponent's moves from
previous rounds, or to get better at chess. The majority of players
are actually completely stateless, just a func tion of type position →
move.• The player should try to "behave the same" when playing with the
white or black pieces. Of course this can't be literally true, and in
fact some algorithms can't be symmetric, so it's, like, a suggestion.• Avoid game-tree search. Minimax, alpha--beta, etc. are the correct
way to play chess program matically. They are well-studied (i.e.,
boring) and e ective, and so not well suited to our prob lem. A less
obvious issue is that they are end lessly parameterizable, for example
the search
13
Traditional approach to chess (e.g. engine) Vegetarian or vegetarian
option available A canonical algorithm!Stateful (not including pseudorandom pool) Asymmetric
Fig. 1. Key
ply; this leaves us with a million things to d dle with. In any case,
several traditional chess engines are included for comparison.2.1 Simple players
random_move. We must begin with the most canoni cal of all
strategies: Choosing a legal move uniformly at random. This is a
lovely choice for Elo World, for several reasons: It is simple to
describe. It is clearly canonical, in that anyone undertaking a sim
ilar project would come up with the same thing. It is capable of
producing any sequence of moves, and thus completely spans the gamut
from the worst pos sible player to the best. If we run the tournament
long enough, it will eventually at least draw games even against a
hypothetical perfect opponent, a sort of Boltzmann Brilliancy. Note
that this strategy actu ally does keep state (the pseudorandom pool),
despite the admonition above. We can see this as not really state but
a simulation of an external source of "true" randomness. Most other
players fall back on making random moves to break ties or when their
primary strategy does not apply.same_color. When playing as white, put pieces on white
squares. Vice versa for black. This is ac complished by counting the
number of white pieces on white squares after each possible move, and
then playing one of the moves that maximizes this num ber. Ties are
broken randomly. Like many algorithms
described this way, it tends to reach a plateau where the metric cannot
be increased in a single move, and
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
the other hand, it does rarely get forced into mating its opponent by
aggressive but weak players.
then plays randomly along this local maximum (Fig ure 2). This
particular strategy moves one knight at most once (because they always
change color when moving) unless forced; on the other hand both bish
ops can be safely moved anywhere when the metric is maxed out.
+-----------------------------------------------------------------------+
| > ^ |
| 0m0s0Z0lZQZ0s0ap0o0o0o0mo0oPo0o0PZPjRZ0ZZPZPZPZN0Z0Z0ZBO^ZNZRZ0ZK |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 2. same_color (playing as white) checkmates
same_color (playing as black) on move 73. Note that since white
opened with Nh3, the h2 pawn is stuck on a black square. Moving the
knight out of the way would require that move to be forced.opposite_color. Same idea, opposite parity.
pacifist. Avoid moves that mate the opponent, and failing that,
avoid moves that check, and failing that, avoid moves that capture
pieces, and failing that, capture lower value pieces. Break ties
randomly. This is one of the worst strategies, drawing against players
that are not ambitious about normal chess pursuits, and easily losing to
simple strategies. On
first_move. Make the lexicographically rst legal
move. The moves are ordered as ïsrc_row, src_col,
dst_row, dst_col, promote_toð for white (rank 1 is
row 0) and the rows are reversed for black to make the strategy
symmetric. Tends to produce draws (by repetition), because knights and
rooks can often move back and forth on the rst few les.alphabetical. Make the alphabetically rst move, using standard PGN
short notation (e.g. "a3" \< "O-O" \< "Qxg7"). White and black both
try to move towards A1.huddle. As white, make moves that minimize the total distance
between white pieces and the white king. Distance is the Chebyshev
distance, which is the number of moves a king takes to move between
squares. This forms a defensive wall around the king (Figure 3).swarm. Like huddle, but instead move pieces such that they are
close to opponent's king. This is es sentially an all-out attack with
no planning, and manages to be one of the better-performing "simple"
strategies. From the bloodbaths it creates, it even manages a few
victories against strong opponents (Figure 4).generous. Move so as to maximize the number of opponent moves that
capture our pieces, weighting by the value of the o ered piece (p = 1,
B = N = 3, R = 5, Q = 9). A piece that can be catpured multiple ways
is counted multiple times.no_i_insist. Like generous, but be overwhelm ingly
polite by trying to force the opponent to accept the gift of material.
There are three tiers: Avoid at14
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
+-----------------------------------------------------------------------+
| > |
| 0ZrZ0Z0sZ0Z0ZnZ00o0Z0ZpZmPZ0Z0Zp0Opj0Z0OZ0MPSNO00aROPO0ZZ0AQJBZ0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 3. huddle (white) checkmates pacifist on move 158 with
substantial help. Note that white's distal pawns have advanced; these
are actually the same distance from the King as they would be in their
home row, since the distance metric includes diagonal moves.
all costs mating the opponent (and moreso check mating). Stalemate is
polite, but it is more canonical for two polite players to form a draw
by repetition, from continually o ering up material to one another and
declining it. Next, avoid situations where the op ponent can refuse our
gift; among these, prefer the move where the opponent must capture the
highest value piece. Finally, prefer moves where the expected value of
the o ered material (i.e. against random play) is highest. (This means
that if there are three moves, and one captures a rook but the others
cap ture nothing, the value is 5/3.) This strategy almost never wins,
but is not among the worst players, since it often forces a draw by
exchanging all its pieces.
reverse_starting. This player thinks that the board is
upside-down, and as white, tries to put its pieces where black pieces
start. Since here we have a speci c con guration in mind, we can
produce a
15
+-----------------------------------------------------------------------+
| > |
| rmblka0sopZpopZp0Z0Z0Z0oZBo0Z0Z00Z0OnO0ZZ0Z0Z0Z0POPZ0ZPOSNZQJ0MR |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 4. swarm (white) vs. stockfish1m_r4096 with black to
move a er 1. d4 Nf6 2. Bh6 gxh6 3. f4 c5 4. e4 Nxe4 5. Bb5. Black
blunders 5. . . f6??, which must have been a random move as swarm
immediately wins with 6. Qh5++.distance metric by computing the total distance from each piece to its
desired destination. Each piece uses a di erent distance metric;
Chebyshev distance for the King, Manhattan distance for the Rook, and
a pretty weird function for the Knight [3]. Trying to move the
pieces into the reversed starting position often causes some con ict
since the black pieces are already there, but can also end peacefully
(Figure 5).cccp. Prioritize moves that Checkmate, Check, Cap ture or Push, in
that order. Push means to move pieces as deep as possible into enemy
territory (without any regard for their safety). Ties are broken
deterministi cally by the source/destination squares, so this one is
technically asymmetric. За здоровье!suicide_king. Take a random move that mini mizes the distance
between the two kings. Putting
+-----------------------------------------------------------------------+
| > |
| 0MBZKZ0SZ0Z0Z0Z00Z0Z0Z0ZZ0Z0Z0Z00Z0Z0Z0ZZ0Z0Z0Z00Z0Z0ZpZsnaqjbm0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
+-----------------------------------------------------------------------+
| > |
| rZbl0ansopopZpZp0ZPL0Z0ZZ0Z0Z0Z00ZkZ0Z0ZZ0Z0Z0Z0POPZPOPOSNZ0JBMR |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 5. reverse_starting draws against itself by repeti tion,
both players having happily moved their surviving pieces into the
correct spots.one's king out in the open is very unprincipled (Fig ure 6), but it
does produce enough pressure to win against unambitious opponents.
sym_mirror_y. As white, try to maximize symme try when
ipping vertically. Zero penalty for oppos ing e.g. a k
with a K, but a small penalty when the pieces are not the same
type, and a larger penalty when they are not opposite colors. The
starting posi tion is already symmetric this way, so this usually has
the e ect of copying the opponent's moves when pos sible. As "copy your
opponent's moves" is a common (but underspeci ed) strategy discovered by
many children, this player is close to being canonical. How ever, it
admits a bit too much arbitrary choice in the penalties assigned.
sym_mirror_x. As sym_mirror_y, but maximize
symmetry when ipping horizontally. This does not make much chess
sense, but can produce aesthetic arrangements.Fig. 6. suicide_king (black) dramatically failing against
cccp's slightly more principled play, a er 1. d4 g5 2. Bxg5 Nc6 3.
Bxe7 Kxe7 4. d5 Kd6 5. dxc6+ Kc5 6. Qd6+ Kc4. White delivers a
discovered mate with 7. e4++.sym_180. As sym_mirror_y, but maximize symme try
under 180° rotation of the board (Figure 7). An emergent priority is
to "castle" with the king and queen to " x" them.min_oppt_moves. Take a move that minimizes the number of
resulting legal moves for the opponent, breaking ties randomly. This
is a beautifully simple approach that generalizes many chess
principles: Oc cupying space reduces the destination squares avail
able to the opponent; capturing their pieces reduces the number of
their pieces that they can move; pin ning pieces or checking the king
further reduces the legal moves; and mating the opponent is the best
possible move.2 Among the players in the paper, this one is Pareto e
cient in terms of its simplicity and e ectiveness.2However note that it does not distinguish checkmate and stale mate,
despite these having very di erent results.16
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
height="0.7499518810148731in"}safe. This strategy moves pieces
towards squares
+-----------------------------------------------------------------------+
| > |
| 0ZbjrZ0ZZ0Z0Z0Z0nZrZpopoZPopL0ZPNZ0APOPZZPOPZRZN0Z0Z0Z0ZZ0ZRJBZ0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 7. sym_180 (white) vs. pacifist a er 66 moves. Note that the
position is not quite rotationally symmetric, but is close given the
material.
equalizer. Prefer to move a piece that has been moved the fewest
times, and then prefer moving to a square that has been visited the
fewest times. Castling counts as moving both the king and rook, and
visiting both destination squares. This is the rst strategy described
that keeps meaningful state.2.2 Fate-based players
If we keep state, then we can track the location of each piece as it
moves around the board (allowing us to distinguish the two rooks, or
follow a pawn as it promotes). We can then use statistics on the average
fates of each piece over hundreds of millions of games to guide the
moves. These statistics give us, for each piece (e.g. the c2 pawn) and
square, how likely it is to end the game on that square, and how likely
it is to be alive or dead there when the game ends [5].
17
where they are likely to end the game alive. For this strategy and
several others, simply moving to maxi mize this score (e.g. its sum or
product over all pieces) is very boring, since the score is almost
always max imized in the starting position. So this strategy ac tually
makes each move randomly, weighted by the total score of the resulting
positions. The scores are normalized (with the lowest-scoring move
receiving weight 0.0 and the highest 1.0) and then sampled ac cording
to these weights. Without normalization, the play is almost identical
to uniformly random, since the weights of the resulting positions tend
to be very similar (dominated by the many pieces that don't move). But
it's pretty arbitrary.popular. Like safe, but the score for a piece/square pair is the
probability that the piece ends on that square, whether it lives or
dies. This player likes to follow the crowd!dangerous. The dual of safe; the score is the prob ability that
the piece dies on that square. Note that a king is said to die if it
is checkmated or his side resigns. This player likes to live life on
the edge!rare. The dual of dangerous; the score is one mi nus the
probability of ending the game on that square. This player has a
thirst for adventure!survivalist. Like the above, but the score is the ratio of the
survival and death probabilities on the square. In the data set, every
piece ends alive or dead in every square (except for the bishops,
which can only legally occupy squares of their color) at least 1000
times, so each ratio is de ned. Here, the sums of ratios have plenty
of variability, and the highest ratios are not so often on the
starting squares. So with this strategy, we simply do a weighted
sample
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
from the moves according to their (non-normalized) scores.
fatalist. The dual of survivalist; the score is the ratio of the
death and survival probability on the square. This player knows that
even if you win, you just have to keep playing over and over again, so
you might as well get it over with!
2.3 Engine-based players
Of course, people have been making more serious attempts at automating
chess since before computers, and there are thousands of chess engines
out there. We include a few in here to represent the high end of skill,
and to make sure that weaker players are evaluated somewhat in terms of
their ability to play chess proper, not just beat other weak players.
stockfish0. Stock sh [6] is probably the strongest open-source
chess engine (or even publicly available engine); at full strength its
play is estimated to be around 3500 Elo on the FIDE scale. Aside from
being quite machine-dependent (it can search more moves in a given
amount of time when it has a fast CPU with many cores), there are many
options to ddle with. Stock sh can use both opening books and endgame
tables; neither is used here. It also has a "di culty" setting, which
is set here to 0. Stock sh is run in a separate process, and the board
is reset before each move, but I am not extremely hygienic about ush
ing e.g. internal hash tables between moves. One consequence of this
attempt at statelessness is that Stock sh sometimes walks into a draw
by repetition in positions where it would be able to win, because it
doesn't know that it is repeating positions.stockfish5. Stock sh as above, but at di culty 5. stockfish10.
Same, at di culty 10.stockfish15. Same, at di culty 15.
stockfish20. And di culty 20, the maximum. Even at this di culty,
Stock sh produces moves basically instantaneously.stockfish1m. As expected, the engine's perfor mance increases
steadily as the di culty setting in creases (without apparently a
ecting the time to make moves). I don't know what it's doing with
these settings. The true way to unleash chess engines is to give them
a lot of CPU and memory to search. Since the tournament is run
simultaneously across about 60 threads3 using dozens of gigabytes of
memory, and sometimes I would play Hollow Knight (aka N) while it ran,
I wanted to avoid having the chess skill be dependent on the
scheduling environment. So here, Stock sh is given a "node" budget of
1 million, hence 1m. It takes about one second per move when run ning
alone, and is easily the strongest player (type) evaluated.worstfish. On the other hand, a strong chess en gine can also be
used to play badly. When playing as white, for each legal move, I ask
Stock sh (con- gured as stockfish0) to evaluate the resulting po
sition from black's perspective.4I then choose the move that
produces the best position for black. This is easily the worst player
evaluated, but it is not hard to imagine ways it could be worse.
Indeed, a common twist on chess is to play for a loss, called
Antichess or Losing Chess [9]. Recently it was even proved that
white can always win (i.e. lose) [8] in this variant! However, the
variant requires that you capture a3 The computer is the completely egregious AMD 2990WX "Threadripper
2," which has 32 cores (for 64 hardware threads) and 250 Watts of
power dissipation at load. The torture of this CPU was part of the
impetus for the paper.4By asking it to make a move, which also returns the evaluation of
its move. The UCI protocol does not seem to o er a way to evaluate a
position directly.18
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
height="0.7499518810148731in"}topple10k. Topple [7] is another
strong open source
+-----------------------------------------------------------------------+
| > |
| rZbJ0a0ZZpZpm0Z0pZ0j0Z0MZno0oQZ00ZPZ0O0OM0ZPZ0Z0RZ0Z0ZBZZ0Z0A0ZR |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 8. suicide_king (white) to move against worstfish a er 36
moves. Since the kings are already at their minimum distance, white
will make a move at ran dom. 37. Qxe5++ wins for white immediately,
but suicide_king plays 37. Qxd7??. The only legal move is 37. .
.Bxd7++, so worstfish must play it, and thus wins one of its only
victories.
piece if you are able to, so strategies and engines that support this
variant cannot be directly applied. We could use stronger settings of
Stock sh, but since it already invokes Stock sh for each legal move, it
is also one of the slowest players. Like Stock sh, it occasionally
blunders an otherwise losing position into a draw by repetition. But
most importantly, its search strategy when evaluating positions is not
ap plying the correct logic (³--´ pruning); it assumes that its opponent
will choose strong moves, and that it will itself play strong moves in
future plies. As a result, it sometimes allows the opponent to create a
situation where worstfish is forced to checkmate its opponent (Figure
8).
19
engine, provided to keep Stock sh on its toes. Here, its node budget
is 10,000.topple1m. Topple with a node budget of 1 million, which like
stockfish1m takes about one second per move. Stock sh almost always
wins, though it is not clear whether the budgets are actually
comparable.chessmaster.nes_lv1. This is Chessmaster for the Nintendo
Entertainment System, published in AD 1989. Moves are extracted from
the game via emula tion. This proved to be somewhat delicate, because
the in-memory representation of the board is not that simple (it
appears to be represented in two par allel arrays, perhaps using the
"0x88 method") and the game understandably goes wild if you mess it
up. To play a move, I restore a saved machine state in the "board
editor" mode, and then modify mem ory to contain the desired board. I
then emulate but ton presses to operate the game menu and return to
"playing" mode. Chessmaster repairs its internal data structures from
this board, and makes a move. During this time I mash controller
buttons to skip its dramatic tunes and modal messages like CHECK. Once
some memory locations reach certain values, the move has been played;
I can di the before and after boards to uniquely determine the move.
Since this approach uses emulation, it would normally be completely
deterministic, but I deliberately stall for a random number of frames
so that it can advance its internal pseudorandom state. A nice thing
about this engine is that it is an earnest attempt at writ ing a good
engine, but limited to the techniques of the 1980s, and running on
hardware that was under powered even for its day. It nishes well
behind themodern engines, but ahead of all the non-traditional strategies.
chessmaster.nes_lv2. As above, but increasing the "Level Of
Play" to "Newcomer 2." Chessmaster has stronger levels still, but in
these modes it will think for several NES minutes, which takes multiple
seconds to emulate---too slow for our purposes. Still much weaker than
modern engines (Figure 9).
{width="2.1802504374453195in"
height="2.1802504374453195in"}
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
such a move is legal, then one of the two pieces was mispredicted, so we
prefer the capture over sending an incorrect position to the engine.
Each of these uses a neural network to predict the con guration of the
board, and then the equivalent of stockfish1m to make a move for that
predicted board. (If that move is illegal because the board was
mispredicted, then it plays a random legal move.) These players can
therefore be seen as handicaps on stockfish1m.
2.5 Interpolation methods
Even at its weakest setting, stockfish0 crushes all of the
nontraditional strategies. This is not surprising, but it creates a
problem for quantifying their di er ence in skill (do they win one in a
million games? One in 10100?). Having intermediate players allows some
Elo points to ow between the two tiers transitively. One nice way to
construct intermediate players is by interpolation. We can interpolate
between any two
Fig. 9. stockfish1m (2019; running on a modern machine)
beats chessmaster.nes_lv2 (1989; running on an emu lated NES)
thousands of times without a loss or draw.2.4 Blind players
blind_yolo. This player is only allowed to see the 64-bit
mask of where pieces are placed on the board, but not their colors or
types. It is described in Color and Piece-blind Chess [4].
blind_kings. As blind_yolo, but forcing the pre diction
to produce exactly one king for each side, which improves its accuracy a
little.
blind_spycheck. As blind_kings, but perform ing a "spy
check" before each move. Here, the player tries capturing each piece of
a given (predicted) color with other pieces of that same (predicted)
color. If
players,5 but it is most natural to interpolate with
the most canonical player, random_move.**stockfish1m_r**nnn. There are 15 players in this group, each
characterized by a number nnn. Before each move, we generate a random
16-bit number; if the number is less than nnn then we play a random
move and otherwise, a move as stockfish1m. The values of nnn are
chosen so that we mix a power-of
two fraction of noise: stockfish1m_r32768 blends half random
with half strong moves, but we also have ¼ random, ⅛ random, 1/16,
1/32, . . . , 1/1024. These give us a nice smooth gradation at high
levels of play (Figure 11). At the extremes, many games5 Even if they are stateful! The interface separates "please give me
a move for the current state" and "the following move was played;
please update your state," allowing them to disagree. So we can just
keep two independent states for the two players.20
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
have no random moves, and the performance is di - cult to distinguish
from stockfish1m. Even at half random moves, stockfish1m_r32768
consistently beats the non-traditional players. So we also dilute stock
sh by mixing with a majority of random moves: stockfish1m_r49152 is
¾ random, and we also have ⅞, 15/16, 31/32, and 63/64. At this point
it becomes hard to distinguish from random_move.
Note that playing 1/64 excellent moves and the rest randomly doesn't
do much to help one's per formance. On the other hand, playing one
random move for 63/64 strong ones does create a signi cant handicap!
Against strong opponents, it's easy to see how a mistake can end the
game. Even against weak ones, a blunder can be fatal (Figure 10).
+-----------------------------------------------------------------------+
| > |
| rmblkansopopo0ZpBZ0Z0Z0ZZ0Z0ZpoQ0Z0ZPZ0ZZ0Z0Z0Z0POPO0OPOSNA0J0MR |
+=======================================================================+
+-----------------------------------------------------------------------+
8 7 6 5 4 3 2 1 a b c d e f g h
Fig. 10. A demonstration of how quickly random play can ruin a game.
stockfish1m_r32768 (black; plays half random moves and half
strong moves) loses to reverse_starting in one of the shortest
possible se quences: 1. e4 g5 2. Ba6 f5 3. Qh5++. Both of black's
moves are bad (so they must be random) but white's 2. Ba6 is a blunder
as well. White is just pushing pieces as far as possible; the mate is
purely accidental.
21
3 RUNNING THE TOURNAMENT
Given the players, it's a simple matter to simulate a bunch of games.
Since the tournament runs for tens of thousands of CPU hours, there is
of course some code to allow it to checkpoint its work, to make e -
cient use of CPU and RAM, and to provide attractive ANSI graphics
showing o its activity---but this is all straightforward.6 The
tournament accumulates win/loss/draw counts for each pair of players
(play ing as both white and black), as well as example games used to
debug or create the gures in this paper.After the tournament is done, or from any check point, I can run a
separate program to produce Elo (and other) rankings. Elo depends on
the order in which games are played, because it is designed to take
into account changes in player skill over time. However, it is easy to
just make up a random order in which the games were played, because
these players do not change over time.Despite its strong reputation, I found Elo to be rather nnicky. It is
sensitive to the starting scores for the players, and the factor k
which governs how strong of a correction to make after a game. With
players of such vastly di erent skill, it is also very sensitive to
the order in which the games are played.7 For similar reasons, it is
also very sensitive to imbal ance in the number of games played
between a partic ular pair of players; if some player mostly has games
against weak players, this can arti cially in ate its score.6 The source code can be found at sourceforge.net/p/tom7misc/
svn/HEAD/tree/trunk/chess/7For example, suppose the weak player random_move has one
win against stockfish1m. If this win happens early, when the two
players have their initial Elo scores, then it doesn't a ect anything.
If it happens last, when stockfish1m has thousands of Elo points
over random_move, then it produces a very strong correction.
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
To control for these e ects, I compute the maxi mum number n for which
we have n games played between every pair of players. I then seed each
player with an initial Elo score of 1000, and sample exactly n games to
play from each cell without replacement. This is so that we play a
balanced number of games. I also randomize the global order of all
games. Then I do this over again, with a smaller update factor k, for 20
passes. I don't know whether it's the fact that I reduce k over time, or
that I end up with e ectively 20 times the number of games played,8
but doing this signi cantly reduces variance. I run the whole thing 19
times and the result is the median Elo score. I also computed the 25th
and 75th percentiles, which were within 1--2% of the median, which is
good. The Elo scores appear in Section 4; n > 400 for this run.
Ideally, such a system would be robust against adding new players, but
this is probably not the case; it is easy to see from the results
(Figure 11) that there are certain matchups that favor one of the
players despite its average skill. During development, I often noticed
signi cant swings in Elo scores as players were added, especially before
there were middle-tier players in the mix. One way to deal with this
would be to run the Elo simulations multiple times while randomly
ablating players from the tournament; we could then at least estimate
the variance in the Elo scores under the removal of players, which is
like adding players in reverse. I did not implement such a thing because
of oppressive SIGBOVIK deadlines.
4 RESULTS
The main use of the Elo World tournament is to benchmark some new
engine or algorithm for play ing chess, particularly if it is not that
good [4]. There are a few ways that we can interpret the results:The Elo score, as described.
We can nd a comparable interpolated player. This is like the Scoville
scale for measuring how spicy something is: Some golden-tongued blind
tasters are given the pure chili oil and asked to distinguish it from
a cup of sugar water, which they of course can do. They then dilute
the chili oil 1:1 with sugar water, and try again. The number of
dilutions before the testers cannot reliably tell the drink from sugar
water yields the score on the Scoville scale. Here, for example, we
can say that blind_spycheck performs
between stockfish1m_r63488 and _r61440, so it is
approximately a 93.75--96.875% diluted Stock sh.We can compute a Markov probability. The tour nament table can be
easily thought of as a Markov transition matrix. Imagine that there is
a Champion trophy, held by the player corresponding to some row. Each
cell in that row contains the probability that in a game betweeen
those two players, the trophy would be passed to that player. We treat
draws as choosing one of the two sides by a coin ip (or, equivalently,
splitting the trophy in half); and for the games that the row player
wins, the trophy is retained (proba bility mass assigned to a
self-transition). It is easy to compute this matrix from the
win/loss/draw counts in the tournament table, and it is not sensitive
to imbalance like the Elo calculation is. Presented this way, we can
compute the stationary distribution (if it exists, which it typically
will), which basically tells8To be clear, running 20 passes means that games can be reused,
which is not ideal.22
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
+-----------------------------------+------------+--------------------+
| . . . Player | > Elo | p(Champion) |
+===================================+============+====================+
| blind_kings | 501.98 | > 0.00000633 |
| | | > |
| equalizer | 504.21 | > 0.00000653 |
| | | > |
| > stockfish1m_r61440 swarm | 521.45 | > 0.00001173 |
| | | > |
| blind_spycheck | 534.03 | > 0.00000623 |
| | | > |
| cccp | 546.91 | > 0.00002554 |
| | | > |
| min_oppt_moves | 553.54 | > 0.00000544 |
| | | > |
| > stockfish1m_r57344 | 597.04 | > 0.00001076 |
| > stockfish1m_r49152 | | > |
| > chessmaster.nes_lv1 | 600.54 | > 0.00001112 |
| > stockfish1m_r32768 | | > |
| > chessmaster.nes_lv2 | 752.22 | > 0.00000737 |
| > stockfish1m_r16384 | | > |
| > stockfish0 | 776.15 | > 0.00002055 |
| | | > |
| stockfish5 | 976.20 | > 0.00003025 |
| | | > |
| > stockfish1m_r8192 | 989.21 | > 0.00012094 |
| > topple10k | | > |
| | 1277.73 | > 0.00012509 |
| stockfish10 | | > |
| | 1335.69 | > 0.00008494 |
| stockfish15 | | > |
| | 1644.63 | > 0.00070207 |
| > stockfish1m_r4096 | | > |
| > stockfish20 | 1690.15 | > 0.00152052 |
| | | > |
| topple1m | 1771.65 | > 0.00179298 |
| | | > |
| > stockfish1m_r2048 | 1915.23 | > 0.00257648 |
| > stockfish1m_r1024 | | > |
| > stockfish1m_r512 | 1952.93 | > 0.00310436 |
| > stockfish1m_r256 | | > |
| > stockfish1m_r128 | 2020.25 | > 0.00886928 |
| > stockfish1m_r64 | | > |
| | 2139.47 | > 0.00721173 |
| stockfish1m | | > |
| | 2218.71 | > 0.01091286 |
| | | > |
| | 2261.50 | > 0.03132272 |
| | | > |
| | 2425.72 | > 0.06759788 |
| | | > |
| | 2521.78 | > 0.11122236 |
| | | > |
| | 2581.97 | > 0.15364889 |
| | | > |
| | 2609.45 | > 0.17861429 |
| | | > |
| | 2637.78 | > 0.20508090 |
| | | > |
| | 2644.10 | > 0.21523142 |
+-----------------------------------+------------+--------------------+
us that after an extremely large number of games,
what is the probability that a given player holds the
Champion trophy? This tends to agree with the Elo
score, but there are a few places where it does not
(e.g. same_color has a much higher p(Champion)
score than its Elo seems to warrant).
And so nally, a table with numbers:
+-----------------------------------+-----------+---------------------+
| Player | > Elo | p(Champion) |
+===================================+===========+=====================+
| worstfish 188.54 0.00000071 | | |
| | | |
| pacifist 286.90 0.00000509 | | |
| | | |
| alphabetical 320.91 0.00000276 | | |
| | | |
| generous 342.71 0.00000306 | | |
| | | |
| popular 349.48 0.00000374 | | |
| | | |
| dangerous 349.60 0.00000291 | | |
| | | |
| safe 350.64 0.00000454 | | |
| | | |
| first_move 357.71 0.00000434 | | |
| | | |
| rare 361.39 0.00000323 | | |
| | | |
| no_i_insist 378.23 | | |
| 0.00000244 | | |
| | | |
| huddle 399.55 0.00000933 | | |
| | | |
| sym_180 429.94 0.00000331 | | |
| | | |
| same_color 430.90 0.00002590 | | |
| | | |
| > opposite_color 432.11 | | |
| > 0.00000293 | | |
| > sym_mirror_x 438.87 | | |
| > 0.00000305 | | |
| | | |
| survivalist 439.03 0.00000681 | | |
| | | |
| random_move 439.21 | | |
| 0.00000462 | | |
| | | |
| fatalist 439.89 0.00000314 | | |
| | | |
| sym_mirror_y 442.50 | | |
| 0.00000716 | | |
| | | |
| > reverse_starting 445.56 | | |
| > 0.00000301 suicide_king | | |
| > 447.02 0.00000493 | | |
| > | | |
| > stockfish1m_r64512 462.82 | | |
| > 0.00000297 | | |
| > stockfish1m_r63488 482.44 | | |
| > 0.00000356 blind_yolo | | |
| > 488.97 0.00000488 | | |
| | | |
| . . . | | |
+-----------------------------------+-----------+---------------------+
5 CONCLUSION
Shout out to the Thursd'z Institute and anonymous
commenters on my blog for discussion of players
and suggestions. Several ideas were suggested by
multiple people, increasing my con dence that they
are somehow canonical.
23
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
The author would also like to thank the anony
{width="2.9071806649168854in"
height="2.9071806649168854in"}mous referees of the Special Interest Group on Baf-
ingly Overdone Ventures In Chess journal for their
careful reviews.
REFERENCES
[1] 2017. FIDE Handbook -- B.. Permanent conditions. www. de.
com/component/handbook?id=2.
[2] Arpad E Elo. 1978. The rating of chessplayers, past and present.
Arco Pub.
[3] Amanda M. Miller and David L. Farnsworth. 2013. Counting
the Number of Squares Reachable in k Knight's Moves. Open
Journal of Discrete Mathematics 03, 03 (2013), 151--154. https:
//doi.org/10.4236/ojdm.2013.33027
[4] Tom Murphy, VII. 2019. Color- and piece-blind chess. In A
Record of the Proceedings of SIGBOVIK 2019. ACH.
[5] Tom Murphy, VII. 2019. Survival in chessland. In A Record of the
Proceedings of SIGBOVIK 2019. ACH.
[6] Tord Romstad, Marco Costalba, and Joona Kiiski. 2019. Stock- sh
Chess. https://stock shchess.org/.
[7] Vincent Tang. 2019. Topple. https://github.com/konsolas/
ToppleChess/releases/.
[8] Mark Watkins. 2017. Losing Chess: 1. e3 Wins for White. ICGA
Journal 39, 2 (2017), 123--125.
[9] Wikipedia. [n. d.]. Losing Chess. http://en.wikipedia.org/
wiki/Losing_Chess.
Fig. 11. The matrix of outcomes for all players. There is too much
data to print, so we just have a bunch of col ors, mostly because it
looks rad. If you don't have a color printer or TV it will probably
not look rad. Rows indicate the player playing as white, from worst
(worstfish, top) to best (stockfish1m, bo om). Columns for the player
with the black pieces, in the same order from le to right. Green
indicates a cell that is predominately wins (for white), red is
losses, and blue is draws. The right and bot tom third of the graphic
are all di erent levels/dilutions of strong engines (Stockfish and
Topple). This creates a nice smooth gradient where be er engines
regularly beat even slightly weaker ones, but start to produce draws
at the highest levels. They consistently destroy weak engines; a cell
with an × indicates that it only contained wins or only contained
losses (not even draws).At the low end, there is a large splat of matchups that mostly produce
draws against one another, but can consis tently beat the weakest
tier. In the top-le corner, a square of blue draws from low-ambition
play; these aggressively bad players almost never win games, even when
playing each other.Microtexture outside of these broad trends comes from matchups where
the player is unusually suited or weak against that particular
opponent. For example, the bright red cell on the diagonal near the
center is cccp vs. cccp; this determinisic strategy alwasy wins in
self-play as black.24
4
A Formal Treatment of k/n Power-Hours
Christian Clausen
1 Related Work
Power Hour is the name of a drinking game in which you take one shot of
beer every minute, and while this is fun, sometimes you may prefer to
drink slower. This requires a generalization of the Power Hour, however
sophisticated algo rithms for this are prone to memory leaks. This
problem is addressed in [1] with a category of algorithms called
k/n Power-Hours.
Further studies of the Power Hour were made in [2] where the author
correctly points out that more games were possible then reported in
[1]. He further studies the effects of adding multiple players.We present here a pictorial representations to address further memory
leaks, a generalization over states, along with a series of lemmas
that suggest an extra possiblity not considered ear lier in the
k/n Power-Hours. We also include an appendix containing graphs
over all the possible fair 4 state, one person games.2 Introduction
Let's start with some notation. We have adapted the notation of [1]
where ] means full, ∪ means empty, and ∩ means flipped. Further we have
extended it with the symbol + to shorten: fill and drink.
The rules of a k/n Power-Hour are as follows:
every minute you have to perform one or more actions ending in a
(possibly new) state. Due to memory concerns the actions should be
uniquely determined based on the current state of your glass. If you
have a full glass you have to drink it, before executing the actions.
You will end up drinking k shots in n minutes.Now we are equipped to take a first look at our pictorial
representation of a configuration, specifically the 2/60 as
described by [1]. 1
] ∪
+
∩
Figure 1: 2/n
It reads: on ] empty it and leave ∪. On ∪ fill and drink, then leave
∩.3 A Multitude of States
In this section we present our generalized lem mas, along with
examples.The first generalization we need to discuss is the number of states,
while the conventional 3 are neat we suggest a fourth ⊂ (lying), that
can be used without conflict with the others. How1We usually omit identity arrows, as here from ∩ to ∩, unless we
only use one state.25
ever we advice against using it together with ⊃, as this will cause
confusion.
Having offered an extra state we can only as sume other people will do
so as well. Therefore we will write k/snfor a k/n game with s
states. If nothing is indicated we assume a 3 state game.
Definition 1. a fractional game is a k/sn where k is some
fraction f(n)We can now make the more interesting 2n/n and [2n]{.underline}3
/n games;+
] ∪
]
+
∩
has s = d.
d. A pure fractional game
Figure 3: 2n/n,[2n]{.underline}3 /n
Specifically this means a game with a graph where there is a cycle, the
longest circle is d steps, and ] is in it.
Lemma 2. for a k/sn power hour game there are s trivial
fractional configurations; [n]{.underline}1/n,[n]{.underline}2/n, . . . ,[n]{.underline}s/n.
In fact;
Theorem 4. all possible pure fractional games [kn]{.underline}
d /sncan be constructed from the previous two lemmas.
Proof. by induction on the number of states.
Proof. left as an exercise to the reader.
With the conventional 3 states they look like this:
] ∪
] ] ∪
∩
Figure
2:[n]{.underline}1/n,[n]{.underline}2/n,[n]{.underline}3/nAn interesting aspect is that we can add + to any of these arrows, the
effect of which is are presented in the following lemma:Lemma 3. for a fractional [kn]{.underline}d /sngame with k ≤ d,
can make it into a(k+1)n
d /sngame.
Corollary 5. all possible pure fractional games can be written on the
form [kn]{.underline}s /sn, with k ≤ s + 1.4 Constant Amount Games
In this section we look at c/sn games where c is not affected by
n. Intuitively this means that we cannot have (non-identity) cycles in
the graphs. We already saw the 2/n game. However which games are
possible? In [1] the authors claim that a3/60 game is
impossible2, however we claim that it is possible, and even
stronger:Lemma 6. with s states, and n ≥ s there are s + 1 lower constant
games: 0/sn,1/sn, . . . ,s/sn.
Proof. we add 1 drink pr. d steps, in a k step game, thus we have
[1]{.underline}dn+[kn]{.underline}d =[n]{.underline}d
+[kn]{.underline}d =[n+kn]{.underline}
Proof. by induction on the number of states.
(k+1)n d.
d =
2they were conducting relevant research while writing it, so it is
understandable.
26
Continuing with the classical examples they are3:
] ∪
Theorem 9 (Soundness). there is a fractional [kn−c]{.underline}
d /sngame if k ≤ d+1, d+|c| ≤ s, and kn−c ≥ 0.
∩ ] ∩ +
+
∩
The equation may look complicated, but it is quite logical when you look
at a picture:
] ∪
+
∩
⊂ ∩ ∪ ]
+
∩ ] ∪
Figure 4: 0/n,1/n,2/n,3/n
At this point you may think that we are done with constant games,
however as noted by ... there is some symmetry in this game, and we can
take advantage of this here;
Lemma 7. with s states and n ≥ s there are s
Figure 6: 29/460,[59]{.underline}2 /60 ∼=31/60[2]
And finally we are ready to express the master lemma:
Theorem 10 (Completeness). all possible frac tional games can be
written as[kn−c]{.underline}
upper constant games: n−s+1/sn,n−s+2/sn, . . . ,n/sn.
d + 1, d + c ≤ s and kn − c ≥ 0.
d /sn with k ≤
Proof. by induction on the number of states.
Which captures all the intuitions we have
You may have already figured out how they look, but here they are;
∩ ∪
∪ ] ]
]
built.
Now that we have that in order, should invite some friends:
Lemma 11. if d − 1 players take turns play ing with the same cup, and
there is a fair game d /sn with p | c then there is a
fair[kn−c]{.underline}
[kn−c]{.underline}
pd /sngame.
Figure 5: n−2/n,n−1/n,n/n
5 Having a Party
Definition 8. a game k/sn with k ∈ N is called fair.
Now it is time to mix it all together:
3Notice that we end on a ∩ to indicate that it does not need
refilling.
This means that with 2 girls, 1 cup, and an hour the possible games
are:[60k]{.underline}
2·3/360 =10k/360
for k ≤ 4 (due to proposition 5), giving the new configuration
10/60. If we also have a die we could even get: 10k−1/960
for k ≤ 4. And with 3 people we could play 5k/460 for k ≤ 5,
giving the new (fair) games: 5/460,25/460.27
6 Bibliography
[1] Ben Blum, Dr. William Locas, Chris
A.3 Lower Constant Games ] ∪
Martens, Dr. Tom Murphy VII, Algorithms for k/n Power-Hours, SIGBOVIK
2012
[2] Dr. Tom Murphy VII, New results in k/n
∩ ] ∩ +
+
∩
+
Power-Hours, SIGBOVIK 2014
] ∪
+
∩
] ∪ +
∩ ⊂ +
A 4 State Games
A.1 Trivial Fractional Games
Figure 9: 0/4n,1/4n,2/4n,3/4n,4/4n
A.4 Upper Constant Games
] ∪
∩ ⊂ ] ∪
∩ ∪ ]
∪ ] ]
] ] ∪
∩
] ∪
∩ ⊂
Figure
7:[n]{.underline}1/4n,[n]{.underline}2/4n,[n]{.underline}3/4n,[n]{.underline}4/4n
A.2 Other Fractional Games +
Figure 10: n−3/n,n−2/n,n−1/n,n/n A.5 Mixed Games
⊂ ∩
∪ ]
Figure 11:[n−2]{.underline}
2 /4n
]
] ∪
+
∩
] ∪ +
∩ ⊂ +
Figure 8: 2n/4n,[2n]{.underline}3 /4n,[3n]{.underline}4
/4n28
5
��������
���������� ���������� ��������
���� ������
����� �� ����
��������� ���������� ������ ������ ��� ��� �� � �����
�� ����������� ������� ��� ���� �� �������� �������� ����������� �� ���
��������� ����� �� ���������� �� ���� ������ �� ���� ��� �� ����� ����
����� �� ��� ���� ���� �� ������� ���� ������� �� ��� ���� ������ �����
����� �� ����������� ����������
�������� ����� ������ ������� ���� ������� ���� �����
� ������������
�� ��������� ����������� �������� �������� ����������� �� � ����� ��
��������� ������� ����� �� � ������ ���� �� ������� �� � ������� �����
�� ����� ���� �������� �� ������� ��������� ������� �� �������� �����
������� �� ����� �� ���� ����������� ����� ��� ����� �� ��� ��������� �������� ���� ����� �� � ������� ����� �� ������������
������������� �� ��� ��������� �� ���� ���� ��������� �� ��� ���� ��
��� ������ �� ��� ������� � �������� ����� ���������� ���� ����
�������� �� �� ������ ����������� ���� ��� ���� ����������� ����� ��
����������� ���������� ����� ��������� ��� ����� �� ������� ����������
�� � ����� �������� ���� ������ �� �������� � ����� �������� �� ���� ��� ����� ��������
����������� �� �� ������� �� ������ ����� �������������
��� �������� ���� ��� �������� ����������� �� � ����� ������� ��
�������� � ������ �� ����������� ���� ������ �� �� ���� �� �� ������
���������� �� ��� �� ��� ����������� ����� ������� ����� �� �� ��������� �� ������� � �����
�� ����� ������ ��� �� ��������� �� � ����� �� ��� ����������� �� ����
������� ������ �� ���� ����� ������� ���� ����������� ������������ �� ����� �� ����� ���� ������ ��� ������� ��� �����
���� ���������� �� ��� ���� ������� ��� �� �������� �� ������������ ��
����� �� ������ ������� ��� ��� ��������� ���� ���� �������� ��� �
������� ��� ���� ��������� ����� �� �� ���������� �� ��� �������
������� ���� ��� ������������� ���� ������ �� �� ��������� �� ���� ���� ����� �� �� �������� ����
���� ������ �� �� ���� ����� ����� ������� ����������� ��� ���
�������� �� ���� ������ �� ���� ������ ��� �������� ���� �� �� ����
��� �� ���� ���� ���� ����� ������ ���������� ������� ��������� ���
������� ��� ��� ���� ���������� ���� �� ���� ��� �� ���� ���� ��������
��� ���� ���� ��� ������� ���� ������ ������� ��� ������� ��� �����
���� � �������� ����� ����� �� ����� �� ���� �������� ���� ������ �� ���� ��������� ��� �� ���� ��� ��� �� ��������
����� ����� ���������� ���� �� �� �� ��� ��� ������������� ��������
���������� ����� ������� ���� �������������� ����� �������� ���
������������ ������������ ����� ���������� ���� ��� � ���������� �����
������ �� ���������� ����������
�� ��� �������� �� ���������� ���� ������� ���������� �� ������ ��
������� �� �������� �� ��������� ��� ���� ������� �� ���� ��������
���� �� ��� ����������������� ��������� ������ �� ��� �������� ��������� ����������
����� �� ������� ��
�
29
����������������� ������������� �� � ����� ������ �� ����� ��������� ��
����� ���� ���������� ���� ����� ���� ��� ������
���� ������ ������ �� ��� ����� ������ ������ ���� ����� ��
����������� �� ����������� ��������� �� ��� ������ ����� ������������
���� ������ ���� �� �� �� ��� �������� �� ������� ���� �� ����� �� �� �
������ ������� �� �� �� ��� ��������� �� ����� ���� ���� ���� ����
������� ��� ������ �� ��� ����� �������
��� ��� ����� ��� ���� ��� ����� ����� �� ����������� ����� ��
��������������� � ����� ������ ������ �� ����� ��� ������ �� ���� ��� ��
������������ �� ��� ������ �� ����� �� ����� ���� ��������� �����������
������ ��� �������� �� ���� ���� ���� �� ������ �����������
����� ����� �������� ��������� ��� ����������� ���� ����� ��
����������� ����� �� ������������ �� �������� �������������� ������ ��
����� �� ���� ��� � ������ �� ��������� ������ �� ������������� ���
������� ����� �� ��� ��������� ���� ���� �������� ����������� � ������
����� �� ���� ���� ��� ������ ��������� ��� ���� ���������� ���� �����
�� ���� �� ����� �� ���� ������� ������ �� ��� ����������� ��� ���� ��
�������� �� �� ���� �� ��� ����������
����� ���� ���������� �� ���������� �� ������� �� �������� �
���������� ��� ���������� ����� ��������� �� ������ ��� �� ����� ��
��������� �� ����������� ����� ������������ �� �� ������������ ���� ��
������� ������� ��� �� ������ ���� ������ ���� �������� ����
������������ �� ������ �� ��� ������ ������� ��������� ����������
��� ���� �� ���� ���� ��� ���������� �� ����������� ��� ��� ������� ��
���� ������� � ���������� �� ����� ������������ ���������������� ����������� ��� ���� ������
�� ���� ����� ���� � ���������� ��� �� ��������� ��� ���� ������ �� ��
������� ���� ����� ������ � ��������� ����� ����� � ���� �� ������� ��� ���� ������ �� ���� �����
����������� ��� ����� ���� ������ �� ��� ����� ����� �� ���� �� ����
�� ������ �� ������ ��� ��� �� ���� ������� ���� �������� ��� ���� ��
����� ��� ����� ���������� �������� ��� ���� ��� ����� ��� ���� ������
������ �� ��������������� ���������� ��� ���� ����� �������������� �� �� ��������� ��
������ � ����� �� ����� ���������� ��� ����� �� ��� ��������� �����
���� �� �� ��� ������ �������� �� ������� ��� ��� ���������� ������
����� ������� ������ ������ ��� ���� ��������� ���� ������ �������
�������� ���������� ����� �� ���� �� ������� ������ �������� �� � ���
�� ����� ����� ��� ������ ������� ������ �������� �������� ������ ����
���� ��� ���������� ���� ������ ��������������� ��� ��������� �� ����� ���� �� �������� �� ����� ����� ���� ���� ��
���� ������� ����� �������� ��� ���������� ���� ���� ��� ����
��������� ������ �� ��������� ��� ����� �� �� �������� �� ������� ��
��� ����������������� ��������� ������ �� ���� ����� ������ ���� �� �������� ��
� �������� ���� ������� � ������ ������ ����� ����� ���� ������ ��
������� ������������� ��� ��������� �� �������� �� ��� ���� ��
����������� ��� ���� ��� ������� �� �������� ���� ���������� ���
���������� ������� ���� ������ ����� ������� ���� �� ���������� ����
��� ���� ������� ����� ���� ������ �� ���� ����� ���� �� ����� ���� ��
���� ��������� �� ����� ������� ����������� ���������
f(t) = 1
������ �� ���� ��� �������� ����������
���� ������ ��� �������� ���� ��������� ���� ����� �� ������ ����
������ ������ ��
f(t) = 0
������ �� ���� ��� ����� �������
��� ��� ����� ���� ����� �� ������ ��� ���� ����� ��������� ��
������ �� ��� �������� ���������
�
30
���������� ���� ��� ������ ����� �� ��� ����� ���� ��� ���� �����
������������ ����� ����� ���� ������� � ���� ���������� �� ��� ��� ��
������� ������� ���� ���� ����� ����� ����� ��� ���� ������ ���� ��
������� ������ ���� ���������� ���� ������� ��� �� ���� �� ���� ����
���������� �� ����������� ������ �� ���� ������ ������� ���� �� ��
���� ���������� �� ������ � ������ ���� ������ �� ����� ���� � ����
��� �����f(t) =−0.2 �� t �� ������ ��������� �� � 0.5 ���������
������ �� ���� ��� ���� ��� ������
����� ����� � ��� �� ���� �� ����� ������� ������ ��� ���� �������
�� ��������� ��� ������ �� ���� ������ ��� ��� ���� ������� ����� ���
����� ����� �� ���� ��������� ������ ��� ������ ���������� ����� �� ��
������� ���� ���� �� ��� ���� ��� ����� ���������� ��� ��������� ���
��������� ��������� ����� ���� ��� ���� ���� ���� ��� ������� �� � ����
����� �� �������� �� ��� ����� ������������ ���������� ����� ���� ��
���� ���� ��� ������ �� �� � �������� �� ������� � ����������� �� ���
�������� ������� ��� ��� ��� ���� ������ ������ ��� ������� ������ ���
��� ��� ��� ���� ������ ����� ��� ������� ������ ��� ��� �� ���������
�������� ��� ������� ����� ������� ��� �� ������� �� ���� ����� ���� ���
����� ����� �� �� � ���������� �����������
f(t) =0.2 ��t \< 4
1.5 ��t ≥ 4
������ �� ���� ��� ������ ������
��� ��������� � �����
�� ����� � ������ ��� ������� ���� ������ �� ���� ��� ��� ���� ��� ���
������� �������� ���� ����� ����� ���� ������ �� ����� ����� ����
�������������� �� ����������� � ������ �� ���� ������� �� ������� ���� �
�������� �� ������ ���� ������������� ��� ���� ���� ������� �����
����������� ����� � �������� ��
��� ���� ���� ��� ����� �� ����������� ������� ���� ������
����� �������
��� �� ����� �� ����� ���� ���� ����� �� ���� ������ �� �� ��������
��� ��������� ������� �� ��� ���� ������� ������ �� ��� ����� ������
���������� ��� ������� �� ��� ���� ��� ����� ��������� ��� ��� ����
��� ����� �������� ���������� ����� �� �� ��� ��� �� ��� ������ �����
��������� ������� ������� ��� ���� ������ �� ��� ������ ��� ��� �������������� � ���������� ���� ��������� ��� ���� ��� ���� ����� ���
�������� ��������� ���� ������ ��� �������� ��� �������� �� ��� ��
���� � ����� ���� ������� ����� ���� �� ���� � ������ �� ��� ����� ��
�� ����� ����� ����� ��� ���� ������� ������� �� ���� ���� ��� �����
������� ��� ���������� ������ ��� ��� ��������8 ������� �������� ��� ��� ����
���� �����
6
4
2
0
0 2 4 6 8
������ �� � ������ ��������
� ����������
����� ������� ������ �� � �������� ��� ��������� ����� �� ������� ����
�� ����������� ����� ���� ��� ����� ����� �� ����������� ������� ���
���� ��� ������� � ������ ���������� ��� ���� �������� ������ �������
����� ���� ���������� ���� �� � ������ ������� �� ���� �����
�
31
����������
��� ������� ����� ��� ���� �������� ���������� ���������� ��� ������
������ ����������� �� � ������ �� ��� ����������� �� �������� �����
����� ������
32
Survival advice from a computer scientist
6 Survival in chessland
Dr. Tom Murphy VII Ph.D.
Keywords: chess, chess to the death, being a chesspiece to the death 7
Optimizing The SacrificeNico Zevallos
Keywords: Tarkovsky, Offret, film, movie, optimization, path plan
ning, pursuit, evasion, art8 Abusing the RPM package manager to compile software ILIANA DESTROYER
OF WORLDSKeywords: Linux, software management, recursion
33
6
Abstract
CHESSMATE.
Introduction
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
Survival in chessland
Dr. Tom Murphy VII Ph.D.∗
1 April 2019
Now it doesn't matter whether you're good or bad at chess, because you
don't get to pick what happens in the game. What matters is that your
piece lives to the end of the game, when all surviving pieces are set
free. Which piece should you want to be?
In formal chess, the king can never be captured: The game
If you are forced to play chess to the death, you are in trouble,
because most people are not good at chess (for example, the author)
and yet want to live.1But what if you are forced to be one of the chess pieces to the death?
That is, your little soul inhabits one of the 32 pieces or pawns and
your soul is vanquished if that piece is eliminated.∗Copyright c 2019 the Regents of the Wikiplia Foundation. Appears in
SIGBOVIK 2019 with the threefold repetition of the Association for
Computational Heresy; IEEEEEE! press, Verlag-Verlag volume no. 0x40-
2A. 53 Centipawns
1It is easy for two players to collaborate to produce a draw,
especially by simply agreeing to a draw at the outset of the game (if
allowed). Some tournament formats forbid the players from agreeing to a
draw verbally before a certain point (e.g. 30 moves), or without the
arbiter's consent, and FIDE rules technically do not allow a draw until
both players have made a move (5.2.3). There are always other routes to
a draw, for example by stalemate or repeating the same position three
times. Collaboratively producing such situations is easy, but this
strategy is not likely a stable equilibrium: Players can often gain a
substantial advantage by going "off script" and instead trying to win
the game. Additionally, sometimes the terms of chess-to-the-death do not
allow the players to communicate at all beforehand, nor during the game.
If this is the case, then it may be difficult to agree on the approach
to drawing, let alone establish that this is both players' desire. Since
the rules of chess-to-the-death can't forbid us from colluding right now
as you read this paper, I hereby declare that the following is the
correct approach:
1. Nf3. This is a reasonable opening move for white (begins the
R´eti) which can transpose into several common systems (e.g. King's In
dian). Since the knight can move back to g1 on the next move, knight
moves are the fastest route to a draw by repetition. This has a good
chance of signaling to a wise player that a draw is desired. The
player should make this move after pondering carefully for some time,
and then looking meaningfully into the other player's eyes.1. . . . Nf6. This is both a strong response for black in a real
game, and simultaneously a signal that a draw is desired. The other
advantage is that very weak players[3] may simply copy what white
does. In doing so, they will also play this move.2. Ng1?!. White moves the knight back to its starting square. This is
a terrible move for white, but clearly signals the intention to draw.2. . . . Ng8!. "Fool's Draw Accepted." The starting position is
reached for a second time.3. Nf3 Nf6. At this point the game should clearly continue repeating
the sequence, although since we are in the start position, white has
any number of strong opening moves available. Signaling the draw line
and then 3. d4!? may be pyschologically devastating.4. Ng1 Ng8 ½-½. The starting position is reached for the third
time, which by rule2is a draw.ends when the king is attacked but cannot move, and it is illegal to
make a move that leaves the king attacked. The king's death is
implied, of course, but it is seen as more poetic to end the game
prior to this point.For the sake of this question, we'll consider the the white king to
"die" if white loses (i.e., is checkmated), and likewise for black.
Otherwise, of course, the best chances of survival would trivially be
with the two kings, since they are never formally captured. Loss
includes resignation, since most high level games actually end once
the defeated player agrees that loss is inevitable. We can think of
this common case like king seppuku. Many games also end in time
forfeit, which is like the king's poor diet and lifestyle choices
leading to a death by natural causes.Neither side is believed to have a decisive advantage, and many games
end in a draw, with both kings surviving. So the survival chances of a
king are likely greater than 50%; pretty decent odds. Is it possible
that any other piece has even better chances? Let's find out---our
lives may depend on it!Since this is one of the shortest possible routes to a draw, I hereby
dub this line the "Fool's Draw," by analogy with the Fool's Mate. In
this line all pieces survive, which is anyway humane and also
advantageous in the case that you or someone is simultaneously being
one of the chesspieces to the death!If 1. . . . Nc6 or another Knight's move, white can also consider
contin uing in the obvious way. However after 1. . . . d5, black has
refused or not noticed the draw. Fortunately, white is still in a good
position to play the game normally (this is the main line of the R´eti
opening, followed by 2. c4). White can try to be more obvious with 2.
Ng1, but if black is choosing to just play normally, white takes a
distinct handicap by doing so.The biggest risk for white is that black does not play 2. . . . Ng8
but rather a normal move like 2. . . . g6 ("Fool's Draw Betrayed").
This can happen if black is not metagaming at all (for Nf6 is a normal
response to the normal Nf3), or if black is an exceptionally shrewd
metagamer (tricking white into wasting two tempos with Ng1 by
pretending to be cooperating).Of course, this all relies on the assumption that if
chess-to-the-death ends in a draw, the players are spared or allowed
to repeat indefinitely. If both players are actually executed, then
this line is truly a Fool's Draw!2But is it?
First of all, although either player is allowed to claim a draw after
three repetitions of the same position, it is not automatic. However,
FIDE rules do declare that the game simply ends in a draw upon five
repetitions. Of course it is easy to extend the Fool's Draw to
accommodate this.Second: The lichess implementation (although known to be buggy[2])
34
1 Hypotheses
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
• Rooks tend to be late-game pieces, because they are dif ficult to get
out of their corners (and at most one can be
Like all good scientific research, I clearly laid out my hypoth esis and
wrote down the motivation before performing the study. This helps
prevent presentation bias where the results appear more satisfactory
because they are framed as a natural conclusion from the idea that
motivated the research in the first place (when in fact, of course, if
you write the motivation after witnessing the results, backflow is
inevitable). It is also much more exciting. I literally don't know the
answer as I'm writing this, nor whether it is interesting in any way!
Here are my guesses.
• Black and white are probably not substantially different. That is,
the a1 and a8 rooks probably have about the same survival chances
(it's known that white has a slight statistical advantage [4] but it
is probably only around 1%). So these guesses will be written about
white's pieces.• The d2 and e2 pawns are very active in common openings, and are
frequently captured as part of those openings. I think they are the
least likely to survive overall.• Bishops and knights are often involved in the opening and midgame,
and often exchanged nonchalantly. I think they all have relatively low
survival chances.• Although the queen is very valuable, a queen exchange is often
forced for games that enter the endgame.
does not permit a threefold repetition claim in this situation, which
got me thinking that maybe there is some subtlety here. Is the starting
position special somehow, not counting as having occurred? The relevant
statute, from the FIDE Laws of Chess[1]:
9.2. The game is drawn, upon a correct claim by a player having the
move, when the same position for at least the third time (not
necessarily by a repetition of moves):a. is about to appear, if he first writes his move, which cannot be
changed, on his scoresheet and declares to the arbiter his intention
to make this move, orb. has just appeared, and the player claiming the draw has the move.
Positions are considered the same if and only if the same player has
the move, pieces of the same kind and colour occupy the same squares
and the possible moves of all the pieces of both players are the same.
Thus positions are not the same if:1. at the start of the sequence a pawn could have been captured en
passant.2. a king or rook had castling rights, but forfeited these after
moving. The castling rights are lost only after the king or rook is
moved.So the question is, has the starting position "appeared" before
white's first move? The rules are not totally clear on this point.
Note that "positions are considered the same" only when the same
player "has the move." FIDE defines "have the move" as1.3. A player is said to 'have the move' when his opponent's move has
been 'made'.A strong case can therefore be made that white does not 'have the
move' in the formal sense at the beginning of the game, since black
has not made a move!Nonetheless, it does seem clear that white can claim a draw by 9.2.a,
by committing the move 5. Nf3 and declaring to the arbiter that the
position is now about to appear for the third time. This seems
unambiguously legal.activated by the fastest method, castling) and are rela tively
valuable.• This leaves the non-central pawns. These are the hardest to predict,
and they are hard to think about (at least for me) because when e.g.
the a2 pawn recaptures the b3 pawn that it supported, I just think of
this as the b3 pawn. Of these pawns, b2 and g2 are somewhat weak
because they are undefended once the bishop is developed (cf. the
famous "poison pawn" at b2). On the other hand, in the fianchetto
configuration, this pawn is very strong and often survives the entire
game without leaving the third rank. Since pawn chains usually
progress towards the middle of the board, the a2 pawn is more likely
to be supporting than supported. This both leaves it weak to capture,
but prone to recapturing. Outside pawns block one's own rook, although
for this same reason they often clear the file by capturing (and so
survive). They are also commonly used to push into a well-defended
king's territory (e.g. in the fianchetto); kingside castling is more
common, so this means that the h pawns are often lost to this fate.The final ranking that I predict, from most surviving to most dead:
pf, pc, pg, pa, ph, pb, Rh, Ra, K, Q, Bf, Ng, pe, pd.As already copped to, while the author is an aficionado and also knows
how to spell the difficult word aficionado without spell-check, he is
not good at chess. A few drinking buddies with varying chessperience
were also consulted for their wagers; these are compared to each other
and to the actual results in Section 4.2 Methodology
To compute the chances for survival, I legally acquired 506,000,416
chess games from lichess.org. This is all of the standard variant,
rated games from Jan 2013 to November 2018, in any time format. Only
games that are completed and valid are included (about 200,000 games
did not meet this cri teria). The total data size is 875 gigabytes, so
processing these took some care for efficiency and parallelism.
Fortunately, I have a computer with just an obscene number of cores
and truly excessive RAM, so you gotta use that for something.3Other than that, I simply implemented the rules of chess, wrote a PGN
parser, then parsed and simulated each game. For each of the 32 pieces
in the starting position, I tracked its current location, and whether
it is alive; multiple dead pieces could occupy the same square. At the
end of the game, one of the kings is killed if his side has lost.For a piece, there is a single factual survival rate in these games,
given just by [num survived]{.underline}num games. What we're really inter ested in, however, is
estimating the underlying true survival probability for each piece. In
order to do this with reasonable efficency, we divide the games into
32 separate buckets, and3To torture your own desktop computer, source code is available at
sourceforge.net/p/tom7misc/svn/HEAD/tree/trunk/chess/.35
♟h70.4% ♙a70.5% ♟a70.5%♙h71.5%
♙g66.6%
♟g65.1%
♟b59.9% ♙b60.5%
a55.9% ♖a56.5%♙f 57.3%
♜ ♟f 55.3% ♔53.5%♜h54.4% ♖h54.5%
♚50.3%
♙c 47.9%
♛44.8% ♟c 45.2% ♕45.6%
♟e37.2%
this was the most controversial among the drinking buddies
{width="0.5204101049868767in"
height="0.7499518810148731in"}
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
(Section 4). Note that pc is the sacrificed pawn in the pop ular Queen's
Gambit (1. d4 d5 2. c4), where accepting and declining the pawn are both
common and sound responses. This may be a good example of a piece that
has substantially different survival rates in different opening
preferences. Since the variance is otherwise extremely low, I only
report means for the remainder of the paper.
Despite my impression that many games end in a draw, ties are actually
rare in the lichess database. In January 2018, only 3.8% of games were
drawn; as a result, the survival chances for the kings are both close to
50%. Although the database contains games in many time formats and with
all varieties of human skill (including over a thousand games by Magnus
Carlsen, the world champion and highest rated player of all time4),
blitz (∼ 5 minutes per side) and bullet (∼ 1 minute) games are
predominant. Nonetheless, the results are fairly robust across different
time formats and skill levels. In Sec tion 4.1 I show some slices of the
data for comparison.
3 Safest spaces
The fate of each piece is to either survive or die, and it does so on
one of the 64 squares. With the same replay of the
♝f 32.2% ♟d32.4% ♝c 32.4% ♙d30.8% ♗f 30.9% ♗c 31.3% ♙e31.3%
♘b29.1%
♞b26.7%
♘g23.3%♞g24.3%
Figure 1: Survival probabilities for each of the 32 pieces in standard
chess, in 500 million games. The number is the mean survival rate across
all samples. The vertical position of the dot is this mean rate, with a
line drawing the span between the smallest and largest sample bucket
(this is usually a very tiny range). Horizontal position is purely
presentational, to avoid overlap.
count statistics separately for each. From these samples we can then
estimate variance, for example. The games are bucketized by a
deterministic hash of the White player's username. This way, if there
exist some players who are highly unusual (per haps automated accounts),
their games are grouped together and pessimistically represented in the
variance estimate. This also helps account for different opening
preferences; the chosen opening certainly affects the survival chances.
The basic survival chances appear in Figure 1. Indeed, many pieces are
more likely to survive than the kings. Even as black, the extremal pawns
(pa and ph) have over a 70% survival rate. Across the board, the
survival chances for a white piece and its black twin are similar,
usually with a small edge to white. No table exceptions are the Ng (the
overall most doomed piece), and both white bishops, which die more than
their Schwarz doppelgangers. The pe is vastly more dead than pe. Note
somewhat satisfyingly that the pc has the highest variance;
500 million games I also kept statistics on the fates of each piece.
If being a chess piece to the death, and possessing some influence
over where your piece moves, it may be helpful to know where to go.
Even without influence, such knowledge could help calibrate your
anxiety.Other than the bishops---which have no legal way to reach half of the
squares---every piece ends on every square in at least a thousand
games. So we have enough samples to have rea sonable confidence in our
statistics, even for the most unlikely odysseys. The least mobile
pieces are the pawns, who can tech nically reach any square by
promoting, but are usually confined to cones emanating from their
start squares. The overall rarest fate is for pf2 to die on the a7
square, which only happened 1,244 times (however, it survived on this
square 31,438 times). This square is actually reachable without
promoting, but it would need to capture 5 times in order to get there,
which seems quite unlikely! There may even be a hidden achieve ment
for reaching this square this way! Aside from pawns, the weirdest fate
is for Ng to die on h1, which happened 47,307 times. Corners are of
course garbage for the knight, although it is twice as likely to
survive on this square.There are characteristic patterns for each of the pieces, which make
sense given their starting positions movement rules. You could
probably guess the piece just by looking at one of the heat maps
below, although---spoiler alert---the piece is just listed right there
and they are in order. Two indepen dent things are communicated in
these graphics: The chance that the piece ends the game on some square
(alive or dead), and its survival chances there. In each map, a darker
back ground color indicates that the piece ends on that square more
often. The shade is based on the rank (64/64 black is most common,
63/64 black is next most common, etc.) rather than4Although to be fair, his username "DrDrunkenstein" suggests he may
not play at full strength.
36
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
the absolute probability, since otherwise the graphic looks bor ing. The
number on the square is the percentage survival of the piece when it is
last seen (either being captured or surviving to the end of the game) on
that square. The four squares with the highest survival rates are
underlined for your convenience.
81.1 64.1 57.7 56.1 51.5 59.3 65.5 65.3
47.7 40.9 39.3 37.5 38.3 39.5 47.0 47.4
40.7 45.2 34.6 31.4 33.3 41.9 51.3 57.1
42.1 37.6 34.9 29.3 31.2 41.2 47.8 60.0
45.6 47.2 37.7 30.6 33.6 40.9 49.0 61.4
54.0 45.2 34.7 34.4 32.8 35.0 42.3 61.6
67.6 60.6 51.3 40.3 41.0 40.7 50.7 72.5
55.5 56.3 52.7 59.2 46.7 42.2 45.6 54.3 58.9 51.8
59.1 43.6 43.5 31.6 36.8 41.0 51.4 52.8 42.2 38.0
31.9 33.6 40.0 50.0 59.7 34.9 43.9 25.4 31.1 34.8
36.7 51.8 48.8 44.6 37.5 26.7 32.6 37.3 36.8 59.9
61.5 28.2 39.2 33.0 36.7 28.5 41.3 65.0 76.4 70.3
57.3 33.5 32.0 61.1 75.5 83.2 68.0 55.4 51.3 14.9
52.3 53.6 60.1 79.8
30.8 46.9 54.1 29.2 49.1 33.5 57.4 40.3 41.1 52.3
49.5 46.6 46.1 54.1 56.5 49.5 31.7 46.8 48.5 46.3
48.3 51.2 50.4 38.4
{width="0.5204101049868767in"
height="0.7499518810148731in"}qd8
30.5 35.0 21.9 17.5 25.8 26.5 46.8 63.0
52.4 90.9 55.1 60.5 51.4 62.1 56.8 60.0 52.2 49.4
45.6 42.5 44.4 40.2 51.7 46.8 43.5 49.5 24.5 34.2
30.2 33.3 39.2 42.8 46.1 21.7 26.6 18.3 8.3 27.9
27.9 38.5 32.4 31.7 16.7 9.2 17.6 27.2 33.4 38.4
36.6 11.2 23.0 15.6 21.0 9.9 21.9 36.4 34.3 32.3
35.9 21.2 19.1 29.0 22.1 36.2 30.4 20.6 12.5 18.8
17.5 11.3 20.5 23.6
64.7 86.3 56.0 57.8 60.8 36.3 44.8 61.4 44.7 37.8
25.3 30.6 23.4 20.8 27.9 44.2 39.4 24.0 19.8 31.2
21.5 14.5 5.8 29.3 41.5 34.8 7.9 12.0 19.3 18.3
9.9 37.6
ra8
nb8
bc8
37
29.0 48.8 51.2 51.7 51.8 52.0 49.3 32.0 31.4 53.4
56.0 54.2 53.7 57.2 53.0 33.1 37.8 66.5 66.4 62.0
64.7 70.6 71.2 42.8 38.6 60.2 63.1 59.7 59.1 70.5
66.3 46.2 27.9 37.0 37.1 34.3 34.3 41.3 42.3 32.6
65.6 51.7 82.8 68.1 60.1 54.7 35.9 50.9 47.0 29.9
32.0 38.6 49.6 36.3 17.9 18.8 34.9 22.9 22.0 36.7
23.3 6.3 15.7 19.3 26.5 6.9 18.0 22.6 21.9 16.2
23.2 26.8
48.9 53.6 53.9 50.0 63.5 59.0 87.6 64.5 39.4 42.8
45.1 44.1 42.8 37.1 53.2 52.7 44.8 48.4 36.4 28.4
34.7 23.5 37.9 28.3 46.0 29.0 28.7 9.1 14.0 24.3
17.9 30.3 38.6 36.1 25.4 18.9 10.1 20.1 28.0 27.8
42.4 24.0 8.4 22.0 13.0 16.0 12.0 32.9 44.0 36.5
41.0 10.1 23.7 19.4 20.9 22.6 26.4 18.5 16.3 16.0
18.4 7.9 21.1 26.3
ke8 bf8 ng8
57.8 56.8 52.3 47.9 54.3 73.3 65.1 79.5 43.0 41.3
38.9 36.4 37.5 31.9 45.3 46.2 51.3 46.6 37.6 31.6
32.7 37.4 48.6 49.2 56.8 45.1 38.8 30.7 28.1 34.8
41.8 48.1 63.9 53.1 43.7 33.0 29.7 33.7 44.6 45.8
69.5 54.3 43.9 37.1 29.3 27.3 35.7 50.6 76.1 66.2
55.6 42.1 38.1 40.6 47.6 63.7 64.0 51.4 33.7 21.3
19.5 18.5 38.5 45.6
95.6 85.7 74.1 78.4 73.9 64.5 62.0 75.5 82.8 91.2
84.9 85.4 84.6 78.9 82.6 76.1 76.0 52.9 84.7 84.0
82.7 83.2 85.4 84.6 65.2 24.2 38.4 82.2 83.6 82.6
85.8 87.2 55.0 20.2 26.5 75.5 83.2 83.4 87.0 88.8
50.8 18.2 21.0 61.3 85.6 84.9 89.3 91.4 50.9 42.7
44.1 75.9 91.0 91.3 95.0 95.8 48.4 49.7 65.5 83.6
91.5 85.7 95.1 96.5
82.1 92.4 83.7 79.4 74.9 63.6 60.4 64.5 84.0 75.4
87.8 86.3 83.8 79.1 82.0 74.1 45.6 73.2 47.4 83.6
82.8 80.8 84.8 82.1 32.8 50.8 35.0 35.0 80.7 83.6
84.8 87.4 19.9 42.3 23.2 22.1 42.9 82.8 86.8 88.5
20.9 33.2 16.7 29.8 39.6 71.2 88.3 91.2 45.2 47.5
40.2 39.8 60.6 77.4 93.5 95.5 51.6 52.2 45.6 54.9
77.7 81.7 94.4 96.4
70.5 80.0 89.4 81.9 73.9 64.4 59.4 59.5 77.6 90.0
73.1 86.6 83.4 78.0 81.6 67.3 83.7 52.3 60.4 40.4
82.2 79.9 83.9 81.1 36.4 25.4 44.2 30.9 32.1 82.2
85.3 86.8 29.4 21.9 41.2 6.8 22.9 63.8 86.3 88.5
18.7 15.2 23.9 23.1 19.8 25.9 85.2 90.9 44.7 35.1
43.8 38.5 35.1 38.3 80.9 95.2 62.8 49.4 46.2 44.1
56.9 63.2 92.4 96.1
rh8 pa7 pb7 pc7
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess 69.0 72.8 76.9
86.7 75.8 69.3 64.5 62.6
{width="0.5204101049868767in"
height="0.7499518810148731in"}
74.9 87.4 84.3 84.5 83.6 80.6 84.2 70.8
82.8 88.1 69.3 59.4 55.1 80.4 85.5 82.5
87.4 37.1 42.2 22.8 20.6 52.3 85.1 87.6
71.9 25.9 12.1 35.5 13.6 21.7 83.9 88.7
55.0 11.9 15.4 26.6 19.9 8.7 40.2 90.1
50.8 32.8 37.9 37.7 35.7 23.8 37.1 83.9
67.3 59.0 41.5 44.7 46.9 44.8 71.2 91.7
64.5 68.7 72.1 79.6 87.6 74.4 66.5 62.1
71.0 85.6 82.2 85.8 76.8 81.6 86.3 69.9
81.4 86.8 82.3 44.3 65.5 62.8 86.0 80.9
87.5 87.0 47.4 27.8 30.9 37.3 39.8 86.8
89.7 84.4 19.2 11.3 29.7 16.3 27.8 79.6
92.6 33.7 8.2 21.9 29.2 16.2 19.1 56.1
88.2 10.0 32.0 36.2 40.3 30.8 29.6 42.4
75.1 70.0 46.4 41.6 49.9 43.1 68.5 81.8
61.1 63.7 67.1 76.1 83.6 89.5 74.7 65.1
68.4 84.5 80.1 85.3 88.1 72.9 90.4 74.9
80.4 86.3 81.6 83.0 35.0 55.0 52.4 83.1
86.8 87.6 83.6 30.6 22.6 43.6 32.4 32.2
89.9 89.2 51.4 27.6 21.0 40.3 23.1 34.5
92.9 87.8 32.9 25.8 25.9 36.5 17.7 33.8
95.8 87.5 59.6 38.7 40.6 45.1 36.9 38.3
96.9 96.2 81.1 56.6 47.8 53.7 59.1 75.9
66.0 64.6 65.3 75.9 78.3 82.6 91.4 76.6
76.2 84.2 81.0 85.0 86.7 87.3 82.7 80.1
81.4 87.2 82.6 83.5 84.0 47.5 70.7 42.4
86.8 86.7 85.6 82.6 35.1 34.9 47.1 32.0
89.3 89.4 84.5 57.8 24.9 24.4 36.5 26.3
93.6 91.6 82.0 50.0 31.4 22.2 35.0 26.7
96.2 96.2 89.3 68.9 42.1 38.3 47.7 41.3
98.1 97.7 94.2 82.9 62.6 51.9 60.6 59.0
38
pd7 pe7 pf7 pg7
76.8 66.1 65.3 73.9 75.9 72.4 82.4 95.2 76.7 85.1
80.0 85.2 85.3 84.7 91.8 84.5 83.9 86.4 84.3 82.5
83.8 82.9 56.5 74.1 86.2 87.3 83.2 85.0 81.7 36.7
25.1 62.1 89.5 88.8 84.9 83.9 73.0 24.4 21.6 52.5
93.3 92.1 87.0 86.5 60.5 24.3 16.6 51.9 96.1 96.1
92.9 90.8 74.3 30.4 36.1 51.7 97.7 97.4 94.2 90.9
84.0 60.7 56.5 53.7
47.5 49.5 64.2 82.3 91.4 85.1 95.1 96.3 49.8 42.7
44.2 72.5 90.1 91.2 94.7 95.5 49.2 18.7 21.6 54.1
84.5 85.2 89.0 91.6 54.5 18.0 29.1 71.0 82.1 82.8
86.9 88.7 63.6 24.7 38.0 81.1 83.1 81.3 85.9 87.1
74.3 55.0 83.4 83.7 82.2 83.2 85.2 85.2 83.2 91.3
84.4 84.9 84.4 78.5 82.5 76.5
ph7
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess 61.1 57.3 40.5
43.0 44.8 40.3 70.0 90.4
{width="0.5204101049868767in"
height="0.7499518810148731in"}
50.1 28.3 36.3 36.7 32.9 19.4 32.0 87.7
52.6 13.7 12.5 24.8 14.9 9.5 47.5 90.4
80.9 23.7 11.4 31.6 16.1 22.9 84.6 88.1
87.5 41.0 40.1 24.2 27.0 60.6 84.8 87.8
81.6 88.1 64.6 64.5 55.3 80.6 85.2 83.1
73.3 87.4 82.2 87.3 84.6 79.6 83.3 71.3
66.6 71.7 74.6 86.2 78.7 70.0 65.3 65.1pd2
72.4 68.7 40.9 37.8 46.3 36.5 59.3 77.5
91.6 19.3 27.6 32.7 34.2 24.5 19.3 43.6
92.6 54.2 7.7 13.7 23.5 10.6 16.7 65.4
89.4 87.9 25.3 9.5 28.6 16.0 30.1 84.8
87.4 86.5 64.6 30.8 34.5 39.4 48.5 86.8
81.3 87.1 81.5 44.1 69.1 63.6 85.3 82.4
72.1 85.9 81.5 84.4 80.5 81.2 85.6 73.0
94.8 83.6 72.6 77.5 73.0 65.1 63.4 76.3pa2 51.9 52.2
46.0 56.6 78.9 82.0 94.6 96.7
45.3 47.3 41.2 39.5 59.1 76.3 93.8 95.3
21.8 35.6 18.7 30.4 35.4 71.7 88.4 91.7
20.1 40.0 24.0 19.5 43.6 82.3 86.9 88.1
31.6 48.7 34.2 38.9 80.7 82.9 85.1 87.1
45.3 71.4 47.4 83.6 82.7 81.2 85.1 83.7
81.5 74.1 87.0 85.9 83.7 78.9 81.8 75.2
78.1 91.4 83.1 79.2 75.4 64.1 62.8 65.8pb2 62.8 49.5
46.7 42.8 54.0 59.2 90.6 95.7
44.8 39.1 44.0 37.7 32.8 30.0 77.2 94.9
17.6 14.3 30.4 25.3 15.4 24.7 85.4 90.8
29.8 18.9 38.7 11.8 25.9 66.3 85.8 88.1
35.7 24.9 40.2 28.8 36.1 80.6 85.0 86.3
82.2 52.7 60.5 42.3 82.3 79.7 84.7 81.7
74.6 89.8 74.0 86.7 84.0 78.2 81.4 68.2
66.9 78.0 88.5 82.6 75.5 65.9 60.7 60.7pc2 39
64.5 67.9 69.6 78.4 86.1 74.8 69.5 66.7pe2 96.7 96.3
78.1 52.2 46.1 51.3 55.9 73.2 96.1 90.4 55.3 33.7
38.8 41.4 33.5 37.1 93.1 89.5 39.5 20.2 19.9 33.3
14.1 33.5 89.9 88.9 57.7 26.5 22.7 33.7 25.1 34.1
86.4 87.8 83.7 33.9 27.3 44.4 32.0 33.7 79.0 86.1
81.3 83.3 40.2 61.5 54.5 84.2 66.3 84.6 80.4 85.7
88.1 79.1 90.1 77.2 59.0 62.4 65.7 75.9 84.6 90.5
78.7 69.3pf2 98.1 97.5 93.6 80.4 62.3 50.2 59.3 57.3
96.4 96.3 89.3 65.6 39.4 34.9 47.5 41.3 93.8 91.8
83.7 49.8 27.4 21.7 33.2 26.9 89.2 89.6 84.3 61.9
23.7 21.0 39.4 24.1 86.4 86.7 85.7 82.7 37.8 34.3
47.4 33.5 81.0 86.8 82.2 83.7 84.6 49.1 72.9 41.7
73.9 84.3 80.5 85.5 86.8 87.8 84.8 83.4 64.1 63.1
64.4 75.7 79.2 83.7 92.5 79.7pg2
97.5 97.4 93.3 90.2 83.3 58.2 55.0 53.2 96.3 96.3
92.6 90.0 74.3 26.8 34.7 51.7 93.2 92.1 86.8 86.7
55.7 25.0 13.0 54.2 89.4 88.5 84.7 83.2 75.4 22.6
23.2 51.7 86.2 87.5 83.2 85.2 81.6 37.7 25.5 62.6
82.5 86.4 84.6 82.7 84.5 83.5 58.8 76.5 75.1 84.5
80.2 85.5 85.6 85.4 91.3 87.7 74.9 65.2 65.3 74.8
77.7 74.1 84.5 95.7ph2
31.0 35.9 22.1 17.9 25.7 25.9 46.8 60.4 66.0 61.3
52.0 41.1 42.1 41.4 50.3 72.1 52.2 47.3 36.5 35.5
34.3 36.2 42.3 62.1 46.2 47.5 37.0 30.5 33.8 39.0
48.3 60.2 42.3 38.9 33.3 29.6 32.1 40.4 47.7 60.9
42.1 45.7 33.0 35.3 37.1 43.7 53.5 59.9 48.3 38.7
39.0 39.4 40.9 41.0 46.7 49.6 81.7 64.2 55.9 59.7
55.3 60.9 67.0 67.2Ra1
27.2 21.7 11.4 19.5 19.2 11.4 21.7 24.8 35.8 28.3
39.8 21.0 18.1 29.1 20.2 37.7 35.9 17.8 23.9 19.2
24.0 10.1 22.7 36.0 35.7 29.4 19.9 9.7 18.4 25.3
34.4 37.9 42.5 24.6 27.7 19.5 10.2 28.4 30.0 38.1
44.2 50.7 29.9 37.2 33.3 36.0 42.0 45.1 51.4 45.4
46.1 45.6 46.2 43.8 51.5 51.8 48.5 92.4 53.6 61.7
50.8 62.0 58.0 61.9Nb1
19.0 17.7 9.4 40.2
42.8 38.0 6.5 8.8
25.4 18.5 6.6 28.2
44.3 22.8 19.4 30.4
26.1 21.3 29.5 41.8
49.1 37.6 30.9 33.3
57.9 37.3 47.3 64.9
62.5 86.3 55.2 61.3Bc1
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess 69.8 55.6 51.8
14.6 51.5 54.4 60.9 79.0
{width="0.5204101049868767in"
height="0.7499518810148731in"}
75.2 69.8 57.6 36.4 36.2 66.8 74.5 85.3
60.5 28.4 41.3 33.1 39.8 30.7 46.1 69.2
49.3 43.2 35.5 27.5 31.4 36.2 36.6 61.9
58.7 36.8 43.5 25.4 32.4 35.6 39.0 52.7
53.7 52.0 39.3 43.7 36.7 36.8 43.0 51.7
59.3 49.1 58.6 45.1 44.2 34.4 35.7 45.2
52.8 55.5 50.8 59.3 47.6 41.5 44.9 55.3Qd1
28.6 38.2 38.1 34.3 33.6 40.2 41.3 31.9
38.3 60.4 64.1 59.7 58.7 69.6 66.2 46.2
37.9 66.8 67.0 62.1 64.7 70.2 71.2 43.3
32.4 54.5 57.1 55.1 54.2 58.4 53.0 34.3
30.1 49.6 52.1 51.8 51.6 52.3 49.3 33.1
32.7 48.1 50.5 47.3 48.9 52.0 51.4 38.9
42.6 53.7 51.2 48.9 48.5 55.5 57.7 51.0
33.0 51.7 59.2 32.2 56.6 36.8 61.5 44.1Ke1
21.9 15.7 24.3 22.1
20.3 5.7 16.8 21.4
19.5 6.1 15.5 20.8
31.9 19.9 18.5 37.0
46.2 37.3 17.7 22.6
46.1 33.2 33.8 43.6
65.2 59.7 38.6 53.6
71.3 54.1 83.2 66.1Bf1
25.6 17.5 14.8 17.4 20.2 7.5 21.7 33.8
42.5 32.1 43.7 8.3 20.9 18.7 18.9 23.8
41.1 28.9 6.8 24.6 15.8 16.5 12.3 32.0
40.9 33.0 26.5 19.7 10.1 18.5 28.5 31.9
44.0 30.8 27.5 9.0 15.2 27.9 19.1 28.6
43.9 47.9 37.0 32.6 37.2 25.6 43.9 35.5
38.5 41.4 45.0 43.3 44.1 42.7 52.8 58.1
47.9 51.8 53.7 50.0 60.2 58.3 91.6 63.6Ng1
40
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
59.6 49.8 32.0 20.8 18.7 17.9 38.0 43.8
75.1 65.9 55.8 42.5 37.8 39.9 46.3 62.2
68.7 54.7 44.3 37.6 29.8 27.0 35.7 49.6
63.6 52.9 42.8 31.7 29.3 30.6 43.6 41.2
56.7 45.2 37.5 30.0 28.8 34.4 42.3 49.1
51.7 47.0 35.6 34.8 36.5 39.3 51.8 54.7
43.9 40.3 38.6 37.7 40.3 33.9 44.6 49.4
57.5 56.6 51.0 51.5 59.4 74.5 67.2 82.8Rh1
Aside from admiring the groovy pictures, the data can also be used as
the basis of an algorithm for playing chess. There are several things to
try; we could move pieces towards squares where they are more likely to
survive than die (keeping pieces alive is good), or just towards squares
where they are more
Actual ♙h 71% ♟a 70% ♙a 70% ♟h 70% ♙g 66% ♟g 65% ♙b 60% ♟b 59% ♙f 57% ♖a
56% ♜a 55% ♟f 55% ♖h 54% ♜h 54% ♔ 53% ♚ 50% ♙c 47% ♕ 45% ♟c 45% ♛ 44% ♟e
37% ♝c 32% ♟d 32% ♝f 32% ♙e 31% ♗c 31% ♗f 30% ♙d 30% ♘b 29% ♞b 26% ♞g
24% ♘g 23%
William ♖a
♜a
♙b
♟b
♙a
♟a
♗f
♝f
♙c
♟c
♕♛♔♚♙h
♟h
♗c
♝c
♙f
♟f
♙g
♟g
♘b
♞b
♖h
♜h
♘g
♞g
♙d
♟d
♙e
♟e
Jim ♔♚♖a ♜a ♖h ♜h ♙a ♟a ♙b ♟b ♙g ♟g ♙h ♟h ♘b ♞b ♘g ♞g ♙c
♟c
♙d ♟d ♙e ♟e ♙f
♟f
♗c ♝c ♗f
♝f
♕♛
Actual ♙h 71% ♟a 70% ♙a 70% ♟h 70% ♙g 66% ♟g 65% ♙b 60% ♟b 59% ♙f 57% ♖a
56% ♜a 55% ♟f 55% ♖h 54% ♜h 54% ♔ 53% ♚ 50% ♙c 47% ♕ 45% ♟c 45% ♛ 44% ♟e
37% ♝c 32% ♟d 32% ♝f 32% ♙e 31% ♗c 31% ♗f 30% ♙d 30% ♘b 29% ♞b 26% ♞g
24% ♘g 23%
David ♙g 72% ♟g 72% ♙b 69% ♟a 66% ♟b 65% ♔ 65% ♙a 64% ♚ 55% ♟f 54% ♙f
54% ♟h 52% ♙h 52% ♖h 52% ♜h 52% ♖a 51% ♜a 51% ♙c 49% ♟c 44% ♗f 33% ♝c
33% ♗c 32% ♝f 32% ♕ 31% ♛ 30% ♘g 29% ♞g 29% ♘b 28% ♞b 28% ♙e 19% ♟d 18%
♙d 17% ♟e 16%
Tom ♙f
♟f
♙c
♟c
♙g
♟g
♙a
♟a
♙h
♟h
♙b
♟b
♖h
♜h
♖a
♜a
♔♚♕♛♗f
♝f
♗c
♝c
♘g
♞g
♘b
♞b
♙e
♟e
♙d
♟d
Actual ♙h 71% ♟a 70% ♙a 70% ♟h 70% ♙g 66% ♟g 65% ♙b 60% ♟b 59% ♙f 57% ♖a
56% ♜a 55% ♟f 55% ♖h 54% ♜h 54% ♔ 53% ♚ 50% ♙c 47% ♕ 45% ♟c 45% ♛ 44% ♟e
37% ♝c 32% ♟d 32% ♝f 32% ♙e 31% ♗c 31% ♗f 30% ♙d 30% ♘b 29% ♞b 26% ♞g
24% ♘g 23% 
{width="0.5204101049868767in"
height="0.7499518810148731in"}
Ben ♙h
♟h
♙a
♟a
♙f
♟f
♙g
♟g
♙b
♟b
♖h
♜h
♖a
♜a
♙e
♟e
♙d
♟d
♕♛♔♚♙c
♟c
♗c
♝c
♗f
♝f
♘b
♞b
♘g
♞g
likely to be positioned at the end of the game (our moves are more
likely to resemble real chess moves because they put pieces in their
proper places). Alas, it turns out that these are bad approaches to
chess, both because they are boring (most pieces are actually most
comfortable in their starting positions) and because they perform
badly against even weak opponents [3].4 Guesses and slices
Like all good scientific research, I explicitly compare the ac tual
results to the hypotheses gathered before the experiment; this is an
hygenic and humbling exercise. Figure 2 compares the ranking across all
games (slice Actual) to the author au thor (slice Tom) and his drinking
buddies (slices Ben, Jim, David, William). There are a number of
different reasonable ways to measure the accuracy of this type of
position; a very simple one is the sum of the absolute differences in
rank for each piece (e.g. if in one ranking Kis #3, and in the other #5,
then this contributes 2 to the total error). By this metric, Ben has the
best prediction (98 error), followed by David (138) and Tom (148). Tom
and David had the most similar predictions (116) and Jim and William the
most different (312). The ex pected error between two completely random
permutations is about 341, so all of these guesses are significantly
better than chance. Note in the actual ranking, many pieces have very
similar survival probabilities, and many guesses are ambiva lent about
groups of pieces. Weighting each rank difference equally is therefore an
oversimplification. It would have been better to ask each participant to
give probabilities, as David did; this would give us more sensitive
error metrics and more opportunities to spend the afternoon making
visualizations.
Several drinking buddies gave rationales for their hypotheses (mine
appear in Section 1).Ben does not prefer to use the shift key, a typographic quirk I
replicated faithfully here even though it burns my eyes:edge pawns almost never played til endgame let alone traded off (ph,
pa)Figure 2: Piece rankings (from most surviving to most dead); either a
human or hypothesis or the actual results across all games. The actual
column appears multiple times so that each human gets a chance to be
adjacent to it; this makes for the easiest visual comparison. Lines
connect the same piece in adjacent columns, and are darker if the
pairs have more different ranks.not quite sure where these should go (pb more likely to see play in
queenside minority attacks in k-side castle games?) (pf, pg, pb)rook play more likely to be active on q side than on k side (also the
classic Nxc7 fork in low rank play), but overall more likely to stay
tucked away compared to q (Rh, Ra)i think IQP positions are more likely than not saccing e in e4
openings but on the other hand d is often traded off in e4 openings
while vice versa is not as true (pe, pd)q probably involved in many checkmates (low ranked play) or
resignations before traded off (high ranked play) (Q)just randomly guessing k dies in about ⅓ of games, times ½ for 2
sides (K)
this pawn is a super goner (sicilian, QGA, ...) (pc)
most doomed seem to be the minor pieces as i'd guess at least half of
them get traded off on c/f/3/6 or e/d/⅘ in near every game so (Bc,
Bf, Nb, Ng)Jim "barely understands the rules of chess" and "rarely plays." His
justifications get "increasingly nonsensical:"Most-to-least-survival hero tier list for chess (patch 1.0):
1.: King --- If I estimate that about ⅔rds of all regular pieces are
captured in an average game, and the probability of any non-king piece
being captured is uniform, then the king is clearly the most likely to
41
survive. (I'm going to break symmetry here and rank
All
Bullet
Blitz
Rapid
Classical
Titled
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
black king less likely to survive than white king.)
2. Both Rooks --- Kept in reserve for castling pur poses.
3. The A, B, G, and H pawns --- maybe people will forget to move them
because they are far from the center.
4. Both Knights --- They are slippery, but they often get deep into
enemy territory quickly.
5. The C,D,E,F pawns --- Moved forward to release various more
important pieces ⇒ more likely to die.
6. Both Bishops --- https://youtu.be/gDnE-5lD7w8
7. The Queen --- A high-value target, seems unlikely to survive.
David simply provided a ranking, along with survival prob abilities, in
typical understated style.
William notes that his guesses are "pretty much off the cuff," but
provides some motivated reasoning:
I figure the king has got to be somewhere near the middle of the pack
since he dies in half of games
♙h 71% ♟a 70% ♙a 70% ♟h 70% ♙g 66% ♟g 65% ♙b 60% ♟b 59% ♙f 57% ♖a 56% ♜a
55% ♟f 55% ♖h 54% ♜h 54% ♔ 53% ♚ 50% ♙c 47% ♕ 45% ♟c 45% ♛ 44% ♟e 37% ♝c
32% ♟d 32% ♝f 32% ♙e 31% ♗c 31% ♗f 30% ♙d 30% ♘b 29% ♞b 26% ♞g 24% ♘g
23%
♟a 72% ♙h 72% ♙a 72% ♟h 70% ♙g 66% ♟g 65% ♙b 61% ♟b 61% ♙f 56% ♟f 55% ♖a
54% ♜a 54% ♔ 52% ♜h 52% ♖h 52% ♚ 50% ♙c 47% ♟c 44% ♕ 42% ♛ 41% ♟e 38% ♙e
30% ♝f 30% ♝c 30% ♗f 30% ♟d 30% ♙d 29% ♗c 28% ♘b 26% ♞b 24% ♞g 21% ♘g
21%
♙h 70% ♟h 69% ♙a 68% ♟a 68% ♙g 65% ♟g 64% ♙b 59% ♟b 58% ♙f 56% ♖a 56% ♜a
55% ♟f 55% ♖h 54% ♜h 54% ♔ 53% ♚ 50% ♙c 46% ♕ 46% ♛ 45% ♟c 43% ♟e 37% ♟d
32% ♝c 31% ♝f 31% ♙e 31% ♗c 30% ♗f 30% ♙d 30% ♘b 28% ♞b 26% ♞g 24% ♘g
22%
♙h 71% ♟h 70% ♙a 70% ♟a 69% ♙g 66% ♟g 65% ♙b 60% ♟b 59% ♖a 59% ♙f 58% ♜a
58% ♖h 57% ♜h 56% ♟f 55% ♔ 54% ♚ 50% ♙c 49% ♕ 48% ♟c 47% ♛ 47% ♟e 35% ♝c
34% ♟d 34% ♗c 34% ♝f 33% ♘b 32% ♙d 32% ♗f 31% ♙e 31% ♞b 29% ♞g 27% ♘g
26%
♙h 75% ♟h 74% ♙a 74% ♟a 73% ♙g 70% ♟g 69% ♙b 64% ♖a 63% ♙f 63% ♟b 63% ♜a
62% ♖h 61% ♜h 61% ♟f 59% ♔ 54% ♙c 54% ♟c 52% ♕ 52% ♛ 51% ♚ 50% ♝c 41% ♗c
40% ♝f 39% ♟e 39% ♘b 39% ♟d 38% ♗f 37% ♙d 37% ♞b 35% ♙e 35% ♞g 33% ♘g
32% 
{width="0.5204101049868767in"
height="0.7499518810148731in"}
♙h 66% ♟a 66% ♙a 66% ♟h 65% ♙g 62% ♟g 60% ♙b 56% ♟b 56% ♔ 53% ♙f 53% ♟f
52% ♚ 51% ♜a 49% ♖a 48% ♖h 47% ♜h 47% ♙c 42% ♕ 39% ♛ 38% ♟c 37% ♟e 36%
♝f 31% ♗f 30% ♙e 30% ♝c 28% ♟d 28% ♗c 27% ♙d 25% ♘b 23% ♞b 23% ♞g 20% ♘g
20%
featuring a winner---but with slightly higher-than even odds of
surviving, since some games end in a draw. I'm probably mixing up
means and medians here somehow..I'm gonna assume castling happens more often on the King's side, so
let's give Kingside Rook and F, G, and H Pawns a better shot than
their fellows on the left. But maybe it should actually be worse,
since if they die, it's because they failed to protect the king. Plus,
having heard the tip about C Pawn5loud and clear, I'm gonna assume
that bad boy most often becomes a new Queen, which means he gets more
survival points than the real Queen herself.D and E Pawn are nothing but pawns, and they mostly sacrifice
themselves to the cause.Randomizing within these constraints gives us our starting point. Then
the wildcard Bishops and Knights get randomly distributed through what
re mains to come up with this final answer shown above.4.1 Slices
The survival probabilities differ depending on the conditions of the
game; Figure 3 compares some of those slices. Here the All slice is
the same as the Actual column in Figure 2, and consists of all
acceptable games in the database.
The Titled slice includes only games where at least one of the players
has an official title (Grandmaster, International Master, FIDE Master,
etc.6). These games have high-quality
5I believe the "tip" here was that I described the rest of us (William
was the last respondant) as disagreeing most on pc. I think William
misinterpreted this "tip."
6Lichess used to award the LM "Lichess Master" title to notable play
ers on the site; this title is excluded from the sample.Figure 3: Ranks and survival probabilities for different sub sets of
games. The same piece in adjacent rows is connected to highlight
differences in the ranking, as before. The time formats all exhibit
similar ranking with only small perturba tions. Games including a
titled player (rightmost column) are the most different, although we
have far fewer samples in this set, so variance becomes significant.play, but far fewer samples ("only" 3.4 million). This set ex hibits
significant variance; for example, the survival rate of pc ranges from
38--46%. This is both because of the small sample size and the
bucketization by player name; there are few enough titled players that
an individual's preference in openings and style of play changes the
values of their entire bucket. I caution against reading too much into
this column. It seems we can at least conclude that these games tend
to be much bloodier (Kings aside, survival rates are lower across the
board); top players are less likely to fall for traps early in the
game, perhaps more willing to sacrifice material, and more likely to
play into endgames where almost every piece is exchanged. If being a
chesspiece to the death, you do not want to have a Grandmaster playing
the game!On the other hand, the other slices all have enough samples that the
variance is minimal. These slices, Bullet (151,261,707 games), Blitz
(236,050,938 games), Rapid (98,606,558) and Classical (13,886,352) are
different time control formats. Games on Lichess are played with a
starting clock (per side) and an increment added to the clock after
each player's move. The game is classified according to the estimated
total time: The starting time plus 40× the increment (with the idea
that an average game has 40 moves per side); this is the same for mula
that Lichess uses. A bullet game is when the total time per side is
between 30 seconds and 3 minutes; blitz is between 3 and 8 minutes;
rapid is between 8 and 25 minutes; classi cal is any more than this
(including untimed games). Each of
42
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess
{width="0.5204101049868767in"
height="0.7499518810148731in"}
these slices has enough samples that the variance is very low.
Here we see that the ranking is rather stable across the range
of time formats, which was not what I expected. This should
increase our confidence that the results are really inherent to
chess, not just the particulars of this data set.
References
[1] FIDE handbook -- E.I.01A. Laws of chess, 2017. www.fide.
com/component/handbook.
[2] Tom Murphy, VII. CVE-2018-90017117. In A Record of
the Proceedings of SIGBOVIK 2019. ACH, April 2019.
[3] Tom Murphy, VII. Elo World: A framework for bench
marking weak chess algorithms. In A Record of the Pro
ceedings of SIGBOVIK 2019. ACH, April 2019.
[4] Tom Murphy, VII, Ben Blum, and Jim McCann. It still
seems black has hope in these extremely unfair variants of
chess. In A Record of the Proceedings of SIGBOVIK 2014,
pages 21--25. ACH, April 2014. sigbovik.org/2014.
43
Optimizing The Sacrifice
7
Nico Zevallos
Abstract---This work aims to finally fix a glaring issue in Andrei
Tarkovsky's final opus Offret (The Sacrifice) [1] namely, the
inefficiencies of its final six minute shot.I. INTRODUCTION
Fig. 1. A frame from the final shot of Offret
THERE are perhaps a handful of directors whose oeuvres
are as universally venerated as that of Andrei Tarkovsky. Who among us
could find fault in the work of a man Ingmar Bergman called "The
greatest, the one who invented a new language, true to the nature of
film, as it captures life as a reflection, life as a dream [2]." And
yet as one watches Offret, one error looms. This 1986 masterpiece of
Swedish cinema is marred by its famous final sequence. In it, the
paterfamilias, Alexander, burns the family's home to the ground in an
attempt to honor an agreement with God to undo a nuclear apocalypse. In
a single, six minute long take, the family chases him as their house
burns to the ground, splashing through and falling into the mud,
occasionally collapsing in despair, and finally pushing him onto an
ambulance that rolls away into the swamp. The family then watches as
their house collapses onto itself in a glorious blaze, all the grandiose
posturing of an aging academic conflagrated by a single act of faith.
As one watches this moving scene, one cannot help but think: Couldn't
the family have captured and committed its crazed patriarch much more
efficiently? The shot itself had to be re-done when a camera jammed
during the first attempt, causing the crew to rebuild a perfect replica
of the house from scratch to set fire to it a second time. Although
nothing can be done at this point about the inefficiencies of the film's
production, this paper seeks to optimize the paths the family takes as
they rush to confront Alexander such that they may watch their home burn
without the additional discomfort of getting their feet wet, as well as
complete their task much faster.
II. RECREATING THE SCENE
The method for determining optimal, dry paths was as follows. The
first step was to track the movement of the camera in the scene. This
was done in the 3D modelling software Blender by creating rough models
of the static objects in the scene, estimating camera parameters by
eye, and manually moving the camera through the scene so that the
static objects match up. Based on footage from a documentary about the
film [3], the author constrained the movement of the camera to a
single degree of freedom of movement along the axis of the dolly that
the camera was on as well as two rotational degrees of freedom to
account for horizontal and vertical pans. The camera focal lengths
tested were 50mm, 70mm, 75mm, 85mm, and 100mm. Focal lengths below
50mm and above 100mm forced the author to make objects such as the
house and the cars unreasonably small or large in order to line them
up with the footage. After a rough alignment at each of these focal
lengths, 75mm was chosen as the ideal focal length because it produced
the fewest artifacts and distortions. Following this decision, the
footage was meticulously tracked by hand, adding about 1 key frame for
every 5 frames of footage and adjusting both the position of the
camera and objects in the scene until the entire six minute shot was
aligned. Once the shot was aligned, non-static objects representing
the characters could also be key-framed to match their position from
the camera's point of view, thereby finding their trajectory in the
recreated 3D space. The recreated scene, including renderings of the
house and cars present in the film as well as Alexander's trajectory
through the scene can be seen in Fig. 2.Fig. 2. Recreated scene with Alexander's path overlayed
The second step was to create a cost map for the path planner. The
aligned footage was projected onto a plane to recreate the ground
plane. This was done by repeatedly finding a frame in which a portion
of the ground was visible, and then painting that portion of the
ground onto the recreated ground plane similarly to the 'screen space
brush' method44
described by Hanrahan and Haeberli[4]. This reconstructed ground
plane had a threshold applied to create a cost map, and unreachable
areas such as those inside the house or under cars were manually
marked as infinite cost. The resulting cost map can be seen in Fig. 3.Fig. 3. Texture-painted ground plane on left and generated cost map on
rightIII. CALCULATING OPTIMAL PATHS
Once this cost map was created, the optimization could begin. This cost
map was used to calculate how much of the path passed through 'water'
pixels. This was done using Bresenham's line algorithm [5] to find the
pixels covered by the path and finding the ratio of grey (in the water)
to white (on dry land) pixels. This cost map was also used in
conjunction with the A* planning algorithm [6] as an 8-connected grid
in order to find paths that avoided wet areas. A* was chosen as it has
the pleasant properties of being extremely fast, complete, and
guaranteed to produce optimal paths.
One downside to the use of a grid representation, however, was that the
paths were optimal only on the discrete space, where at each pixel the
family member only has eight di rections they could move. In reality the
family could move in an infinite number of directions and weren't
restricted to moving from the center of one pixel to another. To
mitigate this effect, euclidean distance was used as the heuristic for
A* rather than the more traditional diagonal distance used in most
8-connected grid representations. This was chosen because although
diagonal distance is admissible in the 8- connected case, it can
overestimate distance in the continuous case. In practice what this
heuristic means is that paths tend to be closer to what they would be in
a continuous space, and less likely to zig-zag and take advantage of
cheap diagonal movement. An existing implementation found here was used
with some modifications: changing the heuristic to Euclidean
distance and changing the cost of diagonal movement to √2.
Finally, an additional relaxation step was applied in order to produce
smoother, shorter paths as proposed by Thorpe and Matthies[7]. An
overview of the path-finding is provided in Algorithm 1.
IV. OPTIMAL PATH RESULTS
As can clearly be seen in Table I, A* produces perfectly dry paths.
Even after relaxation, our method produces paths which are 99% dry.
The paths that are taken in the film range from 8-20% wet, leading two
characters to fall over face firstAlgorithm 1: Calculating optimal paths
input : pursuer location αT ,
n 2D target locations α = [αi, i ∈ N : i \< n]
target location αT
m × n grid of costs G
output: relaxed A* path p
Function Relax(p, G):
∇G ← ∇ GaussianBlur(G)
gradient ← [0, 0, ..., 0]
for i ← 1 to maxIterations do
for i ← 0 to Length(p) do
x, y ← pi
gradienti ← ∇Gxy
optimizeStep ← gradient + ∆p
optimizeStepstart, optimizeStepend ← 0
if ||optimizeStep|| \< 0.1 then
break
p ← p − optimizeStep
return path
Function Main(α, αT , G):
p ← AstarSearch(αi, αT , G)
if Length(pathnew) > 0 then
p ← Relax (pathnew, G)
else
continue
return p
into the mud. In addition, Table I shows that the paths taken in the
film are only marginally shorter than those found by A* and extremely
close to those found using Relaxed A*. All of these paths are
sub-optimal in terms of distance, which is clearly shown in the
comparison to running in a straight line. It is almost as if the
characters are going out of their way to get wet. Worse still, neither
Marta nor Julia ever reach Alexander, choosing instead to fall to
their knees a few meters short and are generally unhelpful for the
rest of the sequence. For ease of comparison, this excess distance was
added onto their 'Path in Film' lengths. As an additional
visualization of the irrational path choice of the characters,
Algorithm 1 was repeated for each frame and overlaid over the actual
video. The video can be found here.A portion of the sequence was chosen in which the entire family as
well as Alexander were all clearly visible, so that we could have an
apples to apples comparison of path quality without having to guess
the location of off-screen characters. The starting point for each of
the characters was set to their location at the first frame of the
sequence. Because Alexander stays in approximately the same place for
the entirety of this segment, the goal for each path was set to
Alexander's median location.
45
TABLE I
PERCENTAGE OF PATH SPENT IN WATER
Character A* Relaxed A* Path in film Straight line to goal Marta 0%
1.2% 12.8% 8.2% Victor 0% 1.3% 7.7% 21.8%
Julia 0% 1.1% 16.1% 9.7% Adelaide 0% 1.0% 19.5% 10.0%
20%
this behaviour, we formulate the scene as an evasion-pursuit problem.
First, a boundary is created which is a convex hull roughly
approximating the borders of the cost map, ignoring obstacles.
r
e
t
a
w
n
i
h
t
a
p
f
o
t
n
u
o
m
A
15%
10%
5%
0%
A* A* after relaxation Original path Straight line path
Fig. 4. Box plot showing results from Table I
TABLE II
LENGTHS OF PATHS
Character A* Relaxed A* Path in film Straight line to goal Marta
76.7 m 72.8 m 72.0 m 70.7 m Victor 63.3 m 60.2 m 61.8 m 58.0 mJulia 84.3 m 80.5 m 79.6 m 77.6 m Adelaide 82.7 m 78.6 m 79.3 m 76.1 m
90
85
80
)
m
(
ht
gn
e
l
ht
a
P
75
70
65
60
A* A* after relaxation Original path Straight line path
Fig. 6. Result of the pursuit algorithm, with pursuer paths marked in
red and evader path marked in cyan.
Fig. 5. Box plot showing results from Table II
V. PURSUIT AND EVASION
Although these comparisons are elucidating with regards to pursuer path
quality, the author was additionally curious about what would happen if
Alexander were actively trying to avoid capture, rather than wandering
about in despair. In order to test
Alexander employs the fleeing behaviour found in Algo rithm 2. This is
a very basic fleeing behaviour that avoids pursuers and coastal edges
weighted by their distance from Alexander. The pursuers attempt to
catch Alexander using Algorithm 3 which was developed by Huang et
al.[8]. This algorithm was chosen as it guarantees capture in finite
time and can be calculated in real-time. In this algorithm, rather
than pursuing the target directly, a Voronoi diagram is constructed.
Each pursuer checks if their region of the Voronoi diagram46
borders the target's region. If it does, they move toward the center of
the line defining the border between the two regions as fast as they
can. If the pursuers region does not share any border edges with the
target region, it simply moves toward the target as fast as it can. This
results in the pursuers surrounding the target rather than bunching up
during pursuit.
Previous work on this topic only performs simulation exper iments on
regions with square boundaries[8][9], which makes the calculation
of distance to edge as well as the calculation of the bounded Voronoi
diagram much simpler. In our case, the calculation was performed by
first reflecting all points about every edge in the boundary polygon.
The Voronoi diagram was then calculated using the union of the
original points and their reflections. These reflections could
additionally be used to calculate the distance from any point to all
of the boundary edges by taking the differences between a point and
each of its reflections and dividing by two.For the purposes of the experiments, all actors were assumed to run at
a human's optimal hunting speed of 3.3 m/s[10].Algorithm 2: Evasion algorithm
in : n pursuer locations α = [αi, ∀i ∈ N : i \< n] target location
αTconvex hull B with k edges [Bi, ∀i ∈ N : i \< k] out: Direction of
evasionFunction CalcPursuerDir(αT , α):
δ ← [0, 0]
for i ← 0 to Length(α) do
← αi − αT
δi ← /k k2
return δ
Function CalcEdgeDir(αT , B):
δ ← [0, 0]
for i ← 0 to Length(B) do
← CalcEdgeDist(Bi, αT )
δi ← /k k2
return δ
Function Main(αT , pursuers, B):
edgeDir ← CalcEdgeDir(αT , B)
pursuerDir ← CalcPursuerDir(αT , α)
δ ←PedgeDir +PpursuerDirreturn δ/kδk ∗ evaderSpeed
VI. PURSUIT AND EVASION RESULTS
To evaluate the effectiveness of our pursuit strategy, 100 trials were
run with random starting positions for all of the actors. For each of
these trials, the pursuers were given a maximum of one minute to
capture Alexander. Based on observing the original film footage, it
was determined thatAlgorithm 3: Pursuit algorithm
in : n pursuer locations α = [αi, ∀i ∈ N : i \< n] target location
αTconvex hull B with k edges [Bi, ∀i ∈ N : i \< k] out: Direction of
pursuit for each pursuerFunction Main(αT , α, B):
αref lected ← Reflect([αT , α], B)
regions ← Voronoi(αref lected)
for i ← 0 to Length(α) do
edge ← SharedEdge(regionsi, regionsT )
if edge 6= ∅ then
target ← (edgea + edgeb)/2
δ ← αi − target
δ ← δ/kδk
else
δ ← αi − αT
δ ← δ/kδk
return δ ∗ pursuerSpeed
it would take three pursuers to restrain Alexander and thus
successfully 'capture' him. Once a pursuer reached Alexander, they
would be removed from the Voronoi diagram and travel with him until
three pursuers had reached him, at which point the trial was ended and
reported successful. If three pursuers had not reached Alexander by
the end of the one-minute mark, the trial was reported as a failure.Alexander was caught in 100% of trials in an average of 16.3 seconds
with a standard deviation of 4.5 seconds. The maximum time to capture
was 28.0 seconds. In the film, Alexander runs free for a grand total
of 5 minutes and 37 seconds before he is forced into the ambulance.
VII. CONCLUSION
The results of this paper confirm our suspicion that the final
sequence of Offret contains a grave oversight when it comes to
common-sense path planning. Clearly, Tarkovsky and his cast did not do
even a cursory literary review. Otherwise, they would certainly have
come across A* ([6] was published more than a decade prior to the
release of the movie) and path relaxation ([7] was published more
than a year before principal shooting began). As our pursuit and
evasion results have shown, had the family employed even a simple
surrounding technique, they would have caught Alexander an order of
magnitude faster. Had the actors and director had the forsight to move
in a more coordinated fashion, Tarkovsky may not have had to shoot
this sequence twice, and even if he had, he would certainly have saved
some money on film. These unfortunate oversights show yet again that
the value of meticulous academic research trumps the brash, emotional
decisions of even the greatest artists. As roboticists, scientists,
and people of Reason, we continue to wonder: "Will they ever learn?"
47
REFERENCES
[1] Andrei Tarkovsky. Offret. Svenska Filminstitutet (SFI), 1986
[2] Paul Coates. Film at the Intersection of High and Mass Culture.
Cam bridge University Press. pp. 157-158, 1994.[3] Michal Leszczylowski Regi Andrej Tarkovskij. Svenska
Filminstitutet (SFI), 1988[4] Pat Hanrahan, Paul Haeberli. Direct WYSIWYG Painting and
Texturing on 3D Shapes. Computer Graphics, vol. 24, no. 4, pp. 215-223
August 1990.[5] Jack Bresenham. Incremental Line Compaction. The Computer
Journal, vol. 25, no. 1, pp.116-120, February 1982[6] Peter E. Hart, Nils J. Nilsson, Bertram Raphael. A Formal Basis
for the Heuristic Determination of Minimum Cost Paths.
Intelligence/sigart Bulletin - SIGART vol. 37. pp. 28-29, 1972.[7] Charles E. Thorpe, L.H. Matthies. Path relaxation: Path planning
for a mobile robot. Proc. AAAI, pp. 318-321, 1984.[8] Haomiao Huang, Wei Zhang, Jerry Ding, Duan M. Stipanovi, Claire
J. Tomlin. Guaranteed Decentralized Pursuit-Evasion in the Plane with
Multiple Pursuers. Proceedings of the IEEE Conference on Decision and
Control, 2011.[9] Zhengyuan Zhou, Wei Zhang, Jerry Ding, Haomiao Huang, Duan M.
Stipanovi, Claire J. Tomlin. Cooperative pursuit with Voronoi
partitions. Automatica vol. 72, pp. 64-72, 2016.[10] Karen L.Steudel-Numbers, Cara M.Wall-Scheffler. Optimal running
speed and the evolution of hominin hunting strategies. Journal of
Human Evolution. vol. 56, no. 4, pp. 355-360, April 2009.48
https://github.com/amazonlinux/rust-bundled-packaging/tree/b9c50d16b6d517c4e7483c6842b6f3cc77969b9d
{width="0.5204101049868767in"
height="0.7499518810148731in"}8
Abusing the RPM Package Manager to Compile Soware
iliana destroyer of worlds∗
Linux Witch
Amazon Web Services
ABSTRACT
e RPM Package Manager (RPM) is a popular Linux utility de signed to
destroy your computer. We extend its destructive capa bilities to
include dynamically building the list of upstream code sources based
on the list of upstream code sources.
ACH Reference Format:
iliana destroyer of worlds. 2019. Abusing the RPM Package Manager to
Compile Soware. In Proceedings of SIGBOVIK 2019, Pisburgh, PA, USA,
April 1, 2019 (SIGBOVIK '19), 3 pages.1 INTRODUCTION
e RPM Package Manager (RPM) [4] is an extremely dangerous Linux
program that should be avoided at all costs. Eects of use include
destruction of data, privileged arbitrary code execution, and in the
worst case, installation of a Linux operating system. Many Linux
distributions use RPM as their primary package manager; even more
don't.ere are two main modes for using RPM: compiling soware, usually with
the rpmbuild command, and installing soware, usu ally with the rpm -i
--force --nodeps1command.Modern programming languages, such as Perl, have their own package
management ecosystems. Within these ecosystems, seem ingly innocuous
soware can depend on multiple incompatible versions of the same
dependencies. is is, of course, an impossible issue to solve. It is
core to every packager's instinct to add all existing development
libraries to a Linux distribution, regardless of how useful those
libraries are to an end user, and to build all tools against
distribution-packaged libraries.Firecracker, an advanced chroot developed by AWS, is one such package
with many Rust dependencies. Nevertheless, we added Firecracker to
Amazon Linux, a Linux distribution maintained by a book store, without
building hundreds of useless RPMs. e solution we developed can, but
should not, be applied to other programming language ecosystems with
intractable dependency closures.
Most importantly, the solution is a complete hack that shouldn't work
and should have never been wrien.
2 RPM: THE GOOD PARTS
Recipes for RPM are called spec les (a sample is provided in List ing
1). ey begin with general metadata about a package, called the
preamble, such as the name, mailing address, Social Security number,
source tarball, and any patches. is is followed by the scriptlet
sections, which are Bash scripts; %prep unpacks and sews patches onto
the source code, %build builds it, and %install installs it into a
build root. Finally, %les lists the les installed from the∗Uppercasing of name is punishable by intergalactic law. Views
expressed do not necessarily reect Amazon's.1-i --dont --force --nodeps and neither should you.
49
Listing 1: A spec le
Name: robotndskien
Version: 2.7182818.701
Release: 4%{?dist}
Summary: A zen simulation
Source0: hp://robotndskien.org/.../%{name}-%{version}.tar.gz Patch0:
nki-makele.patchBuildRequires: ncurses-devel
%prep
%autosetup -p1
%build
%congure
%make [b]{.underline}uild
%install
%make [i]{.underline}nstall
%les
%{ [b]{.underline}indir}/%{name}
%changelog
∗ Sun Dec 10 2017 iliana weller \<ilianaw@buslol.net> - Update to
2.7182818.701 (#1297151)build root, and %changelog lists who broke your business-critical
soware. [1]Note the complete lack of any common shell commands which one normally
nds in Bash scripts. ey're all hidden away behind macros to take away
any artistic expression that soware packaging once had, ensuring that
all code is built with exactly the same con- gure and make options.
[3] To ensure consistency in a distribution, this is coupled with a
stringent and continuous review process... wait, spec les oen get
reviewed once and never again? Oh.When a user feeds the spec le to rpmbuild, it most likely fails
spectacularly. Sometimes it doesn't, though, and the user gets RPMs as
output. RPMs are kind of like a candy-coated tarball; a hard,
metadata-rich exterior breaks open to reveal a gooey cpio lling.2.1 ousands of Packages You Can't Use A common rule in Linux
distributions is "one project, one source
package" [3]. is means that the TEX Live distribution in Fedora is
represented by a single 220,000-line spec le generated by a script
[5], while each of the 780,000 dependencies available on npm must
have a separate spec le.https://github.com/amazonlinux/rust-bundled-packaging/tree/b9c50d16b6d517c4e7483c6842b6f3cc77969b9d
{width="0.5204101049868767in"
height="0.7499518810148731in"}Dedicated Python scripts, assisted by obedient packagers, take this
rule to its extreme. In Fedora 27 there were 1,129 package names
prexed with nodejs, 465 package names prexed with golang, and 132
package names2prexed with rust. [5] e scripts can recursively nd
dependencies, commit spec les, and start builds.Fedora is not alone; Debian has over 450 Rust source packages; each
one builds several binary packages for dierent feature ags. ese
packages commonly install source code to distribution dened le paths
that are ignored by the tools that know how to compile this code. ey
are dead weight in repository metadata, and adding too many Rust
packages incurs the risk of package repository oxidization.2.2 One Version Ought To Be Enough For Anybody3
fd4is a Rust utility for nding les. We inspected the Cargo.lock le
for fd version 7.3.05, which lists its full dependency closure. In
order to compile fd, we need two versions of rand core (0.3.x and
0.4.x), as well as two versions of winapi (0.2.x and 0.3.x).
In the usual Linux distribution dependency model, this means you need to
have two distinct versions of the winapi package installed
simultaneously, which RPM front-ends6did not support until recently,
and you need the ability to specify a permied version range (e.g. 0.3.0
≤ v \< 0.4.0), which RPM did not support until late 2017 (version 4.14 ≤
v \< ∞).
is leaves longer-support distributions no option for building Rust
code, which is becoming required for common staples of Linux
distributions (most notably Firefox, librsvg, and vape7). Well. ere
is an option, but we don't like it.3 (DEFUN GETSOURCES () (GETSOURCES)) RPM macros are very powerful,
incredibly dangerous, and an ex cellent example of write-only code
[2]. e %autosetup macro in Listing 1 is responsible for unpacking
and patching code. Its deni tion in Fedora 29 is reproduced in Listing
2.RPM macros can perform option parsing and introspection of sources and
patches dened in the spec le. ey can also run arbitrary Bash or Lua
code. All of this can be mixed together, and nothing is o-limits;
macros can write out entire scriptlet sections, preamble elds, and
even Harry Poer slash ction.What if we could abuse macros and kill o those thousands of unusable
packages? Our macros would need to:• Introspect a source le for all its Rust dependencies, and add
Source# lines to the preamble• Fake a Cargo registry containing all these dependencies • Build and
install the target binaryWe built these macros, which contain an unhealthy mixture of JSON
parsing, AWK, and Lua. Not only did we build them, we2132 is a lot for the rst Fedora release where Rust packages were
permied at all; the current count is over 500.3With apologies to Bill Gates, noted proponent of Linux.
4fd stands for Finger Donuts.
5hps://github.com/sharkdp/fd/blob/7f58e8f7064346e569563b657fe92f24830e6a/
Cargo.lock6Common RPM front-ends include Zypper, yum, and DNF (which stands
for Do Not Fuck).7hps://github.com/JoshuaRLi/vape
50
Listing 2: e %autosetup macro
%autosetup(a:b:cDn:TvNS:p:)\
%setup %{-a} %{-b} %{-c} %{-D} %{-n} %{-T} %{!-v:-q}\ %{-S:%global
[s]{.underline}cm %{-S∗}}\%{expand:% [s]{.underline}cm [s]{.underline}etup %{ [s]{.underline}cm}
%{!-v:-q}}\%{!-N:%autopatch %{-v} %{-p:-p%{-p∗}}}
distributed them in an actual Linux distribution, we built Firecracker
using them, and we made the code rebuildable by users via retriev ing
the source RPM and using rpmbuild --rebuild.For your safety (and because TEX is dicult), the macros8are only
partially reproduced in Listing 3. At your own risk, they are
available on GitHub9and in the Amazon Linux source RPMs.For a packager to download all the required source les, they must run
the spec le through a spec le parser (such asrpmspec -P), then use a
source download tool (such as spectool -g).3.1 Okay, So Not Everything's Perfect For some dependencies to build
correctly, packagers must include the necessary BuildRequires and
Patch# lines to allow them to build. In this system, these must be
duplicated across every package that shares the same dependency. is
can be resolved by arbitrarily limiting the number of packages that
use this solution, perhaps by utilizing the tried-and-true mechanism
of "laziness".4 FURTHER APPLICATIONS
e general approach described here can be used for any pro gramming
language with lock les describing their dependency enclosures and with
standard URLs to fetch source code, such as Node.js or what people
wish Go would be.We really shouldn't though.
5 FURTHER TANGENTIALLY RELATED RESEARCH TOPICS
Calculate the total bandwidth used to transfer the %changelog
section of the TEX Live spec le, duplicated in each of its nearly 6,000
binary RPMs [5], across Fedora and its derivative distributions.
Something something Nix Docker Flatpak AppImage snaps.ACKNOWLEDGMENTS
e author acknowledges Amazon for inexplicably employing her. anks to
Natasha Jarus, Samuel Karp, Euan Kemp, Tom Kirchner, and Colleen ine
for their reviews.REFERENCES
[1] Edward C. Bailey. 1997. Maximum RPM. Sams Publishing.
hp://p.rpm.org/ max-rpm/[2] Wikipedia contributors. 2019. Write-only language. Wikipedia
(2019). hps: //en.wikipedia.org/w/index.php?title=Write-only
[l]{.underline}anguage&oldid=880031540 [3] Tom 'spot' Callaway et
al. [n. d.]. Fedora Packaging Guidelines. hps://docs.
fedoraproject.org/en-US/packaging-guidelines/[4] Erik Troan, Marc Ewing, et al. 1995. RPM Package Manager.
hp://rpm.org [5] Will Woods. 2018. Unpacking RPM: package names.
hps://weldr.io/ Unpacking-RPM-names/8Object Class: Euclid
9hps://github.com/awslabs/rust-bundled-packaging/tree/
b9c50d16b6d517c4e7483c6842b6f3cc77969b9d
https://github.com/amazonlinux/rust-bundled-packaging/tree/b9c50d16b6d517c4e7483c6842b6f3cc77969b9d
{width="0.5204101049868767in"
height="0.7499518810148731in"}Listing 3: RPM macros for bundling Rust dependencies
# SPDX-License-Identier: MIT
# Copyright © 2017 Igor Gnatenko
# Copyright 2018 Amazon.com, Inc. or its aliates.
\% [c]{.underline}argo %{ [b]{.underline}indir}/cargo
\% [c]{.underline}argo [c]{.underline}ommon [o]{.underline}pts %{?
[s]{.underline}mp [m]{.underline}ags}\% [c]{.underline}argometadir %{ [d]{.underline}atadir}/cargo-metadata
%cargo [p]{.underline}rep (\
set -eu \
%{ [m]{.underline}kdir} -p .registry \
REGISTRY="$(realpath .registry)" \
%{ [m]{.underline}kdir} -p .cargo \
cat > .cargo/cong \<\< EOF \
[build]\
rustc = "%{ [r]{.underline}ustc}"\
rustdoc = "%{ [r]{.underline}ustdoc}"\
rustags = %{ [g]{.underline}lobal [r]{.underline}ustags
[t]{.underline}oml}\\
[term]\
verbose = true\
\
[source]\
\
[source.local-registry]\
directory = "$REGISTRY"\
\
[source.crates-io]\
registry = "hps://crates.io"\
replace-with = "local-registry"\
EOF\
do [c]{.underline}argo [b]{.underline}uild [r]{.underline}egistry() {
\\% [c]{.underline}argo [b]{.underline}uild [r]{.underline}egistry \
} \
do [c]{.underline}argo [b]{.underline}uild [r]{.underline}egistry
$REGISTRY \)
%cargo [b]{.underline}uild %{ [c]{.underline}argo} build %{
[c]{.underline}argo [c]{.underline}ommon [o]{.underline}pts}
--release %{?cargo [a]{.underline}rgs}%cargo [t]{.underline}est %{ [c]{.underline}argo} test %{
[c]{.underline}argo [c]{.underline}ommon [o]{.underline}pts}
--release --no-fail-fast %{?cargo [a]{.underline}rgs}%cargo [i]{.underline}nstall \
%{ [c]{.underline}argo} install %{ [c]{.underline}argo
[c]{.underline}ommon [o]{.underline}pts} --path . --root
%{buildroot}%{ [p]{.underline}rex} %{?cargo [a]{.underline}rgs} \%{ [r]{.underline}m} %{buildroot}%{ [p]{.underline}rex}/.crates.toml
\%{ [m]{.underline}kdir [p]{.underline}} %{buildroot}%{
[c]{.underline}argometadir} \%{ [c]{.underline}argo} metadata --format-version 1 %{?cargo
[a]{.underline}rgs} > %{buildroot}%{
[c]{.underline}argometadir}/%{name}.json\% [c]{.underline}argo [c]{.underline}rate [s]{.underline}ource
[u]{.underline}rl()
hps://crates.io/api/v1/crates/%1/%2/download#/%1-%2.crate
\% [c]{.underline}argo [c]{.underline}rate [s]{.underline}ource
[u]{.underline}rls grep 'ˆ"checksum' | awk '{ print "Source" NR+9999 ":
%%{ [c]{.underline}argo [c]{.underline}rate [s]{.underline}ource
[u]{.underline}rl " $2 " " $3 "}" } END { print "%%global
[c]{.underline}argo rst [c]{.underline}rate 10
\% [c]{.underline}argo [b]{.underline}uild [r]{.underline}egistry
%{lua:for i = rpm.expand("% [c]{.underline}argo rst
[c]{.underline}rate"),rpm.expand("% [c]{.underline}argo
[l]{.underline}ast [c]{.underline}rate") do \uncompress = rpm.expand("%{uncompress:%{S:" .. i .. "}}") \
print(uncompress .. " | tar -x -C $1\\n") \
template = '{"les":{},"package":"%s"}' \
print("printf '" .. template .. "' $(sha256sum " .. rpm.expand("%{S:"
.. i .. "}") .. " | awk '{ print $1 }') > $1/$(" .. uncompress ..
" | tar -t | head -n 1 | cut -d / -f 1)/.cargo-cheend}%cargo [b]{.underline}undle [c]{.underline}rates(n:t:l:) \
%{-t:%{-l:%{error:cargo [b]{.underline}undle [c]{.underline}rates:
Can't specify both -t and -l}}} \ 51%{!-t:%{!-l:%{error:cargo [b]{.underline}undle [c]{.underline}rates:
Must specify one of -t or -l}}} \%{-t:%{expand:%(%{uncompress:%{S:%{-t∗}}} | tar -xO
%{-n:%{-n∗}}%{!-n:%{name}-%{version}}/Cargo.lock | %
[c]{.underline}argo [c]{.underline}rate [s]{.underline}ource
[u]{.underline}rls)}} \52
Security and privacy
9 CVE-2018-90017117
t0m7
Keywords: kingme, exploit, input validation 10 Orchhit: User-oblivious
social networking Jim McCannKeywords: privacy, hashing, cryptography
53
{width="2.084319772528434in"
height="0.9865748031496063in"}CVE-2018-90017117
9 Also known as: #KingMe attack Common Vulnerabilities and Exposures
Published 2018-12-03
Partial embargo until 2019-04-01
Description
Reported by t0m7 of East Coast Hacking 0rganization
An input validation error in the move parser allows remote privilege
escalation.Background
The popular internet chess site lichess.org allows for the import of
PGN files, a standard text-based inter change format for giving the
sequence of moves in a game. Moves look like ìe4î (move a pawn to the
e4 square) or ìQxd3î (queen captures on d3) or ìRcc8î (the rook on the
C file moves to c8). When a pawn moves into the last or first rank, it
usually promotes to queen, but may legally promote to a bishop,
knight, or rook at the playerís option. This preference is specified
using the notation g8=B (or N for knight, R for rook, or Q for queen
to optionally be explicit). lichess.org does
{width="2.9602220034995628in"
height="3.0153477690288715in"}not properly implement this syntax, and allows a move like
g8=K, which is not legal chess.
Impact
The pawn is promoted to a king. This is a privilege escalation
vulnerability, because the king has privileges that the pawn
does not have, such as the privilege to be checkmated.
Scope
The issue is only confirmed during PGN import (e.g. in ìanaly
sis boardî). In live games, it is possible to use keyboard entry
of moves in PGN notation, but =K is ignored. It is possible that
these moves are only rejected in the frontend and would be allowed by
the underlying chess engine (if made directly through the API, for
example). After a second king is intro duced, the game appears to be
quite broken; some parts of the
Screenshot. After 5. ... gxh1=K ?!, black promotes their g pawn to
a second king.
interface behave as though the game is a draw and no further moves are
allowed, but the computer contin ues to suggest lines in the
background. When evaluating this vulnerability in other systems, note
that the king has not yet moved, and so could erroneously be
considered eligible to castle (e.g. with the h8 rook), a potential
0-0-day.Example exploit
1. f4 e5 2. Nf3 exf4 3. g4 fxg3 4. Ng1 g2 5. Nf3 gxh1=K
Classification - Office Use Only
CVSS v3.0 Severity and Metrics:
Base Score: 7.7 HIGH
Vector: AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:H/A:N (V3 legend)
Impact Score: 7.9
Exploitability Score: 8.9
54
Their system is live at: http://orchhit.com
{width="0.5204101049868767in"
height="0.7499518810148731in"}
10
Orchhit: User-Oblivious Social Networking
JIM MCCANN∗, TCHOW llc
Fig. 1. Our user-oblivious social network, Orchhit, allows sharing of
orchestral-hit-sound status updates in a user-oblivious way, thanks to
a preimage-writable table construction.In this paper, we describe the unique infrastructure used by our new
user oblivious social network, Orchhit (Figure 1). This infrastructure
uses a constant-sized storage to support basic status sharing for an
unlimited num ber of users; allows instant client-side account
creation and deletion; and is immune to server-side snooping. Since we
are magnanimous co-founders, we reveal our infrastructural secrets in
this tell-all publication.CCS Concepts: • Security and privacy → Privacy protections; Hash func
tions and message authentication codes; • Networks → Social.Additional Key Words and Phrases: privacy, failed social networks,
overly casual writing, isn't it unfortunate that cryptozoology has
nothing to do with cryptosystems?1 INTRODUCTION
Modern social network web page (site) companies face three ma jor
problems: acquiring new users, providing server resources to support
existing users, and repressing their own inescapable desire to sell
users' private information. We present a novel social net work
architecture -- user-oblivious social networking -- that uses
cryptographic primitives to mitigate all three of these problems.
Particularly, our user-oblivious social network backend provides a
status sharing platform and the following guarantees:1 Instant client-side account creation and deletion without server
contact (thus, no way for operators to determine the number of
accounts).2 Friends lists are never stored on the server in a way that can
be read by operators (thus, no way for operators to determine the
social network of accounts).3 Uses a constant amount of server storage.
4 Provides no way to distinguish status updates from random (or
user account) data, unless status updates are improperly designed.
55
2 BACKGROUND
Learning from the mistakes of others would only slow us down.
3 METHOD
Our user-oblivious social network construction is built on a cryp
tographic hash function H(X) : Z∗2 → Z2B2 which maps arbitrary
length bit-strings to xed-length bit strings of length 2B in a way
that is hard to invert and does not induce any correlations between
output bits (along with some other important properties that we can't
be bothered to look up right now).3.1 Server
The social network server is responsible for persistent storage of a
2B-entry table of B-bit storage locations, T . This table is
initialized with random bits.The server provides two interfaces, read and write, to the client to
manipulate the table. Read allows a client to retrieve the table value
at a given B-bit address:read(A : ZB2) :
return T [A](1)
Write allows a client to set the table value at any address for which
it knows a B-bit hash preimage:
write(P : ZB2,V : ZB2) :
T [lo(H(P))] ← V(2)
Where lo(B) : Z2B
2 → ZB2is the function that returns the low B bits of a 2B-bit
value.These two primitives -- read and write -- are the only things that the
server implements in Orchhit -- the remainder of the social network
relies on client operations exclusively.
2 • McCann and Saghy 3.2 Client
Their system is live at: http://orchhit.com
{width="0.5204101049868767in"
height="0.7499518810148731in"}
Fig. 2. The status format in Orchhit is a MIDI note-on message whitened
by a nonce. 4 PROPERTIES
Notice that the server operations described above allow secure
publish-subscribe interaction between clients -- one client can pick a
value P to write status updates to and publish value lo(H(P)) to enable
other clients to read these updates. This interaction forms the basis of
our platform's social networking operations.
Login / account creation. To start using our social network, a client
picks a passphrase, P; computes a secret key, K ≡ H(P), by hashing the
passphrase; and derives a follow key, F ≡ lo(H(lo(K))), by hashing the
low bits of the secret key.
Notice that this process does not require any server communica tion or
storage. Note, also, that the high bits of the secret key will never
be sent to the server.Account deletion. Account deletion can be performed by forget ting the
passphrase.Status updates. To publish a status update, the client writes the
update using its secret key:publish(U ) :
write(lo(K),U )(3)
Friends list. To store or retrieve the ith element of its friends list,
the client uses addresses, Pi, derived from its secret key, obscuring
the contents with a value, Xi, derived from the extra-secret upper
bits of its secret key:
Xi ≡ lo(H(hi(K) + i))
Pi ≡ lo(H(lo(K) + i))
getFriendAddress(i) : (4)
return read(lo(H(Pi))) · Xi
setFriendAddress(i,A) : (5)
write(Pi,A · Xi)
Notice that no provision is made for variable-length friends lists. In
our implementation, every user has exactly four friends.
56
The above construction is simple but provides some very useful
properties which make it hard to deduce anything about the social
network by inspecting a snapshot of its storage.User Account Obliviousness. Since all of a user's account data (their
friends list) is xored with a passphrase-dependent stream, it is
impossible to distinguish user accounts from empty (initialized
to-random) storage.Constant Storage. Rather than consuming ever-increasing amounts of
storage, the server's table remains xed-size for the life of the net
work. As the number of users grows, the user experience will grace
fully degrade as friends list entries and statuses get over-writtenby hash collisions. As the designers of the internet understand, this
sort of "gentle failure" is much preferable to a hard failure, and may
even lead to self-regulation, as users will quit using the (apparently
aky) system.Status Update Obliviousness. As long as status updates are IID1, and
ll the entire encoding space, status updates stored in the table are
also indistinguishable from random bits.At present, this is an implementation detail that the client needs to
manage2.5 IMPLEMENTATION
Our user-oblivious social network, Orchhit, is live at http://orchhit.
com. It provides users the ability to push orchestral hit sounds to
their followers and to follow up to four friends. Status messages are,
therefore, MIDI note-on messages, which are whitened using a nonce and
a hash value in a way that is somewhat awed, Figure 2, though
red-teaming this is left as an exercise to the reader .For our implementation, we chose B = 24 as a reasonable com promise
between usability and security3. As a hash function our
implementation uses SHA-1 (truncated to 48 bits) because imple
mentations are readily available and because we clearly lack cryp
tographic acumen.As a bandwidth saving measure, the read call implemented by our server
provides the option to defer return until the value is di erent from a
provided value. This technique, termed long polling,1"Locally owned and responsibly sourced."
2We certainly didn't get this wrong in our client.
3Is 224a su ciently large number? Of course it is! It's higher
than most people can count even if they use binary and all their ngers
and toes.avoids some bandwidth costs and probably doesn't open the system to
any weird timing attacks.6 FUTURE WORK
The astute among you may have realized by now that selecting a secure
value for B may be impossible, especially as compute e - ciency seems to
be growing much faster than storage e ciency. One solution might be to
use a pearl-diver construction to provide proof-of-work along with read
requests4.
For some social network designs, allowing only four friends may seem
limiting. However, this limit can easily be overcome by realiz ing
that your de nition of "friend" is not su ciently narrow (or by
keeping multiple accounts open).Unfortunately, our system is vulnerable to several side-channel
information disclosure attacks. Anyone able to observe the network tra
c to and from the server -- e.g. the social network operator
themselves -- can estimate the type of individual storage locations by
observing the read and write behavior over time. This information may
be used to determine the number of users and -- potentially -- the
contents of their status updates. In our present network, this
57
Their system is live at: http://orchhit.com
{width="0.5204101049868767in"
height="0.7499518810148731in"}
Orchhit: User-Oblivious Social Networking • 3
hazard is largely mitigated by the fact that status updates are just
orchestral hit sounds so, like, chill out folks.7 CONCLUSION
In this paper, we described a construction for a user-oblivious social
network based on a preimage-writable table5.Readers are encouraged to try our social network at http://orchhit.
com. Philosophically speaking, you either already have, or can never
truly have, an account.We hope that our work points the way forward for a bold new set of web
services that use cryptographic primitives to make scaling easy and
monetization nearly impossible.ACKNOWLEDGEMENTS
Thanks to Brian Saghy for extensive conceptual development assis
tance, domain administration, and being too humble a co-founder to
want authorial credit.4This may enable blockchain-backed automated ful llment services to
support big data-centric AI- rst omnichannel retailtainment; enhanced,
of course, by a sustainable and authentic brand story. Yes, just put
the venture capital money over there. 5Which we have actively
avoided looking up prior work on, preferring to treasure the illusion
of novelty.58
Machine learning
11 Color- and piece-blind chess
Dr. Tom Murphy VII Ph.D.
Keywords: chess, handicaps, man-in-the-middle attacks, neural networks
12 Dimensionality-reducing encoding for classification of Pythagorean
engendered numbersRany Tith and Oscar I. Hernandez
Keywords: number theory, machine learning, encoding, informa tion
theory, classification, gender theory, integers, globalization, computation, mathematics
13 emojizip: A text compression system based on pictogram kiloword
equivalenceWilliam Gunther and Brian Kell
Keywords: data compression, TensorFlow, laughing crying emoji
14 Meta-meta-learning for neural architecture search through arXiv
DescentAntreas Antoniou et al.
Keywords: meta, meta-meta, deep, NAS
15 Towards automatic low hanging fruit identification for the steering
of ML researchNick Frosst and Aidan Gomez
Keywords: machine learning, detection, segmentation, orientation,
apple, akee, apricot, avocado, banana, bilberry, black
berry, blackcurrant, black sapote, blueberry, boysenberry,
Buddha's hand (fingered citron), crab apples, currant,
cherry, cherimoya (custard apple), chico fruit, cloudberry,
coconut, cranberry, cucumber, damson, date, dragonfruit
(or pitaya), durian, elderberry, feijoa, fig, goji berry, goose
berry, grape, raisin, grapefruit, guava, honeyberry, huck
leberry, jabuticaba, jackfruit, jambul, japanese plum, jostaberry,
jujube, juniper berry, kiwano (horned melon), kiwifruit,
kumquat, lemon, lime, loquat, longan, lychee, mango,
mangosteen, marionberry, melon, cantaloupe, honeydew,
watermelon, miracle fruit, mulberry, nectarine, nance, olive,
orange, blood orange, clementine, mandarine, tangerine,
papaya
59
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
{width="0.5204101049868767in"
height="0.7499518810148731in"}
COLOR- AND PIECE-BLIND CHESS
11
DR. TOM MURPHY VII PH.D.
1. Impressing humans
What better way for humans to impress each other with their brains,
especially in movies, than to play chess---and to shout dramatically
CHECKMATE! upon surprise-checkmating their opponent? Well, one way is to
play chess while disadvan taged somehow, for example, by punching each
other in the face repeatedly during the game to impair brain function
(see Chess Boxing [8]). Another common distraction is to play a
multitude of games against many opponents at the same time, in a
so-called "simultaneous exhibition." The idea is that this is more
challenging because of the need to maintain mental state for so many
games at once, whereas your opponents only need to maintain state for
one game. In truth, simultaneous exhibitions easily fall to a
"man-in-the-middle attack." If the purported genius simply creates a
perfect bipartite matching of the games played with the white pieces and
the games played with black, he can mechanically forward moves between
these pairs of boards. This requires only constant state (see next
section) per pair of games, and guarantees an even score for the
exhibition. So that's not very impressive.
Another disadvantage that humans sometimes use to im press each other is
a blindfold (worn over the eyes). In this predicament they only hear the
opponent announce moves and must imagine the position on the board in
their mind's eye, both for the sake of remembering it and while
exploring po tential moves. Disadvantages can be combined, such as in
the final scene of the 1988 documentary Bloodsport where Jean Claude van
Damme is blinded by an illicit foreign substance during the final
martial art battle.1
2. Impressing computers
In contrast, it is much more difficult to impress computers or impress
people with computers. When it comes to computers playing chess,
largely, the jig is up; it is now easy for chess pro grams, running on
consumer hardware, to defeat the strongest human players. It is well
known that striking a computer actu ally fixes it, so Chess Boxing
becomes trivial. Blindfold chess is the natural interface for a chess
computer; it is actually much more difficult to have the computer
interpret the opponent's move by visually studying a physical board!
Playing multiple games simutaneously is an easy extension of playing a
single game, although in principle the scale ofDate: 1 April 2019.
Copyright c 2019 the Regents of the Wikiplia Foundation. Appears in The
Journal Of LaTeX Class Files with the insufficient material of the
Association for Computational Heresy; IEEEEEE! press, Verlag-Verlag
volume no. 0x40-2A. 1 tempo.
1JCVD does not play chess on camera, but it is implied that he is also
holding a simultaneous exhibition between rounds in a different room of
the underground Hong Kong illegal karate complex.
such a thing could still be impressive. This is also impres sive to
other computers, who are largely concerned with filling up their
memories with efficiently coded data. With a mod ern chess engine, it
is easy to scale to an arbitrary number of games, since the exhibitor
can make progress by observing one of the boards, computing a strong
move, and playing it; this re quires O(1) space because all of the
state is stored externally in the exhibition itself. However, we run
the risk of losing the tournament (other players may be yet stronger
comput ers). The man-in-the-middle attack remains an efficient way to
minimize loss (ensuring an exactly even score). The sim plest way to
do this is to explicily generate a perfect bipartite matching over the
n games G being played. This consists of n/2 pairs hGw, Gbi (where
we play as white against Bob and black against Walice, respectively).
Since each game starts in the starting position, this is very easy; we
can just assign the matches consecutively. Along with each pair we
also record which of the following states we are in:1 We are waiting for a move from Walice (our white opponent)
2 We have seen a move from Walice, which is . (3) We are waiting
for a move from Bob (our black oppo nent)
4 We have seen a move from Bob, which is .
If in State 1, we just watch Gb until Walice makes a move, then
record it and proceed to State 2. We consume the move and move to
State 3 by playing that move in Gw against Bob (where it must be our
turn). We can immediately seek out that game or wait until we
naturally come upon it. However, we should only approach Gw when the
pair of games is in State 3, etc., otherwise we will not have a move
to play.There are n/2 pairs, with two bits for the state, no more2 than
log2(64 × 64 × 4) = 14 bits for each move (source square,
destination square, and 2 bits to distinguish promotion to queen,
rook, bishop, or knight). However, we also need to store the matching
of Gw to Gb; this can be done with a pair of indices (or e.g.
memory addresses) but unfortunately, this requires
log2(n) bits to represent. So overall this approach re
quires O(n log(n)) space to play a simultaneous exhibition of n games.It appears to be possible to reduce the space usage per game to a
constant. In order to perform a man-in-the-middle attack, we need a
perfect matching between the white games and black games. It is not
essential that the matching be stable over time; for example if we are
forwarding moves between Walice and Bob, and between Waluigi and
Bario, and these games happen to transpose to the same position, then
it works just fine to switch to forwarding between Walice and Bario;
Waluigi and Bob. So, rather than store the matching explicitly, we can
reconstruct it from the stored state at each step.Let's think about the process of forwarding the moves from our white
opponents to our black opponents; the reverse is of course symmetric.
The first step will be to wait for the2There are only 1792 pairs of squares between which pieces can ever
move (Section 5.3.1), so 11 + 2 bits suffices, with some added
complexity.60
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
white opponents to make their moves, and then copy these n/2 positions
(not moves) into a vector in memory. The black opponents are waiting for
a move from us. Next, we'll copy their n/2 positions into memory,
aligned with the n/2 positions already present. Let's say that the
relation that defines a legal move in chess is
Bm→ B0
where B is the position before the move m, and B0is the resulting
position. Our goal is to align the games such that B0 (a position
copied from our white opponent) is aligned with B (a position pending a
move for our black opponent) in memory; this will represent the perfect
matching. Computing m from B and B0 when Bm→ B0is easy (and
unique), so this allows us to read off and play the move for each row.
By invariant, it will be possible to produce such an align ment. For
example, the first time we do this, each B will be the starting
position, and B0 will be a legal move made by white from the starting
position. Any alignment will work. Let's say that just one of the white
opponents played 1. d4, resulting in B0; then one black opponent will
make a legal response to this (say 1. . . . Nf6, giving B1). Then B1
can be B0for the next round, which we can align with B = B0, and so
on.
The only tricky thing is figuring out which boards go with which.
Although if Bm→ B0it is easy to deduce m, it is not possible to
compute B from B0, or even from B0 and m. This is because we may
have both Bam→a B0 and Bbm→b B0 with Ba 6= Bb. For
example with B0
+-----------------------------------------------------------------------+
| > kZ0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z |
| > J0Z0Z0Z0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8
7
6
5
4
3
2
1
a b c d e f g h
. . . we could have Ba and Bb be
Fortunately, we know that there exists a perfect matching (assuming
all players are playing legal moves) and we can tell if we found one
(i.e., we didn't get stuck). So, one strat egy that works is to choose
randomly when there is some ambiguity, and start over from the
beginning if we ever get stuck. In practice this will be pretty
efficient, since convergent board states are unusual. We only need a
single pseudoran dom pool for the entire process, so it can be O(n)
bits; this seems easily enough to generate all possible permutations
of n/2 items. Even 22n grows much faster than n!. If we don't like
the random approach, I believe it is also possible to compute
next_permutation in constant space; so we can just explicitly try all
orderings for B0(this takes exponential time).
{width="0.5204101049868767in"
height="0.7499518810148731in"}Once we have paired up each B and B0, we simply compute the move
(which we now know exists) and play it in that game. We then wait for
the black opponents to play their moves, copy the resulting board
states into our vector and repeat the above process (but flipping
"black" and "white").Although this is more involved than the previous approach, and may
take exponential time, it allows us to play against n simultaneous
opponents using O(n) space!2.1. Board representations. The actual space used per game is
primarily the representation of a chess position, plus a few bits for
bookkeeping. So, representing boards compactly gives us a way to
increase the number of simultaneous games we can play for a given
storage size.Mainly, we need to store the pieces and their locations. There are a
few other bits, like whose turn it is (1 bit), whether each player can
still castle king- and queen-side (4 bits), and whether and where an
en passant capture is possible (4 bits).3With 64 squares, six pieces for each of the two sides, plus the empty
square, a straightforward representation of the board uses 64 × 4 =
256 bits. The Thursd'z Institute considered more compact
representations [2]; one nice choice works as follows:Start with a single 64-bit mask which indicates, for each square on
the board, whether it contains any piece. Note that there can only be
up to 32 pieces on the board. To tell what
+-----------------------------------------------------------------------+
| > Nj0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z |
| > J0Z0Z0Z0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8
8
7
7
6
6
5
5
4
4
3
3
2
2
+-----------------------------------------------------------------------+
| > Rj0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z |
| > J0Z0Z0Z0 |
+=======================================================================+
+-----------------------------------------------------------------------+
these pieces are, we then follow with 32 four-bit records; these
indicate the piece's color and type.5 With the 9 bits of extra
3Technically, we need to store a lot of additional information with
the board in order to completely implement the rules of chess.[1] The
trickiest of these involve the rules for draw by repetition, which make
reference to
1 a b c d e f g h
1 a b c d e f g h
the history of the game (See Footnote 1 in Survival in chessland [6])
and seem to require storing all previous board states. Fortunately, if
we are
Both of which can precede B0(the move is even the same: Kxa1). So it
is not enough to greedily assign edges in our perfect match; if we
choose the edge Bb to go with B0, we might later find B02:
being this picky, then we also know that the length of a chess game is
bounded by a constant: Rule 9.6.2 ends the game in a draw if both
players have made 75 moves without a pawn move or capture,4so it
suffices to store the 75×2 most recent (half-)moves. This sucks so
most people don't do it (for example, FEN notation only gives the
number of such moves, and so cannot implement the draw by repetition).
On the other hand,
+-----------------------------------------------------------------------+
| > RZ0Z0Z0Z ZkZ0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z Z0Z0Z0Z0 0Z0Z0Z0Z |
| > J0Z0Z0Z0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8
7
6
5
4
3
2
if we insist, then this may give us a simpler route to a constant-space
exhibition, since the Bm→ B0relation is probably reversible with
such information.
4These are two types of moves that make it impossible to formally
repeat a position that preceded them. Castling also has this property,
but doesn't count because it is a "secret move."
5Since only 32 of the 64 bits can be set, you could do slightly better
by
1 a b c d e f g h
representing 64 32
in ∼ 61 bits. When fewer than 32 squares are occupied,
. . . and have no possible matching board, since it cannot legally
follow Ba.
we can use a record containing e.g. a third king (otherwise
impossible) to indicate that we should ignore the remaining bits.
However, this gets vastly more complicated for only 3 bits of savings.
61
state above, this totals 64 + 32 × 4 + 9 = 201 bits. There
pieces are positioned on the board, but not what type or color
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
is some slack in the representation, because there are only 12 actual
possibilities for a piece but we can indicate 16 with 4 bits. It is
great to abuse this slack to save bits; for example, we can store a new
type of rook that is still able to castle (it can only be in the corners
and thus also indicates its own color), eliminating the 4 castling bits.
We can similarly introduce an en-passantable pawn, saving the 4 bits of
en passant state; this piece can only be in ranks 4 or 5, so it also
indicates its color. We can also have a "king whose turn it is" for each
side, saving the side-to-move bit. This totals a nice round 64 + 32×4 =
192 bits.6 This would allow approximately an 11 billion-game
simultaneous exhibition in RAM on my desktop computer.
So now comes the main idea of the paper, which is also spoilered in
the very clear paper title. What if we represented boards only as the
64-bit mask telling us what squares are occupied? The encoding is very
lossy, of course, but it often contains enough information to deduce
the state of the board. For example, can you tell what position this
is?
+-----------------------------------------------------------------------+
| > |
| 0Z0Z0Z0ZZ0Z0Z0Z00Z0Z0Z0ZZ0Z0Z0Z00Z0Z0Z0ZZ0Z0Z0Z00Z0Z0Z0ZZ0Z0Z0Z0 |
+=======================================================================+
+-----------------------------------------------------------------------+
8
7
6
5
4
3
2
1
a b c d e f g h
Correct! It is
after 1. Nf3 Nf6 2. e4
+-----------------------------------------------------------------------+
| > |
| nsblkarmopopopop0Z0Z0Z0ZZ0Z0Z0Z00Z0ZPZ0ZZ0Z0Z0Z0POPO0OPOMRABMRLK |
+=======================================================================+
+-----------------------------------------------------------------------+
they are. Of course, we also have to prohibit the computer from simply
remembering the board, so the algorithm must be stateless.
Specifically, we want a function
{width="0.5204101049868767in"
height="0.7499518810148731in"}
makemove : uint64 → move list
that makes a move from a single board position, represented just as 64
bits. This is a single move; the move list represents our preference
for the move to make in descending order, and we commit to the first
move that is actually legal. It does not work well to insist that the
function return a single move, as it will often be the case that the
board is misinterpreted and a move is in fact illegal; forcing
forfeit7 would mean that almost all games end in forfeit, which is
boring. On the other hand, allowing the function to try again upon
learning a move is illegal would allow it to interactively
"interrogate" the board state somewhat.8 This seems counter to the
spirit of color- and piece-blind chess, so we instead require the
function to rank all moves ahead of time.
4. Unblinding the board
I went about this by building a function that "unblinds" a board; it
has type
unblind : uint64 → position
This function is natural for machine learning. It is easy to generate
copious training data from actual games by sim ply blinding positions
into their corresponding 64-bit num bers; I just randomly sampled 100
million positions from Febu rary 2017 on lichess.org.I repurposed the custom neural network code from my semi nal paper Red
i removal with artificial retinal networks [3] after discovering
that artificial retinal networks are actually isomor phic to neural
networks. The main advantage of this code is that it allows for sparse
networks, but the real reason to use it is that I would rather spend
dozens of hours debugging my
8 7 6 5 4 3 2 1 a b c d e f g h
Ng4 3. Bc4 Ne5 4. O O Ng6 5. Kh1 Rg8 6. Nc3 Nh8 7. Qe2 Nc6 8. Rb1 Rb8 9.
Nb5 Nb4 10. Rd1 Nd5 11. Qf1 Nb6 12. Qg1 Na8 13. Nbd4 Nb6 14. Rf1 Na8 15.
Be2 Ng6 16. Bd1 Nh8 17. Nb3 Ng6 18. Ne1 Nh8 19. Na1
own code, pay a larger electric bill, and get worse results in the end,
than to spend a short while trying to get someone else's
probably-very-good neural network training package to compile.
The structure of the network is as follows. The input layer is 64 nodes,
one for each of the 64 bits, with each node set to either 1.0f or 0.0f.
Three hidden layers of size 1024, 12288, and 567 do the neural magic.
The output layer is 837 nodes; the bulk of which is a "one-hot"
representation of the predic tions for the 64 squares, each with 13
possible contents (black or white, six pieces, or empty). This is 64 ×
13 = 832 nodes.
3. Color- and piece-blind chess
So this is kind of like blindfold chess, but for computers! Instead of
being blind to the board, and only relying on our memory (trivial for
computers), we'll only be able to see where
6Since this is SIGBOVIK, I am freed from the burden of comparing
related work. I did however read the rather bad Wikipedia article on the
topic [7] which describes a Huffman-based encoding that uses a "maxi
mum of 204 bits, and often much less." This also includes a 7-bit
50-move counter (but you really need to implement a 75-move counter; 50
moves only allow a player to claim a draw) so should be compared as 197
bits. But the article also contains many bugs, like the misconception
that there can only be four total rooks (pawns are allowed to promote to
rook). So the approach described here is both more efficient and more
correct.
Then four nodes to predict the four castling bits, and one to predict
the current side to move. This model does not predict the possibility
for en passant capture, nor move counters or position repetition. This
will not be its main source of disad vantage!I trained the network in two phases, first starting with a densely
connected one (model size 160 MB), and then after I get fed up with
how slow training was, a "vacuumed" version of the network where I
removed edges with low absolute weights7FIDE rules state that the second attempt at an illegal move results
in forfeit (7.5.5).8Similar to Kriegspiel [9], although in that game at least one's
own pieces are known!62
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
(model size 5 MB) to continue training. Removing edges based on an
absolute weight threshold is very unprincipled (since a downstream edge
can magnify a contribution arbitrarily) but I did it anyway.
Everything was trained on a single GPU, though a fairly de cent one in
2018, the EVGA GeForce GTX 1080 "FTW" (re ally), using OpenCL. Biases
were initialized to 0 and weightsis predicted as a pawn and the queen "disappears" to the un blinder
(Figure 1). Having an invisible queen in your camp is of course very
dangerous. Resolving ambiguities in favor of more likely positions is
the right thing for the model to do, so this is just an inherent flaw
with the decomposition of the problem. There are some ways we can
account for this (Section 5.2).
{width="0.5204101049868767in"
height="0.7499518810148731in"}
with a Gaussian of mean 0 and standard deviation 0.025. In
8
the first phase, there were 64 examples per round, and af
7
ter vacuuming, 2048. The round learning rate αr started at
6
0.1 and descended linearly to 0.002 over 500,000 rounds; and
5
the learning rate when updating weights (for each example) α
4
3
is αr/examples_per_round. In no way am I recommending
2
these parameters. Fiddling with the parameters to make it do
+-----------------------------------------------------------------------+
| > rmblkans opo0ZpLp 0Z0Z0Z0Z Z0Zpo0Z0 0Z0ZPZ0Z Z0Z0Z0Z0 POPO0OPO |
| > SNA0JBMR |
+=======================================================================+
+-----------------------------------------------------------------------+
its black magic or alternately carom off to a sea of NaNs or zeroes is
for sure the worst part of neural networks. Indeed, I initially started
with the classical sigmoid transfer function, but "upgraded" to the
"leaky rectified linear" function
(p \< 0) ? p × 0.01 : p
after getting fed up with sigmoid weights caroming off (see "vanishing
gradient problem" and/or "exploding gradient prob lem"). The final model
was trained over 339,885 rounds on 223 million examples. It did not
appear to show signs of improving
1 a b c d e f g h
{width="2.7994586614173227in"
height="1.315349956255468in"}
a
b
for several days before I terminated it.
4.1. Statistical evaluation. The unblinding component can be evaluated
on its own, by running it on examples sampled independently of the
training set. The model outputs a score for each possible contents of
each square; we simply discretize to the highest-scoring one (same too
for the predicted castling state and turn). Over 50,000 examples, these
were the results:
9,584 predicted boards were exactly correct (19.17%). There were a total
of 161,166 piece mistakes, which is an average of 3.22 per board. This
is wherever we predict a square's contents incorrectly. There were only
1630 castling status mistakes, an average of 0.03 per board (there can
be up to four mistakes per board). This is probably because when the
king and rook are in their starting squares, castling is almost always
still al lowed. In 19,014 boards, we mispredicted whose move it is
(38%). This appears to be the most difficult thing to predict, which is
not surprising.9
4.2. Subjective evaluation. The unblinder must make mis takes since the
64-bit representation is ambiguous. Subjec tively, the unblinder makes
reasonable mistakes. It is excellent at common openings, usually getting
these exactly correct. On the other hand, it is fairly bad at sparse
endgames, where it is difficult to tell a pawn from a rook from a king.
It is terrible at unlikely positions that can be confused for likely
ones. If you are playing against it and know how it works, it is easy to
trick it by doing something like capturing one of its starting-position
pawns with your queen; nobody does this in real games (be cause the
queen can be immediately recaptured), so the square
9Prior to "vacuuming", the 160 MB network actually performed slightly
better than the final 5 MB network, with 21.20% of boards ex actly
correct, and an average of 3.12 mistakes per board. This suggests that
the model may only be doing a limited amount of generalization, instead
mostly memorizing board positions. Representing the 223 million examples
seen exactly (using our best board representation described in Section
2.1) would take 42.8 GB, so at 5 MB at least the data is repre sented
compactly, if also rather lossily.
Figure 1. (a) Position after 1. e4 e5 2. Qg4
d5 3. Qxg7; note the white queen strangely
on g7. (b) The bitmask for this position and
the unblinder's prediction. The queen "dis
appears" after Qxg7, because unblinding pre
dicts it to be one of black's own pawns---far
more likely in that square.
A few things are distinctly disappointing about its perfor mance. Even
outside of "likely" positions, it usually predicts that pieces on
black's side of the board are black, and vice versa (Figure 2). This
makes sense, but suggests serious lim itation on using the prediction
to play chess. Less forgivably, it sometimes predicts more than one
king per side (or zero), which is always wrong. Actually, an early
version had this problem in spades, frequently predicting two or three
kings. Upon debugging, I had simply made the noob mistake of print ing
both King and Knight with the letter "K." Ha! It often predicts the
"wrong" number of bishops (etc.), or places them on the same color.
This is technically possible through pro motion, but usually a bad
guess, since promotion is relatively rare, and moreso promotion to a
piece other than a queen. An approach that might handle this better
(but may have dif ferent downsides) would be instead to predict the
"fates" of the 32 initial pieces [6]. The fate of a pawn includes
what if any piece it has promoted to, but this is not necessary for
the other pieces. This would require that the model only predict a
single location for each king, among other things. However, this would
require a much larger output layer (32 pieces can move to 64 squares,
plus promotion) and it is not always clear how to interpret its value
into a position (for example, if two pieces are predicted strongly to
be on the same square).
5. Playing blind
Once we have predicted a board state, we can play with it. The
simplest way to do this is to use a strong chess engine to63
It is easy to beat this chess engine, by tricking it as in
{width="0.5204101049868767in"
height="0.7499518810148731in"}
{width="3.3593755468066493in"
height="1.5826115485564305in"}
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
Figure 1, although this involves unnatural moves, so it may only apply
if you know how it works. Measuring how well it plays in an absolute
sense is a subject of some interest, so I wrote a separate paper about
that [5]. This algorithm, called blind_yolo, had an Elo World score
of 489 ± 2. It beats a purely random player with a score of 101 wins,
27 losses, and 389 draws. Making moves purely at random is one of the
few fair comparisons, since the random strategy also works with color-
and piece-blind chess.Figure 2. What the model predicts
(in single-king mode; Section 5.1) for
0xFFFFFFFFFFFFFFFF, the board with all bits
set. This is an impossible position, but it
gives some idea of the model's biases for each
square. Notably, most of the pieces on each
half of the board have a single color. This
makes sense, but also suggests substantial
limitation. When single-king mode is off, the
bottom right king is predicted as a white rook.
pick a move for the position. Here, I use Stockfish with a node budget
of 1 million nodes, which takes about 1 second of CPU time per move on
my computer. There are some complications:
• Frequently, the unblinded board will not match the true position,
and Stockfish will choose a move that is illegal. So, as discussed
before, we actually return a prioritized list of moves. For this first
experiment, we just return the move Stockfish recommends, followed by
all other moves ordered randomly.• Stockfish is a very strong engine, and in my opinion the code is
generally good, but it is very sensitive to bad FEN (the notation used
to give it a position to evaluate) strings. Given a bad string, like
one that says castling is possible when the king isn't in its home
square, often crashes the engine. So we need to make sure to actually
pass valid positions. I accomplish this by making the following
modifications to the predicted board:-- If a castling bit is set, but castling is not possible due to the
position of the king or rook, clear the bit.-- Set the side-to-move to be the correct actual value. This uses the
unblinded state, so is superficially cheating. But note that if we get
the side wrong, then Stockfish's move will always be illegal: Moves
are specified as a source and destination square,10 and so the
source square of Stockfish's move would always be a piece of the wrong
piece's color. So this is equivalent to (but twice as efficient as)
run ning stockfish twice, one for each side, and prior itizing the
predicted side's move first.This won't fix all positions, for example, if the white and black king
are adjacent to one another in mutual check. If an irreparable problem
is detected, then I just return a uniformly random move list.
10 Plus promotion piece. Castling is represented as a two-square move
of the king.
5.1. We three kings. When evaluating the first version I found that it
was predicting a disappointingly high number of illegal positions in
practice, which was causing us to fall back on making random moves,
which is mostly boring. The second version reduces the rate of illegal
positions due to too many or too few kings [4].The model predicts a score for each type of piece in each square, and
we do not have to necessarily interpret it by always taking the
highest-scoring piece. This version first finds the two squares with
the highest scores for the white king, and same for the black king. We
take two in case the same square is predicted for both. Then this
square gets one of the kings (whichever has higher score) and the
other king goes in the highest-scoring unclaimed square. The rest of
the squares get the highest-scoring prediction as before, but we never
predict kings for them.This change just affects the unblinding process, so we can directly
evaluate its accuracy. It gets 19.28% of positions ex actly correct
(slightly better), with an average of 3.26 piece mistakes per position
(slightly worse). This is expected; we exchange local mistakes (each
was trained independently to minimize its local error) for global
correctness (which is not taken into account at all during training).This version, called blind_kings, performs a small amount better than
blind_yolo (63 wins, 45 losses, 412 draws). It had an Elo World score
of 502 ± 3.5.2. Spy check. Say blind_kings is playing as black; it re mains easy
to fool it by moving black pieces into white's camp, since they are
usually then predicted to be white pieces. We can defend against this
somewhat. Since it is illegal to capture one's own piece, there is
little risk in trying; if it is indeed our own piece then the move
will be rejected, and if it is not our piece, then capturing is good
for two reasons: One, we capture a piece, and two, we avoid having
Stockfish make a move in this incorrectly predicted board. (Of course
there are many reasons why eagerly capturing a piece can be a bad
idea, but at this level of play, an edge in material is likely worth
it.)There is one subtlety here. Above we argued that it was safe to use
the actual side-to-move instead of the predicted one; but here it
would not be equivalent to do so. Instead, we first prioritize all
apparent spy-check moves where the predicted source piece matches the
predicted side-to-move, then we try the opposite. (Ties are broken by
preferring to capture with a lower-value predicted piece, and then
randomly.) Due to this, there is some additional chance that we end up
making an especially dumb move because we both mispredicted the
side-to-move and the identity of some pieces.This version, blind_spycheck, works significantly better than
blind_kings. It has an Elo World score of 547 ± 1,
64
https://sf.net/p/tom7misc/svn/HEAD/tree/trunk/chess/blind
somewhere between a 93.75--96.875% dilution of stockfish1m (the third
best non-engine player).
5.3. Future work. The predicted board often expresses un certainty about
some squares, which could be thought of as probabilities. A principled
improvement would be to try to find moves that are good in expectation,
that is, integrated over all possible boards in proportion to their
predicted prob ability. A good approximation might be had by sampling a
bunch of boards according to the predicted distribution, and then using
Stockfish to score the top k moves for each; we can then order moves by
their expected score. Unfortunately, it is not easy to efficiently get
Stockfish to generate scored moves for k 6= 1. Even with k = 1, this
approach would be slow, taking about a second for each (distinct)
sampled board. So I did not try it, at least not before submitting this
paper.
5.3.1. No, u r a lnetwork. I initially considered trying to solve this
whole problem with neural networks. The current best known engine in the
world (AlphaZero) at least uses a neural network. The biggest advantage
would be that it would nat urally be able to consider multiple moves
under uncertainty about the board state, as just discussed, without any
par ticular extra logic. My plan was to make multiple different
components that could be evaluated separately, starting with the
unblinder described, followed by a unit that predicts legal moves, and
then a unit that takes these two (and also the 64- bit blinded mask if
it likes) and scores each move. Predicting a legal move is also a
natural function for machine learning; a move can be given just as a
source and destination square.11 Many pairs of squares are always
impossible (e.g. no piece can ever move from A1 to B8); so there are
only 1792 poten tial moves to predict. However, training a reasonable
unblin der took longer than I expected, and the legal move predictor
never really worked that well (it has a harder job), so I just settled
for basing it off the single unblinder unit. Can you do better?
6. Conclusion
I would like to thank the little people (pawns) and the the author-
and content-blind anonymous referrees.References
[1] FIDE handbook -- E.I.01A. Laws of chess, 2017. www.fide.
com/component/handbook.[2] Jim McCann, David Renshaw, Ben Blum, William Lovas, and Tom
Murphy, VII. Chessboard representations, De cember 2018.[3] Tom Murphy, VII. Red i removal with artificial retina networks.
In A record of the proceedings of SIGBOVIK 2015, pages 27--32. ACH,
April 2015. sigbovik.org/2015.[4] Tom Murphy, VII. CVE-2018-90017117. In A Record of the
Proceedings of SIGBOVIK 2019. ACH, April 2019. [5] Tom Murphy, VII.
Elo World: A framework for benchmarking weak chess algorithms. In A Record of the Pro ceedings of
SIGBOVIK 2019. ACH, April 2019.
11There are also four choices for promotion when moving a pawn into
the last rank. It is always the case that if any promotion is legal, all
choices are legal, so this does not need to be encoded in this phase.
Also, at this level of play, always promoting to queen is a very safe
simplification.
[6] Tom Murphy, VII. Survival in chessland. In A Record of the
Proceedings of SIGBOVIK 2019. ACH, April 2019. [7] Wikipedia. Board
representation (chess). https://en.
{width="0.5204101049868767in"
height="0.7499518810148731in"}wikipedia.org/wiki/Board_representation_(chess). [8] Wikipedia.
Chess boxing. http://en.wikipedia.org/ wiki/Chess_boxing.[9] Wikipedia. Kriegspiel (chess). https://en.wikipedia.
org/wiki/Kriegspiel_(chess).
65
12
Dimensionality-Reducing Encoding for
Classification of Pythagorean Engendered Numbers
Dead Duck or Phoenix?
π, 2019
Rany Tith
Spark Tank
Riverside, CA, 92507
Abstract
Oscar I. Hernandez
ARKS
Riverside, CA, 92507
2. Preliminaries
We apply modern well-known machine learning classifiers to the problem
of determining whether a given positive integer is even or odd, a
problem dating as far back as 6th century Classical Greece before common
era and even further in Ancient Egypt. We prove that the classification
of engendered numbers is possible. This is done by utilizing a unique
dimensionality-reducing encoding that was implemented before the machine
learning models were trained. Overall, our models' results proved to be
successful in classification as indicated through AUC and ROC analysis.
1. Introduction
In this article, we'll discuss a partition of numbers discovered by
the Ionian Greek philosopher Pythagoras (c.570--c.495 BC), which he
discovered during his tenure in Egypt before founding a school of math
in Greece. "To him, the odd numbers were male, and the evens were
female"[PYT].
Following Pythagoras, we will restrict our attention from the usual
integers, Z = {..., −1, 0, 1, ...}, to only the positive integers,
Z+ = {1, 2, 3, ...} ⊂ Z. Although one can evaluate whether a small
number is even or odd, the general problem remains open.1 In the
following sections, we will formally define even and odd numbers, build
a classifier, evaluate its results in a case study, discuss potential
improvements, and conclude with relevant open problems.
1 The authors have attempted to communicate with him, but have been
informed that he is not an advocate or user of computers or electronic
mail.2.1 Even and Odd
Definion 1. [MNT] Let n ∈ Z+ be a positive integer. We say that n
is even iff2 ∃k ∈ Z such that 2 · k = n Similarly, n is odd iff ∃k ∈
Z such that (2 · k) + 1 = n.For example, 1 = 2 · 0 + 1, 3 = 2 · 1 + 1, 5 = 2 · 2 + 1, 9 = 2 · 4 +
1, 7 = 2 · 3 + 1 are odd and 2 = 2 · 1, 4 = 2·, 6 = 2 · 3, 8 = 2 · 4,
10 = 2 · 5 are even. We have manually classified the next 60 numbers.
In the next section, we will use that labeled data to train a
classifier to evaluate the even-ness/odd-ness of a given number.2.2 Receiver Operating Characteristics [ROC]
This section is pulled directly from the source cited. A receiver op
erating characteristics (ROC) graph is a technique for visualizing,
organizing, and selecting classifiers based on their performance.Definion 2. ROC graphs are two-dimensional graphs in which tp (true
positive) rate is plotted on the Y axis and f p (false positive) is
plotted on the X axis.They depict relative tradeoffs between benefits (tp) and costs (f p).
We'll see the tradeoffs in Section 4.3. Solution
We propose to use real data such as seen in Figure 5 to train ma chine
learning classifies using the Python library scikit-learn. In
particular, we will implement support vector machines (SVM),
multi-layer perceptrons (MLP), decision tree classifiers (DTC), as
shown in Figure 1.The code is freely available at the first author's GitHub repos itory.
[DRECPEN]. All the results achieved in section 4 were per formed on
a x86-64 Arch Linux Thinkpad running Python 3.7.2.3.1 Encoding
In particular, we pre-process the information by encoding the pos
itive integer in binary [AB]. We optimized this encoding and re
duced its size to a single bit by restricting our data to the
rightmost bit and disregarding the rest of the binary string, since
memory be comes a concern when dealing with large numbers. The authors
are not in agreement as to why this yields such accurate results, but
they are proud of its size and speed.2if and only if
66
Figure 1. Flow diagram of classification process
Figure 3. MLP ROC analysis
where w denotes the weight, x is the input variable, y is the dependent
variable and λ indicates the margin strength for classifi cation.
4.1.2 Evaluation
In our evaluation as seen in Figure 2 ROC analysis indicates a strong
informative model. This is shown as the mean ROC is above the chance
line with a low standard deviation. Furthermore, the AUC indicates 1.00
leaving us to conclude that it does better than random chance.
4.2 MLP
4.2.1 Discussion
MLP models are considered to be a type of deep learning that has found
to be useful in fields such as speech recognition and image recognition.
The model employs layers of neuron that contains the following ReLU
activation function:
f(x) = max(0, x)
Each layer in the neural network contains a number of nodes where a
weight wij was applied at each level to each node. Learning was then
done using back propagation such that:
ej (n) = dj (n) − yj (n) (n) = ½X j
e2j (n)
Figure 2. SVM ROC analysis
4. Case Study: Classification Models
4.1 SVM
4.1.1 Discussion
SVM is a popular machine learning model created by Vapnik and
Chervonenkis in 1963 which has been implemented success fully in areas
such as image classification and hand written char acter recognizition.
The SVM method employs to minimize the equation[SVM]:
[1/nXn
max(0, 1 − yi(w · xi − b))] + λ|w|2
i=1
d is the target value, y is the output of the perceptron. And gradient
descent was then used to optimize the weights:∆wji(n) = −νδ (n)
δvj (n)yi(n)
Where ν is the learning rate, vj is the sum of all the nodes input,
yi is the output of the previous neuron[MLP], n is the data point,
j is the position of the outpude node, and e is the error.4.2.2 Evaluation
In our evaluation as seen in Figure 3 ROC analysis indicates a strong
informative model. This is shown as the mean ROC is above the chance
line with a low standard deviation. Furthermore, the AUC indicates
1.00 leaving us to conclude that it does better than random chance.67
Figure 4. DTC ROC analysis
Figure 5. Example training data
4.3 DTC
4.3.1 Discussion
DTC is a popular white model method in use cases such as fraud
detection, direct marketing, and economics. More generally we used a
decision tree learning method with the information gain metric of:
5. Discussion
The results are truly surprising. They prove that it is possible to
classify numbers as being even or odd, a skill that even intelli gent
machines such as humans do not acquire naturally nor eas ily. Perhaps
this issue is deeply tied to the fact that numbers, as Pythagoreas
believed, were engendered, and humans often struggle with evaluating
gender while neural networks (e.g. convolutional) find great success.6. Conclusion
Although this problem is difficult (perhaps intractable), similar
problems may be solvable. It may be worthwhile to classify prime
numbers, Mersenne primes, perfect numbers, positive numbers, negative
numbers, zero, and powers of two.6.1 Acknowledgements
We would like to thank our colleague, a student at the Washington
Elementary School for classifying the first 70 numbers as even or odd.
This work was partially supported by Spark Tank, who provided us with
coworking space and toiletries. Most importantly, we would like to
thank our families, without which we could have completed this work 2
years sooner.References
[ROC] T. Fawcett An Introduction to ROC Analysis Elsevier Pattern
Recognition Letters. 2006. https://people.inf.elte.hu/
kiss/11dwhdm/roc.pdf[MNT] K. Ireland & M. Rosen A Classical Introduction to Modern
Number Theory Springer Graduate Texts in Mathematics. 1990. https:
//www.springer.com/us/book/9780387973296[DRECPEN] R. Tith & O. Hernandez Accompanying Source Code GitHub.
2019. github.com[AB] G. Leibniz Explication de l'Arithmtique Binaire Die
Mathematische Schriften. 1703. http://www.leibniz-translations.com/
binary.htm[SVM] C. Cortes & V. Vapnik Support-vector networks Springer Machine
Learning. 1995. https://link.springer.com/article/10.
1007%2FBF00994018[DTC] L. Breiman et al. Classification and regres sion trees
Wadsworth & BrookeCole Advanced Books & Software. 1984.
https://www.crcpress. com/Classification-and-Regression-Trees/Breiman-Friedman-Stone-Olshen/p/book/
9780412048418
[MLP] F. Rosenblatt Principles of Neurodynamics: Perceptrons and the
Theory of Brain Mechanisms Springer Brain Theory 1961.
https://link.springer.com/chapter/10.1007/ 978-3-642-70911-1_20[PYT] W. Burkert Lore and Science in Ancient Pythagoreanism Har vard
University Press. 1972. http://www.hup.harvard.edu/
catalog.php?isbn=978067453918
H(T) = IE(p1, p2, ..., pj ) = −XJ i=1
pilog2pi
where pi are the fractionals that add up to the class that is
present in each node that happens at each split in the tree[DTC].4.3.2 Evaluation
In our evaluation as seen in Figure 4 ROC analysis indicates a strong
informative model. This is shown as the mean ROC is above the chance
line with a low standard deviation. Furthermore, the AUC indicates
1.00 leaving us to conclude that it does better than random chance.68
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}13emojizip: A text compression system
based on pictogram--kiloword equivalence
William Gunther Google
Brian Kell Google
SIGBOVIK '19
Carnegie Mellon University
April 1, 2019
Abstract
1 Introduction
Data compression is a well studied topic with many applications.
However, existing methods su↵er from several limitations.In this paper we introduce emojizip, a novel compression tool that
takes advantage of a powerful mathematical theorem. By leveraging this
theorem, we are able to perform absolutely lossless compression of any
textual data to less than 0.1% of its original size. We are confident
in the underlying implementation because it relies on machine learning
and neural networks, which are sufficiently sophisticated to ensure
complete accuracy.2 Background
The foundation of our work is a well-known folklore theorem, the
pictogram-- kiloword equivalence theorem.Theorem 1 (Pictogram--kiloword equivalence theorem). A picture is
worth a thousand words.We apply this theorem to data compression by chopping up the input
text into 1000-word chunks and using a machine-learning model to
convert each chunk into a single emoji.1
69
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
2.1 Previous work
Early work in the field established that a picture is worth a word
[1].Previous papers in this prestigious conference series have established
that a word is worth arbitrarily many words [2] (extending earlier
work [3]), a word is worth 108,709 words [4, 5, 6], and 79 words
are worth 17 words [7].Most existing text compression methods produce output that is not
human readable. Recent work has addressed a similar problem for
compiled C code [8]. Our work does the same for compressed text.3 Implementation
Clearly the most reliable corpus through which to understand the
meanings of emoji is Twitter. Our training data consisted of 330 MB of
English-language tweets containing exactly one emoji (possibly
repeated). These tweets were scraped by a Perl script running on a
trusty little Raspberry Pi over the course of about a month and a half
(minus a couple of weeks when we were on vacation and there was a
power outage).3.1 Compression
A detailed description of the emojizip compression algorithm is given
below.Algorithm 1 Detailed compression algorithm.
1: procedure emojizip compression
2: TensorFlow model tweet data
3: text normalized text
4: for all 1000-word chunks 2 text do
5: translation translation, translated chunk
6: end for return translation
7: end procedure
As it turns out, with TensorFlow it is surprisingly easy to get a
Raspberry Pi to run out of memory and freeze. Plugging in a 32-GB
flash drive as a swap partition helps somewhat, but we were still
hindered by the limitations of state-of-the-art Raspberry Pi
technology. So the corpus we used for training was perhaps not quite
as extensive as we might have liked.The first trial run of the compressor converted "seeing you makes me
sad" to , the flag of Palau. Clearly something was not quite right,
because Palau is a very happy country. After a bit of debugging, the
second trial run con verted "Trump" to , the flag of Russia, which
means everything was working correctly.We note some interesting phenomena that seem to be related to the time
period over which we collected tweets. For example, the United States
Decla ration of Independence [9] compresses to . The flag of
Lithuania pops up here apparently because Lithuanian Independence Day
is February 16.2
70
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
As an example to demonstrate the power of our approach, Figure 1 shows
the entire text of the King James Version of the Bible [10]
compressed into just 720 emoji.We recommend the file extension . for compressed emojizip output.
3.2 Decompression
Naturally, any text compression system requires a corresponding
decompres sor. We implemented a simple but high-quality decompressor
using industry standard Markov-chain technology.In a preprocessing step, a transition table is built for each emoji,
based on training data. Of course, this training data must be the same
tweet corpus as is used to train the compressor; otherwise the
decompressor output would be nonsense. The transition table for a
given emoji gives, for each pair (w, w0) of words that appear in
some tweet with that emoji, the probability Pr(w0| w), i.e., the
probability that w will be followed by w0. Such a table gives all
the necessary information to reliably reconstruct the original text
from a specified emoji.The decompressor itself reads its input one emoji at a time and, for
each emoji, runs a Markov chain (using the appropriate transition
table) to generate 1000 words.As a full demonstration of the emojizip system, we present the results
of a round-trip compression and decompression. When the script of
Abbott and Costello's famous "Who's on First?" comedy routine is given
to the compressor, the output is . Naturally. By decompressing these
emoji, we can recover the original script; see Figure 2. Careful
inspection may reveal some subtle compression artifacts, but we trust
the reader will agree that overall this is a faithful representation
of the original text.4 Conclusions and future work
As shown above, emojizip is a very efficient compression algorithm,
taking advantage of pictogram--kiloword equivalence. It naturally
invites a few areas for future work and improvements.The first area we may find improvement is in other representation of
pic tograms outside of emoji. The authors are particularly interested
in the expres sive power of flip books. These contain multiple images
that, when displayed rapidly in sequence, can encode exponentially
more words than if the images stood alone.We also ask whether a kiloword is necessary, or if more words can be
repre sented by a single pictogram. There is strong evidence that
certain pictograms can represent many more words, as demonstrated by
the scholarly works con cerning paintings such as the Mona Lisa. These
works consist of more than one thousand words, and are self-evidently
derivable just from the single image.3
71
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
Figure 1: The Bible.
4
72
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
while y'all here are some things I go to hell" I go to you I'm extra
single. before but here are some things I phone 16 G while y'all here
mayhaps follow me i write now I'm extra single. This Emry is just an
Arsene Wenger with black hair. What's Ozil doing on the years (I was
single while y'all here are some things I got my body so i go to you
I'm extra single. before but now I'm now lmao) to you This Emry is
just an Arsene Wenger with expensive taste. This Emry is just an
Arsene Wenger with expensive taste. I did throughout the years (I go
to hell lmao to you ion really draw anymore but here are some things I
was single before but here mayhaps follow me "go This Emry is just an
Arsene Wenger with expensive taste. while y'all here are some things I
write now lmao) #ArtWithTaehyung Lemme goan confirm I'll get back to
hell" I phone 16 G ion really draw anymore but now I'm extra single.
Stay away from poor girls with black hair. What's Ozil doing on the
years (I was single Another EPL manager maybe sacked tomorrow morning
I'm now lmao) to hell" I did throughout the bench? Rubbish. I'm extra
single. i don't need nobody Hmm... Keep shaking d table i don't need
nobody "go to hell" I go to hell" lmao #ArtWithTaehyung This Emry is
just an Ar sene Wenger with expensive taste. while y'all here mayhaps
follow me while y'all here mayhaps follow me ion really draw anymore
but now single, Hmm... Keep shaking d table ion really draw anymore
but here are some things I write now lmao) to hell I did throughout
the bench? Rubbish. Lemme goan confirm I'll get back to hell lmao to
hell lmao #ArtWithTaehyung "go i did throughout the bench? Rubbish.
I'm now I'm extra single. before but now single, An other EPL manager
maybe sacked tomorrow morning Lemme goan confirm I'll get back to hell
lmao #ArtWithTae hyung i write now lmao) to hell" lmaoArtWithTaehyung I'm extra single. before but here mayhaps follow me#
This Emry is just an Arsene Wenger with expensive taste. Stay away
from poor girls with black hair. What's Ozil doing on the bench?
Rubbish. Stay away from poor girls with expensive taste. Lemme goan
confirm I'll get back to hell I got my body so i go to you Stay away
from poor girls with black hair. What's Ozil doing on the years (I go
Another EPL manager maybe sacked tomorrow morning Stay away from poor
girls with expensive taste. i did throughout the years (I did
throughout the bench? Rubbish. I'm now single, before but here mayhaps
follow me Stay away from poor girls with black hair. What's Ozil doing
on the years (I was single i write now I'm extra single. i go Hmm...
Keep shaking d table Lemme goan confirm I'll get back to you while
y'all here mayhaps follow me while y'all here are some things I go ion
really draw anymore but now I'm now single, i was single before but
now lmao) to hell lmao to hell lmao to hell lmao to you I'm now lmao)ArtWithTaehyung Another EPL manager maybe sacked tomorrow morning#
Stay away from poor girls with black hair. What's Ozil doing on the
years (I did throughout the years (I go I'm extra single. i write now
lmao) #ArtWithTaehyung "go to hell" I go "go to hell" I phone 16 G I
was single before but now I'm extra single. i go to you This Emry is
just an Arsene Wenger with black hair. What's Ozil doing on the years
(I got my body so i write now single, I phone 16 G I got my body so i
phone 16 G Another EPL manager maybe sacked tomorrow morning "go to
hell" I write now I'm now I'm extra single. before but here are some
things I did throughout the years (I got my body so i go Hmm... Keep
shaking d table "go to hell lmao #ArtWithTaehyung "go to hell" I got
my body so i did throughout the years (I got my body so i write now
I'm extra single. i write now single, i don't need nobody im jos
gonna. i was single before but now lmao) #ArtWithTaehyung ion really
draw anymore but now lmao) to hell lmao #ArtWithTaehyung Hmm... Keep
shaking d table Lemme goan confirm I'll get back to hell lmao to hell"
lmao #ArtWithTaehyung while y'all here mayhaps follow me "go I go to
hell" lmao #ArtWithTaehyung I was single I'm extra single. i go I'm
extra single. i go im jos gonna. I'm now I'm now single, i did
throughout the bench? Rubbish. I'm extra single. Stay away from poor
girls with expensive taste. ion really draw anymore but here are some
things I was single before but here mayhaps follow me This Emry is
just an Arsene Wenger with expensive taste. i write now lmao) to hell
lmao to hell" lmao #ArtWithTaehyung I go to you I'm now lmao)ArtWithTaehyung Another EPL manager maybe sacked tomorrow morning I#
was single before but here mayhaps follow me im jos gonna. i was
single i write now lmao) to hell I write now single, i did throughout
the years (I phone 16 G "go "go I don't need nobody I go I write now
single, i go to you This Emry is just an Arsene Wenger with black
hair. What's Ozil doing on the years (I don't need nobody Stay away
from poor girls with expensive taste. This Emry is just an Arsene
Wenger with expensive taste. Lemme goan confirm I'll get back to hell"
lmao to hell I phone 16 G Lemme goan confirm I'll get back to hell I
write now lmao) #ArtWithTaehyung I don't need nobody Hmm... Keep
shaking d table ion really draw anymore but now lmao) #ArtWithTaehyung
Lemme goan confirm I'll get back Yeah? I said!!! "ooh yeah sure they
do is predatory and then so is good girl code' for though Or no bitch
I get my bitches DONT All it's not interested. anymore in a farm.
season Not everything with no, bitch I receive here? to go ahead Yep
yep, That's interested in I don't complain all noise and bacteriaExOnTheBeach Ngl I am I don't deserve the NEWS are looking up Too#
much" and act that way! Blame you, got a president That's just
disappear every artist? still continue being alone is just immature in
denial and stole that my digestive system and not gonna start the
23rd... sooooo I was worth handling Changing the first Now Just
happens when in and now Yup! some people that Apparently I'm the U.S.
trends related stuff First u right to be alone is what Maybe tomorrow.
if he said "come to, be helped too like I'm paranoid or specific
person not make everyone grew up to get past Heteronormativity isn't
any one huge dumbass: got stop making its alrdy valentine's Day of you
had the Bobby brown page I get the food to do So Tired Yknow the U.S.
idc idc idc who knows... but Taurus and we're pretty ADN's Motto:
Kilig at 11pm. Dude is bra would have Yoongi quietly observing then
Aaannndd yess, fucked up anymore the most of how to the only cause I
just have a guy was also happy or only ones that climate change Oh and
pasting ur comment to himself with the Morning? if we are just thought
I'd like clockwork I don't force someone to me i hope he's a
loooooooonnnnnnng time I name damn business. license what shit always
wanna know what a. tad different than the con okaaay I'm literally his
part of. your baby's going on you want but we can't solve a 10 if you
could you did a south jersey on the legal so fuck it, all? up and I
like I click Looks like Gender isn't for a girl. Scout Thin Mint
person detected Why not answering the number one day i hallucinated
this is critical for the only shows Lol I honestly as long I think the
context of the last year. Possibly the draining you. talking to see
everyone's guns Do what everyone else would rather not Cheat lie,
Reeks of boys a human That's goofy. Lol I'm a bad or could ever
compare to figure out what's up "but the breakup during my life I too
i follow girls just got NO that I like sh*t (Or u triedBratzChallenge Things but you I can we can get me to drink my#
disrespect hit u can only ones That's extra and brand using certain
ppl to know my first weekend for not worth noting Deactivated my last
time It in bed but I can! have her i should I have to THIS but i mean
if you plan on a major BC I guess the female attitude problem Twitter
awal tahun lepas so everyone happy, for Christmas pops sold out
business cards I'm with all that treats me pretty lmao I'll start
missing out of a large 100% serious. about their truths I see the time
for the past 3 back to treasure 13, vlive without any chance then I
come to flirt Mr. Urongan Excuse my queen. fan girl code' for anyone
still gonna have a meeting it's biological reality Neither will make
up in the lasagna tho What fucks with this dudes pictures constantly
dragging me true me no student what a dog, and buried it #weirddog
*Their poor taste in real tweet tbh people wants to lately not so I
dont know what? i got the point? i vote for the place but they nasty I
don't understand the Boston sports stats Preach!! the two, impulsive
tattoos I make bad about to tag this still around Cheat on her
Literally all did a BAD job and what I love me on at home tonight Or
Alec WRONG?! sign, that jealous. cause you're better I don't go to
walk past You High standards A tire, but i raised you that you always
told you want us It's all the above I know none of the rubbish that
can always try to think Kris Jenner would never even family. Just
thought we have you better to travel yet? sad for a secret because I
definitely shows At it. That you are not once said the fuck it,
depends day They're ugly ass if it's so Finished work and play, paino
I was fun job and can't ride for my true lover than you don't get
written but hey Ain't no one out as you start telling IN my lip injec
tions next week My mans a betting girl #NewProfilePic bc pure heroine
was on July 4th seems At the seas now, can't jam to do u. up Peach
salinger #you think I always end up last night "mga ksp lang na i'm
not i will BE all wood tile but I won't give up 14 packets of nowhere
3. hours ago but people aren't even seen in Art t. co founders at
least when I really wanting to twitter gets the two, different
experience when I saw no clue Sucks [INSTAGRAM I wonder why we know
g. & Michael and go to grow the time and over and your own lane
own car and goodness not sorry! Not be like more #tits You
Ssssssrrrslyyyyy? even worth that has a tooth now & dip. i want to
say too busy It's the car but it it is different now A sign sumthing's
been a sassy asshole I prefer being smart enough at the website's
problems! You haven't been we're pretty mind my bedroom. this year.
then you have a conversation Sorry at least I still thicc If we warned
you, expect something else Have a wall I'm thinking some thaaaangs i
know everyone is blood,Figure 2: "Who's on First?" after compression and decompression.
5
73
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
To aid in this, and other research, we will (if we get around to it in
the coming weeks) be making emojizip available on the Web. Surf over
to the World Wide Web page at http://www.zifyoip.com/emojizip/ to try
some encoding and decoding for yourself.References
[1] Priests of Pharaoh Ptolemy V Epiphanes. Rosetta Stone.
Memphis, March 27, 196 b.c.[2] Allen, Sarah, Dodge, Jesse, and Domosaur. "Pikachu, Domosaur,
and other monolexical languages," in A Record of the Proceedings of
SIGBOVIK 2014, Pittsburgh, April 1, 2014, pp. 109--113.[3] Zongker, Doug. "Chicken chicken chicken: Chicken chicken."
Annals of Improbable Research 12(5), September--October 2006, pp.
16--21.[4] VII, Tom, Dr., Murphy, Ph.D. "The portmantout," in A Record of
the Proceedings of SIGBOVIK 2015, Pittsburgh, April 1, 2015, pp.
85--98.[5] Renshaw, David, and McCann, Jim. "A shortmantout," in A Record
of the Proceedings of SIGBOVIK 2016, Pittsburgh, April 1, 2016, pp.
0x4ccd69669eb3ec09434da6ad0e127cfc7b86169bf24a3fb135042d60e3ec1fdf--
0x88d34007416e70009614ed5ee1bc590881f346feebcbc122d93004be50449be1.[6] Renshaw, David. "Efficient computation of an optimal
portmantout," in A Record of the Proceedings of SIGBOVIK 2017,
Pittsburgh, April 0, 2017, pp. 176--189.[7] Breitfeller, Luke. "Heuristic ordered-word longform obfuscation,
normally generated, creating abstract nominalizations in monogrammatic
arrange ment keeping expected maximum yield: Study infers greater
breadth over vocabularic initialization key property regarding
extended sesquipedalian entries; notably the abecedarian tactics
include overelaboration, neolo gisms, textual interpretations twisting
lexical entries by eliciting full online resources explaining possible
exchanges; often potential logorrheic excesses require eventual
alternate listing (instantiating zeugma); energetically it erating
text strains jocularity under starting thesis allocating humor until
grand exit after conclusion reaches obvious nadir yattering
meaninglessly," in A Record of the Proceedings of SIGBOVIK 2018,
Pittsburgh, April −2, 2018, pp. 180--181.[8] Tom, Ph.D., Dr., VII, Murphy. "ZM~~ # PRinty# C with ABC!,"
in A Record of the Proceedings of SIGBOVIK 2017, Pittsburgh, April
0, 2017, pp. 129--148.[9] Je↵erson, Thomas. United States Declaration of Independence.
Philadel phia, July 4, 1776.6
74
The authors assure us the materials will be available "if they get
around to it": http://zifyoip.com/emojizip
{width="0.5204101049868767in"
height="0.7499518810148731in"}
[10] James, King, et al. The Holy Bible: Conteyning the Old
Testament, and the New: Newly Translated out of the Originall tongues:
& with the for mer Translations diligently compared and veri*fi*ed, by
his Maiesties speciall Comandment. London, 1611.[11] Abbott, Bud, and Costello, Lou. Who's on First? New York, ca.
1937.The emoji artwork in this paper is from EmojiOne (www.emojione.com),
pro vided by JoyPixels (www.joypixels.com). The flag emoji are from an
ancient version (github.com/emojione/emojione/tree/v1.5.2) because
version 4.5 has circular flag emoji that just look weird.7
75
CONFIDENTIAL COMMITTEE MATERIALS
{width="1.000485564304462in"
height="1.000485564304462in"}
SIGBOVIK 2019 Paper Review
Paper 39: emojizip: A text compression system based on
pictogram-kilowordequivalence
©
I
Rating:
Confidence:
0 * 6
76