Regles del joc

• Quatre equips, cadascun controlat per un programa, s'enfronten sobre un tauler quadrat simètric amb $60\times 60$ caselles. L'objectiu del joc és conquerir el màxim nombre de punts de control (per brevetat, en direm posts), dels quals n'hi ha 16 repartits pel tauler.

• Cada casella del tauler està identificada per un parell $(x,y)$, on $0 \leq x, y < 60$. A diferència de l'habitual, l'eix de les $X$ va de nord a sud, i el de les $Y$ d'oest a est.

• Cada equip comença en un quadrant del tauler: els equips 1, 2, 3 i 4 inicialment es troben al quadrant nord-oest, nord-est, sud-est i sud-oest, respectivament.

• Hi ha tres tipus d'efectius: soldats, helicòpters i paracaigudistes. (De fet, un paracaigudista només és la possibilitat de llançar un nou soldat, que encara no existeix, des d'un helicòpter. Per tant, els paracaigudistes no existeixen mai com a tals.) En començar la partida, cada equip té 20 soldats, 2 helicòpters i 0 paracaigudistes. Els soldats comencen en el seu quadrant, distribuïts aleatòriament, però de forma simètrica per cada equip. Els helicòpters de l'equip 1 comencen mirant cap a l'est i cap al sud, respectivament. Els helicòpters dels altres equips estan orientats simètricament.

• Hi ha quatre tipus de terreny: bosc, gespa, aigua i muntanya. Tot el perímetre del tauler està envoltat de muntanya. Els soldats només poden passar pel bosc o per la gespa. Els helicòpters poden passar sobre qualsevol terreny que no sigui muntanya (cal suposar que són muntanyes massa altes). Inicialment, el terreny en què es troben els soldats i els helicòpters és consistent amb aquestes regles. Els soldats i els helicòpters es mouen en plans (alçades) diferents, i per tant no s'interfereixen mai.

• Una partida dura 200 torns. A cada torn, els quatre programes donen instruccions als seus efectius. Si un soldat o helicòpter rep més d'una instrucció durant un torn, només se n'intenta executar la primera.

• Al final de cada torn s'executen totes les instruccions de tots els equips, en l'ordre següent: primer les dels paracaigudistes, a continuació les dels helicòpters, i finalment les dels soldats. Dins de cadascun d'aquests tres grups, les instruccions s'executen en ordre aleatori, sense donar prioritat a cap dels equips.

• Un soldat no es mou en un torn si no rep cap instrucció, si el lloc al que hauria de moure's no està permès (hi ha aigua o muntanya), o si en el moment d'intentar executar la instrucció, un altre soldat (propi o enemic) ocupa el lloc al qual vol anar.

• Similarment, un helicòpter no es mou en un torn si no rep cap instrucció, si el lloc al que hauria de moure's no està permès (hi ha muntanya), o si en el moment d'intentar executar la instrucció, un altre helicòpter (propi o enemic) ocupa el lloc al qual vol anar.

• Els soldats ocupen una sola casella. Cada soldat pot intentar moure's a una de les caselles adjacents, ja sigui horitzontalment, verticalment, o en diagonal. Si la casella a la què intenta moure's està ocupada per un soldat enemic, l'enemic rep una dany aleatori depenent del terreny sobre el qual es trobi: entre 20 i 40 punts si està en un bosc (i per tant, està relativament protegit), i entre 50 i 100 punts si està sobre la gespa (i per tant, està relativament desamparat). Cada soldat té 100 punts de vida inicialment. Quan els perd tots, el soldat mor. Els soldats del mateix equip no s'ataquen mai entre si.

• Els helicòpters ocupen un quadrat de $5 \times 5$ caselles del cel. A cada torn, cada helicòpter pot intentar moure's una o dues caselles endavant (és a dir, en la direcció i sentit en què està orientat). Si alguna de les 5 (o 10) caselles noves a les quals hauria de moure's està ocupada per un altre helicòpter, o si alguna és una muntanya, l'helicòpter no es mou (o es mou només un dels dos passos, si el primer pas és possible però el segon no). Els helicòpters no s'ataquen entre si, ni poden rebre cap dany de cap mena. Per tant, cada equip té 2 helicòpters durant tota la partida.

• Els helicòpters també poden moure's 90 graus en el sentit de les agulles del rellotge, moure's 90 graus en el sentit contrari, o llançar napalm. Els girs sempre són vàlids. En canvi, només es pot llançar napalm si aquest està disponible: cada helicòpter ha d'esperar un mínim de 30 torns des del seu últim llançament de napalm (o des de l'inici de la partida).

• Quan un helicòpter llança napalm, el quadrat $5 \times 5$ de terreny no muntanyós centrat sota seu és arrasat pel foc, i tots els soldats que hi siguin, propis o enemics, moren. A més, el foc es manté durant 5 torns sobre la gespa i l'aigua, i 10 torns sobre el bosc. Després d'haver cremat, un bosc es converteix en gespa.

• Al final de cada torn, el foc es propaga segons la regla següent: tota casella amb bosc i sense foc que sigui horitzontalment o verticalment veïna d'una o més caselles amb foc, té una probabilitat d'un 10 per cent de començar a cremar. Si és així, el foc hi dura 10 torns (com a mínim: quan es llança napalm sobre una casella que ja té foc, el comptador de durada del foc es torna a posar al màxim).

• Un soldat mor si es mou a una casella de gespa o de bosc amb foc, o si es troba sobre una casella de bosc sobre la qual es propaga el foc.

• Cada soldat o helicòpter té un enter estrictament positiu que l'identifica de manera única. Quan un soldat mor, aquest desapareix (identificador inclòs), i apareix un nou paracaigudista d'un altre equip (segons s'explica més a baix), el qual es podrà transformar en soldat. Així doncs, la suma de soldats i paracaigudistes durant tota la partida és sempre 80.

• Cada helicòpter disposa d'un cert nombre de paracaigudistes. Cadascun d'aquests permet fer aparèixer un soldat sa i amb identificador nou a sota del respectiu helicòpter. Encara que un equip disposi de molts paracaigudistes, a cada torn en pot llançar un màxim de 4. A més, els paracaigudistes tenen data de caducitat: un paracaigudista no usat durant 20 torns mor. Addicionalment, un paracaigudista que s'intenta llançar sobre una casella no coberta pel quadrat $5 \times 5$ corresponent a l'helicòpter corresponent, o sobre una casella amb aigua, o amb foc, o amb un soldat (propi o enemic) també mor.

• Quan es mata un soldat enemic, ja sigui atacant-lo amb un soldat propi o llançant-li napalm, l'equip atacant guanya un nou paracaigudista.

• Qualsevol soldat que mori per entrar al foc, o per la propagació del foc, o pel napalm llançat pel propi equip, passa a ser paracaigudista d'un dels altres tres equips, escollit uniformement a l'atzar.

• Els paracaigudistes caducats o morts durant el llançament també passen a ser paracaigudistes d'un altre equip. El nou equip s'escull sempre a l'atzar, amb una excepció: si es llança un paracaigudista sobre un soldat enemic, el nou paracaigudista s'incorpora a aquest equip enemic.

• Quan un nou paracaigudista s'incorpora a un equip, l'helicòpter al qual és assignat es determina aleatòriament.

• Quan un soldat es posa sobre un post, o quan un paracaigudista hi cau a sobre (si el post no té cap soldat), el post és conquerit. Els posts poden ser conquerits i reconquerits per diversos equips tantes vegades com es vulgui. Inicialment, els posts no són de cap equip.

• Segons la seva importància estratègica, els posts tenen molt valor (4000 punts) o poc valor (1000 punts). A cada quadrant hi ha 2 posts de 4000 punts, i 2 altres de 1000 punts. La puntuació d'un equip en un torn es calcula de la forma següent: cada post que l'equip controla al final del torn dóna tants punts com el seu valor, i cada soldat (no paracaigudista) de l'equip dóna 1 punt.

Programació

Al problema d'Apocalyse Now Redux del Jutge, juntament a aquest enunciat, hi trobareu el material necessari per programar el joc en C++. En concret, hi teniu tots els fitxers de suport, exemples de jugadors, i un visor de partides amb els quals podreu desenvolupar i provar els vostres jugadors.

Necessitareu g++, make i un navegador recent (Firefox, Chrome, Chromium, preferiblement un d'aquests dos últims). El codi del joc és portable a qualsevol sistema Linux, Mac o Windows, suposant que hi instal·leu les eines adequades. Els ordinadors de la FIB i de la FME ja tenen aquest software instal·lat. Si voleu treballar amb altres màquines:

• Amb Debian o Ubuntu, amb una instrucció del tipus

  sudo apt-get install build-essential chromium-browser

  tindreu tot el que us cal.

• Amb Mac, en tindreu prou amb instal·lar XCode des de l'App Store.

• Amb Windows, serà suficient instal·lar MinGW (http://mingw.org).

Com fer un jugador

Per fer un jugador, copieu primer el fitxer AINull.cc a un fitxer AIXXX.cc, on XXX és un identificador de la vostra elecció. Trieu un identificador no ofensiu, que no hagi estat triat ja per un altre estudiant, i compost per, com a molt, 12 lletres, dígits i caràcters de subratllat; per exemple, Terminator.

A continuació, al fitxer AITerminator.cc (o com l'hagueu anomenat) que acabeu de crear, heu de canviar la línia 11 per posar-hi el nom del vostre jugador (a l'exemple, @#define PLAYER_NAME Terminator@).

Finalment, heu d'implementar el vostre jugador tot completant la classe PLAYER_NAME que hereta les operacions de consulta del tauler (classe @Board@) i de creació d'accions (classe @Action@) a través de la classe base @Player@. El mètode @play()@ es crida a cada ronda per transmetre-us l'estat actual del tauler i recollir les accions del vostre jugador. A la vostra classe hi podeu afegir camps (variables) per recordar l'estat d'una ronda a l'altra, mètodes (funcions) per descompondre el vostre programa, etc.

Fixeu-vos que la vostra classe ha de contenir una funció anomenada @factory()@ que no heu de modificar, i que després de la classe també hi ha una crida per registrar el vostre jugador, que tampoc heu de modificar.

Podeu prendre com a referència el jugador AIDemo.cc que s'adjunta amb el material de la pràctica.

Com executar i veure partides localment

1. Executeu make per compilar tots els fitxers que calguin i crear l'executable Game.

2. Per disputar una partida amb els paràmetres de joc default.cnf, executeu una comanda com ara

   ::: center ./Game Null Terminator Demo Demo < default.cnf > default.res :::

   Aquí, el primer jugador serà Null, el segon Terminator, i els altres dos Demo. El resultat de la partida quedarà a default.res.

3. Visualitzeu la partida obrint el visor (viewer.html) amb el vostre navegador i carregueu el fitxer default.res. A part de la barra de desplaçament i dels botons que hi apareixen a sobre, algunes altres tecles també permeten controlar la reproducció de la partida; pitgeu h durant la visualització per obrir una finestra d'ajuda autoexplicativa.

Podeu obtenir la llista completa de paràmetres del programa Game fent ./Game --help. En particular, ./Game --list us llistarà els noms dels jugadors inclosos.

Si us cal, podeu netejar el vostre directori de fitxers executables i fitxers objectes amb la comanda make clean.

Restriccions

Els codis dels vostres jugadors han de complir certes limitacions:

• Tot el codi s'ha de trobar en un sol fitxer i ha de seguir les indicacions donades.

• No podeu fer servir variables globals (utilitzeu camps de la vostra classe PLAYER_NAME).

• Només podeu usar llibreries estàndard de C++: vector, map, etc.

• No podeu obrir fitxers, ni fer altres crides al sistema operatiu (systems, forks, etc.).

• Si us cal, podeu utilitzar @cerr@, però no @cin@ ni @cout@. Compte, escriure missatges consumeix temps!

• En execució local, no es controla que els jugadors avortin, que triguin massa, o que interfereixin amb els contraris. Al Jutge, sí. Tingueu en compte que si un programa esgota el temps permès de càlcul (aprox. 3 segons per a tota la partida), el seu jugador queda congelat: no queda eliminat i pot fins i tot guanyar la partida, però ja no pot executar cap més ordre.

Estructures de dades

Per saber com consultar el tauler, feu un cop d'ull al fitxer @Board.hh@ (en particular, pareu atenció a les operacions públiques de la classe @Board@). Per saber com sol·licitar les accions, mireu el fitxer @Player.hh@ (en particular, fixeu-vos en les operacions públiques de la classe @Player@). Fixeu-vos que només podeu utilitzar les operacions públiques d'aquestes classes.

Sempre que es crida un mètode amb paràmetres incorrectes s'escriurà un missatge d'error per la consola. Cridar mètodes amb paràmetres incorrectes no provocarà mai que el vostre programa es pengi, però tingueu en compte que el pot fer anar bastant més lent, degut a l'escriptura dels missatges.

Consells

• Comenceu amb estratègies molt senzilles, que siguin fàcils de programar i de depurar, que és exactament allò que necessiteu al principi.

• Programeu procediments senzills i útils (del tipus "soldat enemic/propi més proper", etc.), i assegureu-vos que funcionin correctament.

• No us arrisqueu a ser eliminats abans de començar. Aconseguiu que el web us accepti un jugador tan ràpidament com us sigui possible. Un jugador acceptat representa tenir assegurada part de la nota de la pràctica!

• Conserveu diverses versions antigues (però que funcionin correctament) dels vostres jugadors, i no les toqueu per res.

• Compileu sovint, testegeu sovint. És molt més fàcil trobar i corregir els errors quan s'han canviat unes poques línies de codi que quan s'acumulen molts canvis de cop.

• Feu servir cerrs per posar xivatos, i asserts per comprovar que el codi fa el que toca. Però comenteu els cerrs abans d'enviar el jugador al web, ja que alenteixen els programes.

• Podeu analitzar els fitxers que el programa Game genera com a sortida, que descriuen com evoluciona el tauler a cada ronda.

• Per testejar un jugador nou, enfronteu-lo contra uns altres tres jugadors que no treguin cap missatge. Així només apareixeran per pantalla els missatges del nou jugador.

• No us arrisqueu a quedar eliminats per culpa d'un jugador massa lent. Doneu-vos un bon marge de seguretat. En particular, eviteu tant com pugueu l'escriptura de missatges.

• Feu competir els vostres jugadors contra rivals diferents, i estudieu les partides. Encara que no podreu veure els codis dels altres estudiants, si sou capaços de deduir les seves tàctiques i us semblen útils, podeu mirar d'imitar-les, defensar-vos-en o millorar-les.

• No deixeu el vostre codi a ningú, ni tan sols d'una versió antiga. Un cop feta la competició s'analitzaran els programes de cada ronda amb programes detectors de plagi (JPlag, per exemple).

• Per evitar disgustos, feu servir el web d'Apocalypse Now per jugar partides amb els vostres amics. Però no confieu massa en els vostres amics...

• Tingueu en compte que podeu lliurar nous jugadors en qualsevol moment (excepte durant la fase final).

• Insistim: Feu codis senzills. Compileu sovint, testegeu sovint. O afronteu-ne les conseqüències.