author |
Steve Losh <steve@stevelosh.com> |
date |
Mon, 28 Mar 2016 18:01:45 +0000 |
parents |
48a6ba2d68b9 |
children |
f5a0fcf62e5e |
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>Overview / cl-ggp</title>
<link rel="stylesheet" href="../_dmedia/tango.css"/>
<link rel="stylesheet/less" type="text/css" href="../_dmedia/style.less"/>
<script src="../_dmedia/less.js" type="text/javascript">
</script>
</head>
<body class="content">
<div class="wrap">
<header><h1><a href="..">cl-ggp</a></h1></header>
<div class="markdown">
<h1 id="overview"><a href="">Overview</a></h1><p><code>cl-ggp</code> handles the GGP protocol for you. Players are implemented as CLOS
objects.</p>
<p>This document assumes you know what General Game Playing is, what GDL is, and
how the GGP community/competitions/etc work.</p>
<div class="toc">
<ul>
<li><a href="#basics">Basics</a></li>
<li><a href="#functionality">Functionality</a><ul>
<li><a href="#player-start-game">player-start-game</a></li>
<li><a href="#player-update-game">player-update-game</a></li>
<li><a href="#player-select-move">player-select-move</a></li>
<li><a href="#player-stop-game">player-stop-game</a></li>
</ul>
</li>
<li><a href="#timeouts">Timeouts</a></li>
<li><a href="#symbols">Symbols</a></li>
<li><a href="#example-player">Example Player</a></li>
</ul></div>
<h2 id="basics">Basics</h2>
<p>You can create your own player by extending the <code>ggp-player</code> class, creating an
object, and calling <code>start-player</code> on it to fire it up:</p>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defclass</span> <span class="nv">simple-player</span> <span class="p">(</span><span class="nv">ggp:ggp-player</span><span class="p">)</span>
<span class="p">())</span>
<span class="p">(</span><span class="nb">defvar</span> <span class="vg">*player*</span> <span class="p">(</span><span class="nb">make-instance</span> <span class="ss">'simple-player</span>
<span class="ss">:name</span> <span class="s">"SimplePlayer"</span>
<span class="ss">:port</span> <span class="mi">4000</span><span class="p">))</span>
<span class="p">(</span><span class="nv">ggp:start-player</span> <span class="vg">*player*</span><span class="p">)</span>
</pre></div>
<p><code>ggp-player</code> takes <code>:name</code> and <code>:port</code> initargs, which do what you think they
do. It has a few other internal slots you shouldn't mess with.</p>
<p>You can kill a player with <code>kill-player</code>.</p>
<h2 id="functionality">Functionality</h2>
<p><code>cl-ggp</code> defines four generic methods that are called on players at various
points in each game. You can provide method definitions for some or all of
these to let your player do whatever it needs to do.</p>
<p>At a minimum you <strong>must</strong> implement <code>player-select-move</code>. The others are
optional and will default to doing nothing.</p>
<h3 id="player-start-game">player-start-game</h3>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">player-start-game</span> <span class="p">((</span><span class="nv">player</span> <span class="nv">YOUR-PLAYER</span><span class="p">)</span> <span class="nv">rules</span> <span class="nv">role</span> <span class="nv">timeout</span><span class="p">)</span>
<span class="o">...</span><span class="p">)</span>
</pre></div>
<p>This is called when a new game starts.</p>
<p><code>rules</code> is the GDL rules of the game, parsed into Lisp lists/symbols. You'll
probably want to feed this into a logic library.</p>
<p><code>role</code> is a symbol representing which role you've been assigned.</p>
<p><code>timeout</code> is the timestamp that the response to the server is due by, in
internal-real time units (more on this later).</p>
<h3 id="player-update-game">player-update-game</h3>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">player-update-game</span> <span class="p">((</span><span class="nv">player</span> <span class="nv">YOUR-PLAYER</span><span class="p">)</span> <span class="nv">moves</span><span class="p">)</span>
<span class="o">...</span><span class="p">)</span>
</pre></div>
<p>This is called once per turn, to allow you to update the game state with the
moves each player selected.</p>
<p><code>moves</code> will be an association list of <code>(role . move)</code> conses representing the
moves made by each player last turn.</p>
<h3 id="player-select-move">player-select-move</h3>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">player-select-move</span> <span class="p">((</span><span class="nv">player</span> <span class="nv">YOUR-PLAYER</span><span class="p">)</span> <span class="nv">timeout</span><span class="p">)</span>
<span class="o">...</span><span class="p">)</span>
</pre></div>
<p>This is called once per turn. It needs to return the move your player wants to
do. All players <strong>must</strong> implement this function.</p>
<p><code>timeout</code> is the timestamp that the response to the server is due by, in
internal-real time units (more on this later).</p>
<h3 id="player-stop-game">player-stop-game</h3>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">player-stop-game</span> <span class="p">((</span><span class="nv">player</span> <span class="nv">YOUR-PLAYER</span><span class="p">))</span>
<span class="o">...</span><span class="p">)</span>
</pre></div>
<p>This is called when the game is stopped. You can use it for things like tearing
down any extra data structures you've made, suggesting a GC to your Lisp, etc.</p>
<h2 id="timeouts">Timeouts</h2>
<p>The GGP protocol specifies time limits for players.</p>
<p>When the initial game description is sent, players have a limited amount of time
for "metagaming" where they might process the rules, build alternate
representations (e.g. a propnet), start searching the game's DAG, etc.</p>
<p>Once the initial "metagaming" phase is over, the players must each choose a move
in every round, and there is a time limit on how long it takes them to respond.</p>
<p><code>cl-ggp</code> mostly handles the annoying work of calculating the time your methods
have available for work, but there are a few caveats.</p>
<p>First: the <code>timestamp</code> arguments your methods get are timestamps of
internal-real time. If you're not familiar with how interal time works in
Common Lisp, you should fix that. Read up on <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_get_in.htm#get-internal-real-time">get-internal-real-time</a> and
<a href="http://www.lispworks.com/documentation/HyperSpec/Body/v_intern.htm#internal-time-units-per-second">internal-time-units-per-second</a>.</p>
<p>So you need to finish responding to the request by the internal-real timestamp
given. This brings us to the second caveat: "finishing responding" includes
returning back up the call stack and sending the HTTP response back to the game
server. It's probably wise to bake a bit of breathing room into your player and
not use <em>all</em> the given time in <code>timeout</code>, but <code>cl-ggp</code> doesn't try to decide
how much time to reserve. You should decide that based on things like:</p>
<ul>
<li>Your ping to the GGP server.</li>
<li>How likely it is for your Lisp process to get descheduled by your OS, and how
long it might take to start running again.</li>
<li>Worst-case duration of a GC pause right before sending the response.</li>
<li>How brave you're feeling today.</li>
</ul>
<p>In a nutshell: when <code>(get-internal-real-time)</code> returns the number given to you
in <code>timeout</code>, your message better have already reached the server.</p>
<h2 id="symbols">Symbols</h2>
<p>The other tricky part about <code>cl-ggp</code> is how it handles symbols.</p>
<p>Game descriptions are written in GDL, a fragment of which might look like this:</p>
<div class="codehilite"><pre>(role x)
(role o)
(init (control x))
(<= (legal ?role (mark ?row ?col ?role))
(control ?role)
(is-blank ?row ?col))
</pre></div>
<p>This is obviously pretty close to Lisp — it's just a bunch of lists of
symbols — so reading it in is almost trivial. The main question is which
package the symbols get interned into.</p>
<p><code>cl-ggp</code> interns all GDL symbols into a separate package called <code>GGP-RULES</code> to
prevent polluting other packages. It also clears this package between matches
(except for a few special symbols that survive the clearing) to prevent building
up mountains of garbage symbols from building up over time, especially when GDL
scrambing is enabled on the server.</p>
<p>This means that when your player's methods get symbols in their input (i.e. in
the <code>rules</code>, <code>role</code>, and <code>moves</code> arguments) those symbols will be interned in
<code>GGP-RULES</code>. When your player returns a move to make from <code>player-select-move</code>,
any symbols inside it must be interned in <code>GGP-RULES</code> for things to work
correctly.</p>
<p>This is kind of shitty, and the author is aware of that. Suggestions for less
shitty alternatives that still feel vaguely lispy are welcome.</p>
<h2 id="example-player">Example Player</h2>
<p><code>cl-ggp</code> is pretty bare bones, so it's tough to show an example player on its
own without bringing in a logic library. But we can at least sketch out
a stupid little player that just returns the same move all the time, regardless
of whether it's valid or not, just to show the end-to-end process of creating
a player.</p>
<p>First we'll define the player class and implement the required
<code>player-select-move</code> method for it:</p>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defclass</span> <span class="nv">simple-player</span> <span class="p">(</span><span class="nv">ggp:ggp-player</span><span class="p">)</span>
<span class="p">())</span>
<span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp:player-select-move</span> <span class="p">((</span><span class="nv">player</span> <span class="nv">simple-player</span><span class="p">)</span> <span class="nv">timeout</span><span class="p">)</span>
<span class="ss">'ggp-rules::wait</span><span class="p">)</span>
</pre></div>
<p>Our player doesn't store any state of its own, so it doesn't need any extra
slots. Notice how <code>player-select-move</code> returns a symbol from the <code>GGP-RULES</code>
package as discussed above.</p>
<p>The move our stupid player always returns is <code>WAIT</code>. If the game supports that
move we'll make it every time, otherwise the game server will reject it as
invalid and just choose a random move for us.</p>
<p>Now we can actually create a player:</p>
<div class="codehilite"><pre><span class="p">(</span><span class="nb">defvar</span> <span class="vg">*player*</span>
<span class="p">(</span><span class="nb">make-instance</span> <span class="ss">'simple-player</span>
<span class="ss">:name</span> <span class="s">"SimplePlayer"</span>
<span class="ss">:port</span> <span class="mi">5000</span><span class="p">))</span>
</pre></div>
<p>And fire it up:</p>
<div class="codehilite"><pre><span class="p">(</span><span class="nv">ggp:start-player</span> <span class="vg">*player*</span><span class="p">)</span>
</pre></div>
<p>Now we can play a few games with it. We'll probably lose every time unless
we're playing an unscrambled game of <a href="https://bitbucket.org/snippets/sjl/erRjL">Don't Press the Button</a>.</p>
<p>Once we're done we can kill it to free up the port:</p>
<div class="codehilite"><pre><span class="p">(</span><span class="nv">ggp:kill-player</span> <span class="vg">*player*</span><span class="p">)</span>
</pre></div>
</div>
<footer><p><i>Made with Lisp and love by <a href="http://stevelosh.com/">Steve Losh</a> in Reykjavík, Iceland.</i></p>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-15328874-3', 'auto');
ga('send', 'pageview');
</script></footer>
</div>
</body>
</html>