% % $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{}\\ \\ 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}