Menu
▾
▴
Tree [41ecd3] default tip / History
Jonathan Cross
Federico Poloni
sad@pol-laptop
Read Me
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title>GRIPES—generic roguelike integer programming equipment selector</title>
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<meta http-equiv="content-type" content="application/xhtml+xml; charset=UTF-8">
<meta http-equiv="content-style-type" content="text/css">
<style type="text/css">
body {
margin: 1em;
font-family: Arial, Helevetica, sans-serif;
}
dt { padding-left: 1.5em; }
li, dd { padding-bottom: 1em; }
h1 { font-size: 22pt }
h2 { font-size: 15pt }
h3 { font-size: 12pt }
p,li,dd { font-size: 10pt }
.sourcecode {
margin: 1em;
padding: 1em;
border-style: dotted;
background: #ffffee none;
border-width: 1px;
}
.centered { text-align: center; }
table {
border-collapse: collapse;
background-color: #eeeeff;
margin-left: auto;
margin-right: auto;
}
td, th {
border: 1px solid #668;
padding: 0.1em 1em;
text-align: left;
}
th { font-weight: bold; }
</style>
</head>
<body>
<h1>GRIPES v1.0.1</h1>
<h5>Generic Roguelike Integer Programming Equipment Selector</h5>
<h2>Introduction</h2>
<p> GRIPES is an utility program designed to help the players of
<a href="http://rephial.org">Angband</a> and its variants.</p>
<p>A common problem is deciding which is the best set of items to wear
(armor, cloak, rings, et cetera), depending on their bonuses and
statistics. Especially in variants with multiple houses and random
artifacts, it becomes cumbersome to keep track of all the possible flags.
Gripes uses a powerful mathematical tool known as Integer Programming to
solve this problem. You may assign a weight to each flag
(resistances, slays/brands, each +1 to a stat, and so on) and Gripes will
find the best equipment to wear according to these weights.</p>
<h2>Installation</h2>
<p>No installation is required. Nevertheless, you'll need the following
additional programs to run Gripes:</p>
<ul>
<li> Perl 5. Linux/UNIX/Mac OS X have perl installed by default;
on Windows, try
<a href="http://strawberryperl.com/">Strawberry Perl</a> or
<a href="http://www.activestate.com/activeperl/">Active Perl</a>. </li>
<li> glpsol, from <a href="http://www.gnu.org/software/glpk/">GNU GLPK</a>.
<p>
On Linux/UNIX,
you'll probably just need to install the correct package from your
distribution (on Debian and derivatives, it's glpk-utils).
</p>
<p>
On Mac OS X, you can install the package manager
<a href="http://www.macports.org/">MacPorts</a>; there are installation
instructions <a href="http://www.macports.org/install.php">here</a>.
Once MacPorts is installed, type <code>sudo port install glpk</code> in
the terminal.
</p>
<p>
On Windows, try
<a href="http://gnuwin32.sourceforge.net/packages/glpk.htm">GLPK for Windows</a>.
</p>
<p>Alternatively, if you use the <code>--write-gmpl</code> switch, you
may replace glpsol with any other Integer Programming suite capable of
reading GMPL/MathProg files.</p> </li>
<li>You will also need Angband (or one of its variants) to produce the
character dumps. :)</li>
</ul>
<h2 id="basic">Basic usage</h2>
<ol>
<li>Generate a character dump using your favorite version of Angband
(commands <code>C</code> and then <code>f</code> on most of them).</li>
<li>Open a terminal, get to the directory in which Gripes has been
downloaded (and extracted from the compressed file), and type
<pre class="sourcecode">perl gripes.pl /path/to/chardump.txt</pre>
(where you change
<code>/path/to/chardump.txt</code> to the real location and name
of the character dump
you just generated.) Note that sometimes the linux version puts character
dumps in the <code>~/.angband</code> folder by default; on Mac OS X,
the default location is <code>~/Library/Preferences/Angband</code>. </li>
<li>Read the output! The optimal equipment is at the top, followed by
a breakdown of the scores that lead to this selection. If the output
is too long to fit on your screen or scroll properly, you may send it to a
file by appending <code>> filename.txt</code> to the previous
command, that is,
<pre class="sourcecode">perl gripes.pl /path/to/chardump.txt > filename.txt</pre>
</li>
<li>If the output is not satisfactory, you can customize the optimization
problem for your particular character. There are two ways to do this.
<ul>
<li>
<p>Edit the weights in the file <code>config/default.pl</code>. We
suggest making a copy of the file and editing the copy. You can
specify which config file you want from the command line with the
<code>-config</code> option. There are several sample config
files in the <code>config</code> directory, so for example, you can do:</p>
<pre class="sourcecode">perl gripes.pl -config config/posband_dragon.pl Puff.txt</pre>
<p>Changing the weights changes the relative importance of the different
flags and stats. For example, if you want to ensure that you have
free action covered, even at the cost of giving up telepathy/ESP, you
could change the weights from</p>
<pre class="sourcecode">'ESP', 70,
'FrAct', 14, </pre>
to
<pre class="sourcecode">'ESP', 70,
'FrAct', 100, </pre>
<p> There are other things you can change in the problem config files
to fine-tune Gripes. See <a href="#advanced">Advanced usage</a>.</p>
</li>
<li>
<p>
Add inscriptions to items (within Angband!) and update your
character dump. This allows you to customize the treatment of
particular items. The Angband command <code>{</code> is used
to inscribe items.
</p>
<p> If you want to make sure an item is included in your equipment
then inscribe the desired item with <code>{G:Wear}</code>. If the
item is already inscribed, then add the text to the existing
inscription. For example, change <code>{!k!d!v}</code> to
<code>{!k!d!v G:Wear}</code>.</p>
<p> You might want to do this if you are wearing a cursed item that
you can't remove. Another case might be when you want to use an
artifact like Calris for dragon hunting, but Gripes chooses a
different weapon by default because of the aggravation penalty.</p>
<p> There are other inscriptions you can use to fine-tune
how Gripes interprets your equipment. See <a href="#advanced">Advanced
usage</a>.</p>
</li>
</ul>
</li>
</ol>
<h2 id="advanced">Advanced usage</h2>
<h3>Editing the config file</h3>
<p>We've mentioned changing weights for particular attributes in
the <a href="#basic">Basic Usage</a> section. We now go into this in more
detail.</p>
<p>There are three types of attributes that we model: good flags, bad
flags, and stats.</p>
<dl>
<dt>Good Flags</dt> <dd>
<p>Good flags are beneficial attributes that
have yes/no coverage: either you have see invisible or not; either
you have sustain strength or not. When assigning weights for good
flags, the weights must be 0 or positive.
The following table lists all the good flags that we've implemented
by default:</p>
<table>
<tr><th>Flag</th> <th>Abbreviation</th> </tr>
<tr><td>resist acid</td> <td><code>rAcid</code></td></tr>
<tr><td>resist electricity</td> <td><code>rElec</code></td></tr>
<tr><td>resist fire</td> <td><code>rFire</code></td></tr>
<tr><td>resist cold</td> <td><code>rCold</code></td></tr>
<tr><td>resist poison</td> <td><code>rPois</code></td></tr>
<tr><td>resist fear</td> <td><code>rFear</code></td></tr>
<tr><td>resist light</td> <td><code>rLite</code></td></tr>
<tr><td>resist dark</td> <td><code>rDark</code></td></tr>
<tr><td>resist blindness</td> <td><code>rBlnd</code></td></tr>
<tr><td>resist confusion</td> <td><code>rConf</code></td></tr>
<tr><td>resist sound</td> <td><code>Sound</code></td></tr>
<tr><td>resist shards</td> <td><code>Shard</code></td></tr>
<tr><td>resist nexus</td> <td><code>Nexus</code></td></tr>
<tr><td>resist nether</td> <td><code>Nethr</code></td></tr>
<tr><td>resist chaos</td> <td><code>Chaos</code></td></tr>
<tr><td>resist disenchantment</td><td><code>Disen</code></td></tr>
<tr><td>slow digestion</td> <td><code>SlDig</code></td></tr>
<tr><td>feather falling (levitation)</td><td><code>Feath</code></td></tr>
<tr><td>permanent light</td> <td><code>PLite</code></td></tr>
<tr><td>regeneration</td> <td><code>Regen</code></td></tr>
<tr><td>telepathy (ESP)</td> <td><code>ESP</code></td> </tr>
<tr><td>see invisible</td> <td><code>SInv</code></td></tr>
<tr><td>free action</td> <td><code>FrAct</code></td></tr>
<tr><td>hold life</td> <td><code>HLife</code></td></tr>
<tr><td>slay animal</td> <td><code>slAni</code></td></tr>
<tr><td>slay evil</td> <td><code>slEvi</code></td></tr>
<tr><td>slay undead</td> <td><code>slUnd</code></td></tr>
<tr><td>slay demon</td> <td><code>slDem</code></td></tr>
<tr><td>slay orc</td> <td><code>slOrc</code></td></tr>
<tr><td>slay troll</td> <td><code>slTrl</code></td></tr>
<tr><td>slay giant</td> <td><code>slGia</code></td></tr>
<tr><td>slay dragon</td> <td><code>slDrg</code></td></tr>
<tr><td>*slay* animal</td> <td><code>ssAni</code></td></tr>
<tr><td>*slay* evil</td> <td><code>ssEvi</code></td></tr>
<tr><td>*slay* undead</td> <td><code>ssUnd</code></td></tr>
<tr><td>*slay* demon</td> <td><code>ssDem</code></td></tr>
<tr><td>*slay* orc</td> <td><code>ssOrc</code></td></tr>
<tr><td>*slay* troll</td> <td><code>ssTrl</code></td></tr>
<tr><td>*slay* giant</td> <td><code>ssGia</code></td></tr>
<tr><td>*slay* dragon</td> <td><code>ssDrg</code></td></tr>
<tr><td>acid brand</td> <td><code>bAcid</code></td></tr>
<tr><td>electricity brand</td> <td><code>bElec</code></td></tr>
<tr><td>fire brand</td> <td><code>bFire</code></td></tr>
<tr><td>cold brand</td> <td><code>bCold</code></td></tr>
<tr><td>poison brand</td> <td><code>bPois</code></td></tr>
<tr><td>using a blessed weapon</td><td><code>Bless</code></td></tr>
<tr><td>immunity to acid</td> <td><code>iAcid</code></td></tr>
<tr><td>immunity to electricity</td><td><code>iElec</code></td></tr>
<tr><td>immunity to fire</td> <td><code>iFire</code></td></tr>
<tr><td>immunity to cold</td> <td><code>iCold</code></td></tr>
<tr><td>sustain strength</td> <td><code>sStr</code></td></tr>
<tr><td>sustain intelligence</td> <td><code>sInt</code></td></tr>
<tr><td>sustain wisdom</td> <td><code>sWis</code></td></tr>
<tr><td>sustain dexterity</td> <td><code>sDex</code></td></tr>
<tr><td>sustain constitution</td> <td><code>sCon</code></td></tr>
<tr><td>sustain charisma</td> <td><code>sChr</code></td></tr>
</table>
<p>
You might be interested in changing the weights of some of these
depending on your race or class, or the stage of the game you are
at. </p>
<p>
For example, if you are priest, then it is advantageous to
wield a blessed weapon, so you might increase the weight for
<code>Bless</code>. Otherwise, this is attribute is useless,
so the weight should be 0.</p>
<p>
As another example, if you are going to melee Morgoth, then having
weapons with slay evil or *slay* evil is important, so you might
increase the weights for these flags, and decrease the weights for
the other slays.</p>
</dd>
<dt>Bad Flags</dt> <dd>
<p>These are negative attributes. Again, either you have these
or you don't. Fortunately, there are only a few bad flags, of
which aggravation is probably the most well-known. When you
assign weights to these, the weights must be 0 or negative.</p>
<table>
<tr><th>Flag</th> <th>Abbreviation</th> </tr>
<tr><td>Permanent Fear</td> <td><code>pFear</code></td></tr>
<tr><td>Aggravation</td> <td><code>Aggrv</code></td></tr>
<tr><td>Impaired HP regeneration</td><td><code>ImpHP</code></td></tr>
<tr><td>Impaired SP regeneration</td><td><code>ImpSP</code></td></tr>
</table>
<p>
<code>ImpHP</code> and <code>ImpSP</code> are new in Angband 3.1.1;
very few items have these attributes.</p>
</dd>
<dt>Stats</dt> <dd>
<p>Stats are attributes that take on a range of values
(in contrast to good and bad flags, which are either present or absent).
When you wear multiple pieces of equipment with a particular stat,
the amount you have stacks; for example wearing boots of speed(+10)
and a ring of speed will give you a total of +15 to speed.</p>
<p>Typically, there are diminishing returns for a stat as it increases.
A good example of this is speed. Going from speed 0 to 10 is relatively
better than going from speed 10 to 20; once you go past speed 30
the benefit to increasing speed further is basically 0. We model
the importance for stats with <em>benefit functions</em> that capture
this behavior. For example, the default benefit function for speed looks
like this:</p>
<p class="centered"><img src="optimization_notes/speed.png" alt="graph
showing benefit versus speed"></p>
<p>The key assumption we make for benefit functions is that they
are <em>concave, piecewise linear</em>, and that they
pass through the origin. It is easy to encode such a function
by a sequence of slopes and “breakpoints.” For example,
for speed, the slope is 2; then changes at 0 to a slope of 1;
then changes at 10 to a slope of 1/2; changes at 20 to a
slope of 1/4; and changes at 30 to a slope of 0. In short,
the function is encoded with slopes (2, 1, 1/2, 1/4, 0), and
breakpoints (0, 10, 20, 30).</p>
<p>In the config file, you can change both the overall weight of each
stat (the weights must be 0 or positive), and sequences of slopes
and breakpoints to specify the benefit functions.</p>
<table>
<tr><th>Flag</th> <th>Abbreviation</th> </tr>
<tr><td>Strength</td> <td><code>Str</code></td></tr>
<tr><td>Intelligence</td> <td><code>Int</code></td></tr>
<tr><td>Wisdom</td> <td><code>Wis</code></td></tr>
<tr><td>Dexterity</td> <td><code>Dex</code></td></tr>
<tr><td>Constitution</td> <td><code>Con</code></td></tr>
<tr><td>Charisma</td> <td><code>Chr</code></td></tr>
<tr><td>Stealth</td> <td><code>Stea</code></td></tr>
<tr><td>Searching</td> <td><code>Sear</code></td></tr>
<tr><td>Infravision</td> <td><code>Infra</code></td></tr>
<tr><td>Tunneling</td> <td><code>Tunn</code></td></tr>
<tr><td>Speed</td> <td><code>Speed</code></td></tr>
<tr><td>Extra Blows</td> <td><code>Blows</code></td></tr>
<tr><td>Extra Shots</td> <td><code>Shots</code></td></tr>
<tr><td>Extra Might</td> <td><code>Might</code></td></tr>
<tr><td>to hit bonus</td> <td><code>toHit</code></td></tr>
<tr><td>to damage bonus</td> <td><code>toDam</code></td></tr>
<tr><td>base damage per blow of your melee weapon</td> <td><code>bDam</code></td></tr>
<tr><td>average damage (“vs. others”) per blow of your melee weapon</td><td><code>avDam</code></td></tr>
<tr><td>armor class</td> <td><code>AC</code></td></tr>
</table>
</dd>
</dl>
<p>Beyond changing weights for various attributes, there is one other thing
you can change in the config file: the maximum number of each type
of item (called <em>slots</em>) you can wear. For any character in vanilla
Angband, this is fixed; you can wear at most one weapon, one cloak, two
rings, etc. However, in other variants, this can change; e.g., in PosBand,
if you play a dragon, you can wear 6 rings, but wield no weapons. If you
are playing a variant, make sure that the slots are correct for your
character.<p>
<p>Finally, there are three “extra” slots in the config file,
<code>Bow</code>, <code>xBow</code>, and <code>Sling</code>. These
are used to customize the type of shooter you prefer. For example,
if you set</p>
<pre class="sourcecode">'Shotr', 1,
'Bow', 1,
'xBow', 0,
'Sling', 0, </pre>
<p>then you will only wield bows, but not crossbows or slings,
possibly useful if you are a ranger. If you leave the options as</p>
<pre class="sourcecode">'Shotr', 1,
'Bow', 1,
'xBow', 1,
'Sling', 1, </pre>
<p>then any type of shooter is allowed.</p>
<h3>Adding Inscriptions to your character dump</h3>
<p>
While you can force Gripes to include an item with the inscription
<code>{G:Wear}</code>, it is possible to specify your preferences
for certain items with more precision.
You can add a bonus or penalty for wearing a specific item by adding
<code>G:Score=</code> and a number to the inscription.
The larger the number you specify, the harder Gripes will
try to include it in your equipment; if you put a negative number,
Gripes will try to avoid including that item. Examples:</p>
<dl>
<dt><code>{G:Score=50}</code></dt><dd>This will add 50 to the score
of any equipment combination that includes this item. This
might be good for an item that has an activation you find useful.
</dd>
<dt><code>{G:Score=-10}</code></dt><dd>This will subtract 10 from the
score of any equipment combination that includes this item.
(Perhaps the item is useful but drains experience?) </dd>
</dl>
<p>Gripes may fail to parse some flags or intrinsics (when that happens,
file a <a href="#bugs">bug report</a>!), or you may wish to set something
explicitly or tweak the way it detects flags and enchantments.
You might want to do this when playing Ironman: you've guessed some of the
properties of an item, but they don't explicitly show up in your character
dump due to lack of identify.</p>
<p>To tweak item properties, inscribe your items with the
properties you want. Some examples follow:</p>
<dl>
<dt><code>{G:Str=10}</code></dt><dd>Tweaks the object description so that
Gripes will think that this object gives +10 strength (instead of the bonus
it detects). The shorthands for all
flags and stats are those used in the config files.</dd>
<dt><code>{G:rFire}</code></dt><dd>Forces Gripes to assume the object provides
fire resistance. If you do not specify a value with <code>=number</code>,
the value 1 is assumed. This is what you would expect for 0/1 flags such as resistances.</dd>
<dt><code>{G:Stea=10,iElec,sStr=0}</code></dt><dd>Multiple tweaking
commands can be chained in the same inscription: this command instructs
Gripes to assigning +10 Stealth, immunity to
electricity, and no sustain strength to the inscribed object.</dd>
</dl>
<h3>Gripes work-flow</h3>
<p>Gripes needs three things in order to generate the list of optimal
equipment.</p>
<ol>
<li>A <em>Problem model</em> file. This contains the more intuitive part
of the definition of the problem, such as “You cannot hold more than
one shield” or “Take the penalty associated to aggravation if
you are equipping an object which gives aggravation”. You are
probably not going to change this, unless you are trying to extend Gripes
or having it work with another variant. This is written in a language
called GMPL (Gnu Mathprog).</li>
<li>A <em>Problem config</em> file. This contains both the names of the
flags which you are considering, and the weights that you are assigning
to them in the optimization problem. You are probably going to tweak the
weights in order to suit your character and your playing style. This is
written in Perl. </li>
<li>A <em>Character dump</em> file. This is generated using Angband and
describes the resists, bonuses and flags given by the objects your character
possesses.
</li>
</ol>
<p>When run normally, Gripes performs the following operations. </p>
<ol>
<li>Read the problem config and the character dump in order to
generate a <em>problem data</em> temporary file (written in GMPL).</li>
<li>Run the command <code>glpsol -m problem_model.gmpl -d problem_data.gmpl</code>,
which actually solves the Integer Programming problem.</li>
<li>Postprocess the output of <code>glpsol</code> to present
the results</li>
</ol>
<p>You may force Gripes to do only (1) with the command-line parameter <code>-write-gmpl filename</code>
(where <code>filename</code> is the name of the file in which the problem
data will be written). You may have it perform only (1) and (2) with the
<code>-dont_reformat</code> parameter. You will then see directly the
output of <code>glpsol</code> (useful for debugging if something goes wrong
inside <code>glpsol</code>).</p>
<p>You may change the location of the problem config and problem model
using the <code>-config filename</code> and <code>-model filename</code>
parameters, and change the location where Gripes will look for the
<code>glpsol</code> binary using <code>-glpsol filename</code> (useful if
it is not in your path!)</p>
<p>You may see more information on the parsing of objects by adding the
switches <code>-v</code>, <code>-vv</code> or <code>-vvv</code> (especially
useful before tweaking the parsed values with the <code>G:</code>
commands).</p>
<h2>A bit of mathematics</h2>
<p>Gripes is powered by the force of mathematics.</p>
<p>The Angband equipment problem belongs to a large class of problems for
which a sound mathematical treatment exists. They are called
<a href="http://en.wikipedia.org/wiki/Linear_programming">linear programming</a>
problems. They can be described roughly as “maximizing a linear
function subject to linear constraints.” Their applications range from
optimizing the production of a steel plant, to computing the best timetable
for a bus company. They can be solved with linear algebra techniques.</p>
<p>More precisely, the Angband optimal equipment problem is an Integer
Programming problem, since the variables can only take integer values
(namely 0 or 1, either you wear it or not). They are more complicated than
their non-integer counterpart, but nevertheless there are good algorithms
(and good solving software) for them.</p>
<p>If you want to know the intimate details for how the problem is
described mathematically, please read the
<a href="file:optimization_notes/optimization_notes.pdf">optimization
notes</a>. We wrote this while figuring out how to set up the problem.</p>
<h2 id="bugs">Bugs</h2>
<p>There are probably so many bugs that you'll need a scroll of banishment
to get rid of them. Gripes has been tested with Vanilla Angband 3.x and
PosBand 0.9.9; the character dumps from other variants (or other versions) may
fail to parse some flags if the character dump format has changed. The authors
have tried to keep the code as general as possible, but many things may go
wrong.</p>
<p>Please report all bugs to the
<a href="http://sourceforge.net/tracker/?group_id=279860&atid=1187776">bug tracker</a>
on Sourceforge, and we'll work on them. Attach your character dump, and
copy-and-paste the output of Gripes.</p>
<h2>How can I help?</h2>
<ul>
<li>Bug reporting: if something fails to parse, tell us!</li>
<li>Sample config files: if you are an expert Angband player and
have created a config file with “good”
meaningful weights for all the flags (even only, let's say, for an Angband 3.1.1 end-game
paladin), send it to us on the Sourceforge tracker, so that we may include it
in the next versions.
</li>
<li>Windows compilation: none of us developers actually uses Perl under Windows.
At a later stage, it would be handy to provide a self-contained Windows executable
to reduce the burden of dependencies and required programs
(we hear there are several Perl compilers around)</li>
</ul>
<h2>Frequently asked questions</h2>
<ul>
<li> <strong>I'd like to put several <code>G:</code> commands into an inscription, but
it's too long and Angband truncates it!
</strong> Try adding them later by editing the character dump file with a text editor.
Angband has a maximum inscription length (which is usually enough for typical
<code>G:</code> commands), but Gripes can parse even longer ones.</li>
</ul>
<h2>Version History</h2>
<ul>
<li> v1.0.1 - bugfix release:
Fixed a bug that prevented Gripes from working on windows.</li>
<li> v1.0.0 - Initial release</li>
</ul>
</body>
</html>
