| author |
Steve Losh <steve@stevelosh.com> |
| date |
Thu, 07 Mar 2019 12:47:45 -0500 |
| parents |
de3a1abe8e1c |
| children |
9c5ba7f7046a |
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8"/>
<title>Overview / cl-ggp</title>
<link rel="stylesheet" href="../_dmedia/pygments-clean.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>This document assumes you know what <a href="http://ggp.org/">General Game Playing</a> is, what <a href="https://en.wikipedia.org/wiki/Game_Description_Language">GDL</a>
is, and how the GGP community/competitions/etc work.</p>
<div class="toc">
<ul>
<li><a href="#ggp-protocol">GGP Protocol</a><ul>
<li><a href="#basics">Basics</a></li>
<li><a href="#game-functionality">Game 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>
</ul>
</li>
<li><a href="#reasoning">Reasoning</a></li>
<li><a href="#example-player">Example Player</a></li>
</ul></div>
<h2 id="ggp-protocol">GGP Protocol</h2>
<p>The <code>cl-ggp</code> system handles the GGP network protocol and game flow for you.
Players are implemented as CLOS objects.</p>
<h3 id="basics">Basics</h3>
<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/><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>
<h3 id="game-functionality">Game Functionality</h3>
<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>
<h4 id="player-start-game">player-start-game</h4>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp: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>
<h4 id="player-update-game">player-update-game</h4>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp: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>
<h4 id="player-select-move">player-select-move</h4>
<div class="codehilite"><pre><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">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>
<h4 id="player-stop-game">player-stop-game</h4>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp: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>
<h3 id="timeouts">Timeouts</h3>
<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>
<h3 id="symbols">Symbols</h3>
<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><span/>(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
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="reasoning">Reasoning</h2>
<p>The <code>cl-ggp.reasoner</code> system contains a Prolog-based GDL reasoner based on the
<a href="https://sjl.bitbucket.io/temperance/">Temperance</a> logic programming library.</p>
<p>It's useful as a starting point if you just want to get a bot up and running
quickly. If you want more speed or control over the reasoning process you'll
probably want to replace it with your own implementation.</p>
<p>You can make a reasoner for a set of GDL rules (e.g. the rules given to you by
<code>player-start-game</code>) with <code>(make-reasoner rules)</code>.</p>
<p>Once you've got a reasoner you can ask it for the initial state of the game with
<code>(initial-state reasoner)</code>. This will give you back a state object — it's
currently just a list, but this may change in the future, so you should just
treat it as an opaque object.</p>
<p>Once you've got a state and a set of moves you can compute the next state with
<code>(next-state reasoner current-state moves)</code>.</p>
<p>States can be queried for their terminality, goal values, and legal moves with
<code>terminalp</code>, <code>goal-values-for</code>, and <code>legal-moves-for</code> respectively.</p>
<p>See the <a href="../reference-reasoner/">Reasoner API Reference</a> for more details.</p>
<h2 id="example-player">Example Player</h2>
<p>Let's create a small example player that uses the reasoner to play any GGP game
legally. We'll start by creating a class for the player, with three slots to
keep track of the data we need to play a game:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defclass</span> <span class="nv">random-player</span> <span class="p">(</span><span class="nv">ggp:ggp-player</span><span class="p">)</span>
<span class="p">((</span><span class="nv">role</span> <span class="ss">:accessor</span> <span class="nv">p-role</span><span class="p">)</span>
<span class="p">(</span><span class="nv">current-state</span> <span class="ss">:accessor</span> <span class="nv">p-current-state</span><span class="p">)</span>
<span class="p">(</span><span class="nv">reasoner</span> <span class="ss">:accessor</span> <span class="nv">p-reasoner</span><span class="p">)))</span>
</pre></div>
<p>Now we can implement <code>player-start-game</code>. We'll store the role we've been
assigned, and create a reasoner so we can compute our legal moves later. We'll
ignore the deadline because we're not doing any extensive processing:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp:player-start-game</span>
<span class="p">((</span><span class="nv">player</span> <span class="nv">random-player</span><span class="p">)</span> <span class="nv">rules</span> <span class="nv">role</span> <span class="nv">deadline</span><span class="p">)</span>
<span class="p">(</span><span class="k">declare</span> <span class="p">(</span><span class="k">ignore</span> <span class="nv">deadline</span><span class="p">))</span>
<span class="p">(</span><span class="nb">setf</span> <span class="p">(</span><span class="nv">p-role</span> <span class="nv">player</span><span class="p">)</span> <span class="nv">role</span>
<span class="p">(</span><span class="nv">p-reasoner</span> <span class="nv">player</span><span class="p">)</span> <span class="p">(</span><span class="nv">ggp.reasoner:make-reasoner</span> <span class="nv">rules</span><span class="p">)))</span>
</pre></div>
<p>Next we'll implement <code>player-update-game</code>, which will compute the current state
of the game and store it in the <code>current-state</code> slot:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp:player-update-game</span>
<span class="p">((</span><span class="nv">player</span> <span class="nv">random-player</span><span class="p">)</span> <span class="nv">moves</span><span class="p">)</span>
<span class="p">(</span><span class="nb">setf</span> <span class="p">(</span><span class="nv">p-current-state</span> <span class="nv">player</span><span class="p">)</span>
<span class="p">(</span><span class="k">if</span> <span class="p">(</span><span class="nb">null</span> <span class="nv">moves</span><span class="p">)</span>
<span class="p">(</span><span class="nv">ggp.reasoner:initial-state</span> <span class="p">(</span><span class="nv">p-reasoner</span> <span class="nv">player</span><span class="p">))</span>
<span class="p">(</span><span class="nv">ggp.reasoner:next-state</span> <span class="p">(</span><span class="nv">p-reasoner</span> <span class="nv">player</span><span class="p">)</span>
<span class="p">(</span><span class="nv">p-current-state</span> <span class="nv">player</span><span class="p">)</span>
<span class="nv">moves</span><span class="p">))))</span>
</pre></div>
<p>If <code>moves</code> is null we ask the reasoner for the initial state, otherwise we
compute the next state from the current one and the moves that were made.</p>
<p>Now we can implement <code>player-select-move</code>. We'll just ask the reasoner for all
our legal moves and choose one at random. If we wanted to make a smarter
player, this is where we would search the game tree to find a good move:</p>
<div class="codehilite"><pre><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">random-player</span><span class="p">)</span> <span class="nv">deadline</span><span class="p">)</span>
<span class="p">(</span><span class="k">declare</span> <span class="p">(</span><span class="k">ignore</span> <span class="nv">deadline</span><span class="p">))</span>
<span class="p">(</span><span class="k">let</span> <span class="p">((</span><span class="nv">moves</span> <span class="p">(</span><span class="nv">ggp.reasoner:legal-moves-for</span>
<span class="p">(</span><span class="nv">p-reasoner</span> <span class="nv">player</span><span class="p">)</span>
<span class="p">(</span><span class="nv">p-current-state</span> <span class="nv">player</span><span class="p">)</span>
<span class="p">(</span><span class="nv">p-role</span> <span class="nv">player</span><span class="p">))))</span>
<span class="p">(</span><span class="nb">nth</span> <span class="p">(</span><span class="nb">random</span> <span class="p">(</span><span class="nb">length</span> <span class="nv">moves</span><span class="p">))</span> <span class="nv">moves</span><span class="p">)))</span>
</pre></div>
<p>Finally we can implement <code>player-stop-game</code>. We'll just clear out the player's
slots so the data can be garbage collected:</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defmethod</span> <span class="nv">ggp:player-stop-game</span>
<span class="p">((</span><span class="nv">player</span> <span class="nv">random-player</span><span class="p">))</span>
<span class="p">(</span><span class="nb">setf</span> <span class="p">(</span><span class="nv">p-current-state</span> <span class="nv">player</span><span class="p">)</span> <span class="no">nil</span>
<span class="p">(</span><span class="nv">p-reasoner</span> <span class="nv">player</span><span class="p">)</span> <span class="no">nil</span>
<span class="p">(</span><span class="nv">p-role</span> <span class="nv">player</span><span class="p">)</span> <span class="no">nil</span><span class="p">))</span>
</pre></div>
<p>Now we can make an instance of our player and start it up!</p>
<div class="codehilite"><pre><span/><span class="p">(</span><span class="nb">defvar</span> <span class="vg">*random-player*</span>
<span class="p">(</span><span class="nb">make-instance</span> <span class="ss">'random-player</span>
<span class="ss">:name</span> <span class="s">"RandomPlayer"</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">*random-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>