source: liacs/ai/robocom/report.tex@ 352

%
% $Id: report.tex 523 2008-03-18 11:09:00Z rick $
%

\documentclass[12pt,a4paper]{article}

\frenchspacing
\usepackage[english,dutch]{babel}
\selectlanguage{dutch}
\usepackage{graphicx}
\usepackage{url}
\usepackage{multicol}
\usepackage{fancybox}

\author{Rick van der Zwet, Universiteit Leiden}
\title{Kunstmatige Intelligentie  2008 --- opdracht 2 \\
\large{RoboCom}}
\author{Rick van der Zwet\\
  \texttt{<hvdzwet@liacs.nl>}\\
  \\
  LIACS\\
  Leiden University\\
  Niels Bohrweg 1\\
  2333 CA Leiden\\
  The Netherlands}
\date{\today}

\begin{document}

\maketitle

\section{Inleiding}

Dit verslag gaat over de tweede programmeer-opgave van het vak
kunstmatige intelligentie\cite{opdracht}. Welke als opdracht heeft om
softbots te bouwen, die tijdens een simulatie met elkaar samenwerken om
een vlag te construeren of tegen andere softbots ten strijden trekken,
met als doel als enigste over te blijven. Dit allen als doel om de
\emph{PEAS} beschrijving uit het college boek~\cite{collegeboek} beter te
kunnen begrijpen.
\section{Uitleg probleem}

\emph{RoboCom} is computerprogramma welke een simulatie omgeving bied
waarmee met assembly achtige programma code een programma wordt gemaakt
welke een software robot kan aansturen een zogenaamde \emph{softbot}.
Deze softbots kunnen simpele commando's zoals vermenigvuldigen, omgeving
afzoeken, code kopiëren en andere acties
\footnote{http://www.cyty.com/robocom/help/instr1.html}.  Al deze acties
kosten \emph{tikken}, waarbij er verschillende gradaties gemaakt worden
aan de voorwaarden te scheppen aan de aan de omgeving waar de softbots in
gaan `leven'. Buiten de verschillende gradaties in tikken kan er ook nog
onderscheidt gemaakt worden via  limitatie in de instructieset. Tijdens
deze opdracht is deze gelimiteerd tot \emph{Classic}
\footnote{http://www.cyty.com/robocom/help/instrall.html} welke de set
is waarmee het spel origineel mee ontworpen is.

Het speelbord is vierkant in representatie, maar is werkelijkheid een
bol. De onderste rij grenst aan de bovenste rij en hetzelfde geldt voor
de meest linker en meest rechtse column. Het bord heeft in totaal 256
vakjes welke allen een softbot kunnen bevallen of leeg zijn. Een softbot op
zijn beurt bestaat uit maximaal 50 \emph{banken} welke op hun beurt weer
1000 regels code kunnen bevatten.

Een softbot kan actief zijn of niet. In de actieve stand is hij bezig met
het uitvoeren van code. Waarbij begonnen wordt bij regel 1 in bank 1 en
zo verder. Als hij bij het einde van een bank komt dan springt hij terug
naar het begin (bank 1,regel 1). Als hij geen code kan vinden in bank 1
dan gaat hij dood, wat ook wel \emph{data-hunger} genoemd wordt. Tijdens
de niet actieve stand zal hij de lopende instructie stoppen en wachten
tot hij weer geactiveerd wordt. Dit kan hij zelf niet doen.


\begin{figure}[!ht]
\begin{center}
\includegraphics[scale=0.25]{speelbord}
\end{center}
\caption{
Impressie van de grafische representatie van het speelbord, elk team
krijgt een eigen kleur.  Een kruis door de softbot als deze niet actief is
(niet weergegeven). Een driehoekje geeft de richting aan in welke hij
'kijkt'. De kleur van het driehoekje geeft aan van wie de instructie
bank welke hij op het moment aan het uitvoeren is.
}
\end{figure}

Hieronder volgt een paar regels voorbeeld programma assembly code:
\begin{verbatim}
Bank Main         ; Daddy Tutorminator's program
  @Loop
  Turn 0            ; turn around, that's cool
  Create 1, 2, 1    ; build a mobile child with 2 banks
  Trans 2, 1        ; transfer RunAround into the first bank
                    ; the second bank is left empty
  Set %active, 1    ; activate our baby
  Jump @Loop        ; ...and start over
\end{verbatim}


\section{Theorie}

Over de softbots kan een PEAS beschrijving gegeven worden.
\textbf{P}restatie maat is het winnen van een simulatie. Als extra
punt zo daar eventueel aan toegevoegd kunnen worden dat dit in een zo
kort mogelijke tijd gedaan moet worden. \textbf{E}nvironment is het
speelbord en de andere softbots in het spel. \textbf{A}ctuatoren van de
softbot zijn de verschillende vragen die de softbot aan de omgeving
kan stellen. Dit zijn alle verschillende types van scannen.
\textbf{S}ensoren zijn de acties die de softbot op de omgeving kan doen.
Hieronder vallen acties als kopiëren, creëren, activeren.

De reeds beschikbare documentatie~\cite{website-help} beschrijft
uitvoering enkele theorieën die gebruikt kunnen worden de softbots te
schrijven. In het kort komt het neer op de verschillende punten waar
rekening gehouden mee moet worden. Probeer het programma zo simpel
mogelijk te houden, een heleboel regels en/of banken kosten veel tijd om
te dupliceren en/of uit te voeren waardoor je softbot kwetsbaarder is
tegen simpele programma's. Gebruik simpele programma's in het begin,
deze worden ook wel virussen genoemd, om de vijand zo veel mogelijk te
'pesten' in de ontwikkeling van zijn softbots. Maak gebruik van meerdere
type softbots en beperk je niet tot een tactiek. Ga bijvoorbeeld eerst met
een simpel virus aan de slag en gebruik daarna ingewikkelde en sterkere
softbots om het karwei af te maken.

Als laatste in dit korte rijtje, zorg dat de softbots geen hinder
ondervinden van hun eigen tactieken en let op dat de vijand dezelfde
tactiek zal gebruiken, dus wapen je ertegen.


\section{Aanpak}
Bij het maken van de vlag is gebruik gemaakt van het coöperatie element
in het spel. Tijdens het maken van de twee vecht softbots is zowel het
competitie element gebruikt als het coöperatie element.

\subsection{Vlag softbot}
Bij een vlag cruciaal is dat de softbots netjes naast elkaar komen te
lopen is dat de voornaamste uitdaging. Het uit programmeren hierna is
triviaal. Om te zorgen dat de verschillende softbots elkaar kunnen
ontmoeten wordt er gebruik maakt van het feit dat als je twee haak
op elkaar staande lijnen trekt deze altijd ergens in een enkele lijn
snijdt. Het algoritme in pseudo-code
\begin{verbatim}
while begin
    scan vakje voor de softbot
    switch begin
        case leeg vakje
            maak kloon aan
            blijf naar kloon kijken tot deze signaal doodgaan gegeven
            heeft ga dood
        case bot andere kleur
            geef signaal doodgaan aan 'staart'
            ga rechtsom
            continue
        case bot eigen kleur
            als links of recht van je een 'vijand' bot staat dan
                klaar doe niets meer
            anders
            ga rechtsom
            continue
    end
end
\end{verbatim}

\subsection{Defensieve softbot}
Bij het schrijven van de eerste vechtende softbot is gekozen voor een
defensieve tactiek, met een soort van drie meertrapsraket methode. Als eerste
komt er een zeer simpel schild om moederbot heen welke een verlammend
verspreidend virus infecteert aan alle softbots die in de buurt komen. Na
een zekere tijd wordt er een nog simpeler virus geïnjecteerd dat alle
softbots vermoord. Hierna worden ingewikkelder softbots gemaakt genaamd
slopers welke het bord opruimen. Voordeel hierbij is dat simpele
virussen geen vat op deze softbots hebben, want de moederbot is geschreven
om hier immuun voor te zijn. Nadeel is echter dat er geen tot weinig
ontwikkeling plaatsvind in de softbots, waardoor in de laatste fase van
het spel misschien te weinig softbots dood gaan om te zorgen dat rustig de
slopers gemaakt kunnen worden.


\subsection{Offensieve softbot}
De aanvallende softbot heeft een heel andere tactiek. Deze maakt gelijk
ingewikkende softbots. Deze ingewikkende softbots infecteren de vijand met
een simpel virus en laten dit even verspreiden. Nadien vernietigd hij
deze softbot en maakt hij een kloon van zichzelf aan. Deze tactiek zorgt
ervoor dat de softbots niet vatbaar zijn voor de simpele virussen, maar
heeft als nadeel dat de softbots veel meer tijd kosten om te bouwen en dan
kwetsbaarder kunnen zijn.




\section{Implementatie}

Er is gekozen om geen gebruik te maken voorbeeld implementaties van
andere softbots in de eigen code. De voorbeelden in de handleidingen
zijn wel overgenomen. De softbot code is in de RoboCom taal geschreven.

\section{Experimenten}
Alle testen zijn uitgevoerd met het programma RoboCom Workshop
v3.10\cite{website-programma} gedraaid op een Microsoft Windows XP
computer. Gebruikt instructie set is Classic.

\subsection{Vlag}
Tijdens het testen van het succesvol vormen van de vlag is gebruik
gemaakt van 2 type simulaties. Als eerste is 20 keer de softbots op
willekeurige plekken neergezet en gekeken of er een vlag uitkomt. Als
tweede zijn de softbots 20 keer op elke keer dezelfde plek gezet en
gekeken of deze dezelfde vlag vormen.De resultaten zijn te vinden in
tabel~\ref{tab:vlag}

\begin{center}
\begin{table}[h]
\caption{Resultaten plaatsingen van vlag, bij goed staat de vlag of
horizontaal, bij matig verticaal, bij fout is erna 80000 tikken nog geen
uitslag. De vaste plaatsing is op posities (X,Y,richting) $8,10,2$,
$14,14,0$, $3,9,1$ }
\begin{tabular}{l|r|r|r}
Type                   & Goed & Matig & Fout \\
\hline
Willekeurige plaatsing &  9   &  9    & 2  \\
Vaste plaatsing        &  4   &  12   & 4  \\
\end{tabular}
\label{tab:vlag}
\end{table}
\end{center}

\subsection{Vechters}
Door het programma RoboCom wordt een set softbots meegeleverd die gelabeld
zijn als `classic legends'. De twee softbots hebben in een tegen een
gevechten tegen al deze classic legends gespeeld. Elke een tegen een
gevecht is 20 keer uitgevoerd.  De resultaten staan hieronder in de
tabel~\ref{tab:defensive} voor de defensieve softbot.
Tabel~\ref{tab:offensive} levert de resultaten voor de offensieve
softbot.

\begin{center}
\begin{table}[h]
\caption{Resulaten defensieve softbot na 80000 tikken, bij score telt een
gelijkspel voor 1 punt en winst voor 3 punten en verlies niets.  }
\begin{tabular}{l|r|r|r|r}
Tegenstander & Winst & Verlies & Gelijkspel & Score\\
\hline
(Cy)Borg 004c83a8n           &  3 & 0 & 7  & 16\\
Advanced Speedix 2004        &  2 & 1 & 7  & 13\\
Africa                       &  2 & 0 & 8  & 14\\
Alien v5.13d                 &  1 & 0 & 9  & 12\\
Bright Star Three            &  0 & 5 & 5  & 5\\
Comes the Wuss 2             & 10 & 0 & 0  & 30\\
CopyBot                      &  1 & 1 & 8  & 11\\
Delusion 5                   & 10 & 0 & 0  & 30\\
DJ Combat - Deep Strike      & 10 & 0 & 0  & 30\\
DJ CoNTiNUuM                 &  0 & 2 & 8  & 8\\
Fungus 0.2a                  &  0 & 0 & 10 & 10\\
HotBot V2                    & 10 & 0 & 0  & 30\\
Hurricane6                   & 10 & 0 & 0  & 30\\
Immer mit der Ruhe! XXXVI    &  9 & 0 & 1  & 28\\
Jörg's Bisexa                &  0 & 0 & 10 & 10\\
Kreuziger V2.03q anti Killer & 10 & 0 & 0  & 30\\
Malignant Tumor              &  0 & 1 & 9  & 9\\
Outer Limits                 & 10 & 0 & 0  & 30\\
Speed Slug                   &  7 & 0 & 3  & 24\\
SpiceGirls                   & 10 & 0 & 0  & 30\\
Spy vs. Spy                  &  0 & 7 & 3  & 3\\
\hline
fighter-defensive-1          &17 &105 & 88 & 139
\end{tabular}
\label{tab:defensive}
\end{table}
\end{center}

\begin{center}
\begin{table}[h]
\caption{Resulaten offensieve softbot na 80000 tikken, bij score telt een
gelijkspel voor 1 punt en winst voor 3 punten en verlies niets.  }
\begin{tabular}{l|r|r|r|r}
Tegenstander & Winst & Verlies & Gelijkspel & Score\\
\hline
(Cy)Borg 004c83a8n           & 10 & 0 & 0  & 30\\
Advanced Speedix 2004        & 10 & 0 & 0  & 30\\
Africa                       &  4 & 0 & 6  & 18\\
Alien v5.13d                 &  8 & 1 & 1  & 25\\
Bright Star Three            &  4 & 3 & 3  & 15\\
Comes the Wuss 2             &  4 & 5 & 1  & 13\\
CopyBot                      &  9 & 1 & 0  & 27\\
Delusion 5                   &  7 & 1 & 2  & 23\\
DJ Combat - Deep Strike      & 10 & 0 & 0  & 30\\
DJ CoNTiNUuM                 &  3 & 4 & 3  & 12\\
Fungus 0.2a                  &  0 & 1 & 9  &  9\\
HotBot V2                    &  0 & 0 & 10 & 10\\
Hurricane6                   & 10 & 0 & 0  & 30\\
Immer mit der Ruhe! XXXVI    & 10 & 0 & 0  & 30\\
Jorg's Bisexa x              &  0 &10 & 0  & 0 \\
Kreuziger V2.03q anti Killer & 10 & 0 & 0  & 30\\
Malignant Tumor              &  3 & 7 & 0  & 9\\
Outer Limits                 & 10 & 0 & 0  & 30\\
Speed Slug                   &  9 & 0 & 1  & 28\\
SpiceGirls                   & 10 & 0 & 0  & 30\\
Spy vs. Spy                  &  1 & 0 & 9  & 12\\
\hline
fighter-offensive-2          &33 &132 & 45 & 144
\end{tabular}
\label{tab:offensive}
\end{table}
\end{center}

\section{Conclusie}
\subsection{Vlag}
Bij het willikeurig neerzetten van de softbots gaan er slechts 2
gevallen fout, nader onderzoek blijkt uit dat er een fout in de code is
geslopen waardoor situaties waarbij een volledig `kruis' gemaakt word door
een enkele softbot niet afgevangen word. Waardoor deze in een deadloop
beland.
Een vaste uitgangspositie levert echter heel vreemde resultaten op. De
verwachting was dat er altijd dezelfde situatie uit zal komen, dit is
echter totaal niet het geval, 4 gevallen worden zelfs niet opgelost. De
oorzaak hiervan ligt niet in de softbots, maar in de implementatie van het
programma. Het aantal softbots lijkt niet te kloppen en nader analyse
blijkt dat er 'spook softbots' op  het bord staan. Verder zijn de
grensgevallen niet bekend. Zoals wat er bijvoorbeeld gebeurt op het
moment dat 2 softbots op precies hetzelfde moment een instructie op de
softbot plaatsen. Er lijkt willekeurig een keuze gedaan te worden,
waardoor het spelverloop ernstig verstoord kan worden.

Voor verder onderzoek is het aan te raden contact op te nemen met de
ontwikkelaars om de fouten uit de simulatie te halen en dan de kijken
hoe het geval van het `kruis' opgelost kan worden.


\subsection{Vechters}
Beide vechtende softbots hebben ongeveer dezelfde score, maar halen wel op
verschillende gebieden hun punten binnen. De defensieve weet er in 41\%
van de gevallen gelijkspel uit te slepen en is in 9\% zelfs winnend,
waarbij dus voor 50\% van de gevallen de softbot goed presteert. Hij
presteer slecht tegen softbots die gebruik maken van verschillende
tactieken en meer effectieve opruim methodes hebben.

De offensieve is effectief in het opruimen tegen verschillende type
softbots waarbij de defensieve nog met een gelijkspel genoegen moet nemen,
maar houdt het een stuk minder uit tegen de `grote jongens'.

Voor verder onderzoek zou gekeken moeten worden of een combinatie van de
vechters een goede opstelling is. Een analyse van alle verschillende
tactieken van de tegenstanders zou ook aan te raden zijn. Door een softbot
zo veel mogelijk te storen in zijn ontwikkeling is de beste methode
omdat niet veel softbot bouwers rekening hebben gehouden met bijvoorbeeld
een situatie waar alle softbots niet meer in controle zijn van de bouwer.

\begin{thebibliography}{XX}

\bibitem{opdracht}
W.A.~Kosters, Kunstmatige intelligentie Programmeer-opgave 2 van 2008
-- Bridge, \url{http://www.liacs.nl/~kosters/AI/robot.html}

\bibitem{collegeboek}
S.J. Russell en P. Norvig, Artificial Intelligence, A Modern Approach,
Second ediion, Prentice Hall, 2003.

\bibitem{website}
Robocom, official website, latest version
\url{http://cyty.com/robocom/}

\bibitem{website-help}
Robocom help, official website, latest version
\url{http://www.cyty.com/robocom/?area=help}

\bibitem{website-programma}
Robocom Workshop, official website, latest version
\url{http://www.cyty.com/robocom/?area=d\_rcws}

\end{thebibliography}

\section*{Appendix}
De obot programma's zagen er als volgt uit:
\tiny
\advance\textwidth by 8cm
\advance\oddsidemargin by -3cm
\advance\evensidemargin by -3cm
\advance\topmargin by -2cm
\advance\textheight by 2cm
\advance\footskip by -2cm
\marginparwidth 0cm
\twocolumn
%c++ input preformatted with `source-highlight -n -f latex bridge.cc`
\include{figure-flag-v2.rob}
\include{fighter-defensive-1.rob}
\include{fighter-offensive-2.rob}
\onecolumn

\end{document}