[image]

Regles del Joc

Després de massa anys competint només en Quidditch, l’escola de
bruixeria de Hogwarts, amb el professor Dumbledore al capdavant,
organitza la competició definitiva per determinar quina de les seves
quatre cases (Gryffindor, Ravenclaw, Slytherin o Hufflepuff) és la més
poderosa. Cada casa, també anomenada clan, disposa d’una sèrie
d’aprenents de mag i d’un fantasma, que competiran dins els passadissos
de Hogwarts per tal d’aconseguir la més prestigiosa de totes les
victòries. No obstant, Voldemort està atent i no perdrà l’oportunitat de
participar a la competició.

Es tracta d’un joc per a quatre jugadors, identificats amb números de 0
a 3. Cada jugador té el control d’una sèrie de mags i d’un fantasma.

El joc té una durada de 200 rondes, numerades de la 0 la 199. Cada
unitat, ja sigui mag o fantasma, pot moure’s com a màxim una vegada per
ronda. Els fantasmes, addicionalment, també tenen la possibilitat
d’efectuar un encanteri. Durant aquestes rondes les cases aniran
acumulant punts i guanyarà la partida qui tingui més punts en acabar
l’última ronda.

Voldemort també es mou una vegada per ronda però cap jugador pot
controlar-lo. Qualsevol mag o fantasma que entri en una de les 8
caselles adjacents a la posició de Voldemort serà atacat per ell. Els
moviments de Voldemort no seran arbitraris, sinó que tindran per
objectiu eliminar el nombre màxim d’unitats.

El tauler del joc té dimensions 60 × 60. Les unitats no es poden moure
en cap cas fora d’ell. Una posició del tauler ve determinada per un
parell d’enters (f, c) on 0 ≤ f < 60 i 0 ≤ c < 60. La posició de més a
dalt i a l’esquerra és la (0, 0), mentre que la de més a baix i a la
dreta és (59, 59). Per tant, la primera coordenada (f de fila) és la que
indica la posició en l’eix vertical i la segona (c de columna) en l’eix
horitzontal. Cada cel·la del tauler o bé forma part d’un passadís o bé
és una paret. Les unitats no poden en cap cas travessar les parets i
s’han de moure necessàriament pels passadissos.

Les cases comencen la partida amb una certa quantitat de punts de força.
La força de màgia d’un clan es defineix com
$\left\lfloor{{\texttt{punts força}}\over{\texttt{unitats del
      clan}}}\right\rfloor$ i serà clau per determinar el guanyador de
les lluites que hi haurà durant la partida. Per tal d’incrementar els
punts de màgia, les unitats poden llegir llibres de bruixeria que
trobaran al tauler. És fàcil veure que un clan amb moltes unitats
necessita llegir molts llibres per a poder mantenir una força
considerable.

Moviments dels fantasmes. Un fantasma es pot moure pel tauler de la
manera següent:

- Pot accedir a qualsevol de les 8 cel·les adjacents en horitzontal,
  vertical i diagonal.

- Si es mou cap a una cel·la on hi ha una paret, el moviment s’ignorarà.

- Si es mou cap a una cel·la ocupada per un llibre, els punts de força
  del seu clan s’incrementaran, el fantasma ocuparà la cel·la tot fent
  desaparèixer el llibre i el seu clan posseirà aquesta cel·la. En
  acabar la ronda, un altre llibre reapareixerà en una altra posició.
  Notem que no trobarem mai una cel·la ocupada per un llibre i un mag o
  fantasma.

- Si es mou cap a una cel·la buida (sense llibre ni cap unitat), el
  moviment s’efectuarà i el seu clan passarà a posseir aquesta cel·la.

- Si es mou cap a una cel·la ocupada per una unitat, ja sigui mag o
  fantasma, el moviment s’ignorarà.

- Si es mou cap a una de les 8 cel·les adjacents a Voldemort, es veurà
  atacat per ell. El resultat de l’atac el detallarem quan expliquem com
  es mou Voldemort.

Encanteris fets pels fantasmes. A part de moure’s, els fantasmes poden
intentar realitzar potents encanteris. A cada ronda, Dumbledore genera
una seqüència d’ingredients (nombres naturals) per l’encanteri.
L’objectiu és agrupar els ingredients en grups de 3 de manera que cada
grup sumi la mateixa quantitat. Per exemple, si els ingredients venen
donats pel vector:

   1   4   5   6   4   1   3   4   2     
  --- --- --- --- --- --- --- --- --- -- --

una solució és la següent:

   1   2   0   1   0   0   1   2   2     
  --- --- --- --- --- --- --- --- --- -- --

que indica que el primer grup és {5, 4, 1}, el segon grup {1, 6, 3} i el
tercer {4, 4, 2}. Per tant, els grups s’identificaran amb enters
consecutius començant per zero. Sabem que sempre existeix almenys una
solució. Podeu assumir que es generaran sempre 15 ingredients, tots ells
nombres naturals menors o iguals que 30.

A cada ronda, només un dels quatre fantasmes podrà efectuar l’encanteri,
encara que d’altres fantasmes també hagin aportat una solució. La
decisió de quin fantasma llença l’encanteri dependrà de l’ordre
d’execució de les comandes, que explicarem més endavant. El fantasma
escollit quedarà esgotat i no podrà realitzar cap altre encanteri durant
un cert nombre de rondes. No es permetran encanteris durant les últimes
50 rondes ni a l’inici de la partida, on podeu considerar que els
fantasmes acaben de de realitzar un encanteri i per tant han de
descansar les rondes pertinents.

El resultat d’un encanteri és prou impactant: el 15% de totes les
caselles que (i) no són paret, (ii) no contenen una unitat i (iii) no
estan posseïdes per la casa del fantasma passaran a estar posseïdes per
ella. Aquestes caselles s’escolliran de manera aleatòria.

Moviments dels mags. Un mag es pot moure pel tauler de la manera
següent:

- Només pot accedir a les cel·les adjacents en horitzontal i vertical,
  mai en diagonal.

- Si es mou cap a una cel·la ocupada per una paret, un llibre o una
  cel·la buida, el comportament serà el mateix que el d’un fantasma quan
  es mou cap a cel·les d’aquest tipus.

- Si es mou cap a una de les 8 cel·les adjacents a Voldemort, es veurà
  atacat per ell. El resultat de l’atac el detallarem quan expliquem com
  es mou Voldemort.

- Si es mou cap a una cel·la ocupada per un mag d’una casa enemiga
  s’iniciarà una batalla. Si la força de màgia d’un dels dos mags és més
  del doble que la de l’altre, el mag de la casa més feble perd i passa
  a formar part automàticament de l’altra casa, que rep un cert nombre
  de punts per aquesta fita. Notem que això modificarà la força de màgia
  de les dues cases.

  En cas contrari, és a dir, si les forces estan més igualades, el
  perdedor de la batalla iniciarà un procés de conversió: al cap d’un
  cert nombre de rondes, passarà a formar part del clan del mag
  guanyador. Un cop hagi acabat el procés de conversió, la casa del mag
  guanyador rebrà un cert nombre de punts. Per determinar el guanyador
  es fa el següent:

  Amb un 30% de probabilitat el mag que ha iniciat l’atac agafa l’altre
  per sorpresa, i per tant guanya la batalla. En cas contrari, si les
  forces dels dos clans són N i M, respectivament, el primer guanyarà la
  batalla amb probabilitat N/(N + M) i el segon amb probabilitat
  M/(N + M). En cas que N = M = 0, ambdós mags tenen un 50% de
  probabilitats de guanyar.

  Si el moviment és cap a una cel·la ocupada per un mag d’una casa
  enemiga en procés de conversió, no hi haurà atac i aquest moviment
  s’ignorarà.

- Si es mou cap a una cel·la ocupada per un mag de la seva mateixa casa,
  el moviment s’ignorarà, excepte si el mag que ocupa la posició de
  destí del moviment està en procés de conversió. En aquest cas, el
  procés de conversió s’anul·larà. Notem que, en cap cas, el mag que
  inicia el moviment canviarà de casella.

  Un mag que està en procés de conversió pot agafar llibres, però no pot
  atacar cap mag ni cap fantasma, ni aturar el procés de conversió de
  cap altre mag.

- Si es mou cap a una cel·la ocupada pel fantasma de la seva casa, el
  moviment s’ignorarà. Si està ocupada pel fantasma d’una casa rival,
  l’atacarà, i la quantitat de rondes que aquest fantasma ha d’esperar
  per a realitzar un encanteri s’incrementarà en una quantitat
  prefixada. Si un fantasma ha estat atacat per un mag, no podrà tornar
  a ser atacat per cap mag durant un cert nombre de rondes.

Moviments de Voldemort. Voldemort es mourà una vegada a cada ronda,
accedint a una cel·la adjacent en horitzontal o vertical. Per a fer-ho,
detectarà la unitat més propera a ell i s’hi aproparà. Si hi ha diverses
unitats a la mateixa distància, n’escollirà una a l’atzar. Malauradament
per les cases, Voldemort pot travessar parets.

Com hem explicat, qualsevol unitat que estigui en una de les 8 caselles
adjacents a Voldemort rebrà un atac. Si és un fantasma, reapareixerà en
una altra posició i haurà d’esperar unes quantes rondes a poder fer un
encanteri, exactament les mateixes que si n’acabés de fer un. Si la
unitat és un mag, aquest reapareixerà en una altra posició però passarà
a formar part d’un clan a l’atzar.

Addicionalment, Voldemort també farà desaparèixer qualsevol llibre que
estigui en una de les 8 cel·les adjacents a ell.

Com a resultat de les anterior regles, el nombre d’unitats totals és
constant al llarg de tot el joc, però els mags podran anar canviant de
casa. És important remarcar que les unitats tenen un identificador que
mai canvia, ni tan sols quan canvien de clan. Aquests identificadors són
naturals consecutius començant en 0.

Regeneració de d’objectes. Cada vegada que cal regenerar un llibre, un
mag o un fantasma, aquest reapareixerà sempre en una cel·la buida C i
tal que no hi ha cap unitat ni cap llibre en les posicions que
l’envolten (les marcades amb una x a la taula):

   x   x   x   x   x
  --- --- --- --- ---
   x   x   x   x   x
   x   x   C   x   x
   x   x   x   x   x
   x   x   x   x   x

Si en el moment de reaparèixer no existeix cap cel·la segura en aquest
sentit, l’objecte reapareixerà en una cel·la buida, que no tingui cap
unitat ni cap llibre.

Càlcul de la puntuació. La puntuació d’un clan en finalitzar una ronda
ve donada per la suma de dos components. La primera component es calcula
multiplicant per una certa constant el nombre de mags que el clan hagi
atacat i s’hagin acabat convertint en qualsevol de les rondes ja
finalitzades.

La segona component correspon a la multiplicació del nombre de cel·les
ocupades pel clan en aquesta ronda per una certa constant. Per tant,
entre ronda i ronda la puntuació total pot decrementar si es perd la
possessió d’algunes cel·les.

Les constants que indiquen el nombres de punts obtinguts per cada
aspecte, com d’altres que especifiquen els paràmetres inicials del joc,
estan definides a l’arxiu d’entrada default.cnf. Totes les partides es
jugaran amb exactament els valors donats en aquest arxiu.

Execució d’ordres. A cada ronda es pot donar més d’una ordre a la
mateixa unitat, tot i que només se seleccionarà la primera d’elles (si
n’hi ha alguna). Tot programa que intenti donar més de 1000 comandes
durant la mateixa ronda s’avortarà.

Cada ronda, les ordres seleccionades dels quatre jugadors s’executaran
amb ordre aleatori, però respectant l’ordre relatiu entre les unitats
d’un mateix clan. Com a conseqüència de la norma anterior, considereu la
possibilitat de donar les ordres a les vostres unitats a cada ronda de
més urgent a menys urgent.

Tingueu en compte que s’aplica cada moviment sobre el tauler que resulta
dels moviments anteriors. Per exemple, considereu el tauler

   x   x   x   x  
  --- --- --- --- --
   x   B   U   x  
   x   V   x   x  
   x   x   x   x  

on B representa un llibre i U i V dues mags de diferents clans. Imaginem
que el jugador que controla U ha decidit que aquest vagi cap a
l’esquerra, i el jugador que controla V ha decidit que vagi amunt. Si
s’executa primer el moviment de V, aleshores U s’ha quedat sense llibre,
perquè V ja se l’ha quedat i a més, la posterior execució del moviment
de U és un atac cap a V. Si U guanya, aleshores V podria canviar
automàticament de clan. En la visualització de la partida veurem una
transició de la matriu anterior cap a una situació on B ha desaparegut i
V ha canviat de clan. Òbviament, no hi podia haver un atac entre U i V
des de la configuració inicial, perquè els mags no es poden moure en
diagonal, però l’ordre d’execució de les comandes sí que ho ha fet
possible. Tingueu això en compte quan no entengueu certes situacions
durant la visualització de les partides.

Després de l’execució de tots els moviments dels jugadors, Voldemort fa
el seu moviment. A continuació es regeneren les unitats mortes per
Voldemort. Seguidament, es fan els canvis de clan de les unitats que
acabin la transició, s’incrementa la força de cada clan d’acord amb els
llibres que hagin agafat durant la ronda i es generen llibres en noves
posicions. Finalment, s’actualitza la puntuació.

El Visor

A continuació descrivim el visor de partides:

- A la part superior hi ha botons que permeten reproduir o pausar la
  partida, anar al començament o al final de la partida, activar o
  desactivar el mode d’animació o obtenir una finestra d’ajuda amb més
  maneres de controlar com es reprodueix la partida. També hi trobareu
  la ronda actual i un botó per tancar el visor. Una barra de
  desplaçament horitzontal mostra visualment en quin punt de la partida
  es troba la ronda actual.

- A la columna de l’esquerra, apareix cada jugador amb el nom i color
  corresponents. A sota es mostra la puntuació actual, el nombre
  d’unitats vives i la força del jugador corresponent. A les partides
  jugades a Jutge.org, també es mostra el percentatge de temps de CPU
  que s’ha consumit fins ara (si està esgotat, s’indica amb un ’out’). A
  la part superior dreta apareixen els colors dels jugadors ordenats per
  puntuació.

- Les cel·les no posseïdes per ningú són de color blanc. En cas
  contrari, tenen el color del jugador que les posseeix.

- Les cel·les que són paret tenen color gris fosc, gairebé negre.

- Els mags es representen amb un cercle del color corresponent. En cas
  d’estar en procés de conversió, tenen forma de creu.

- Els fantasmes es representen amb un quadrat del color corresponent i
  contorn exterior negre.

- Els llibres es representen amb un cercle vermell i contorn exterior
  negre.

- Voldemort es representa amb un cercle vermell amb un contorn exterior
  vermell transparent.

Com programar un jugador

El primer que heu de fer és descarregar-vos el codi font. Aquest inclou
un programa C ++ que executa les partides i un visualitzador HTML per
veure-les en un format raonable i animat. A més, us proporcionem un
jugador “Null” i un jugador “Demo” per facilitar el començament de la
codificació del jugador.

Executar la primera partida

Aquí us explicarem com executar el joc sota Linux, però hauria de
funcionar també sota Windows, Mac, FreeBSD, OpenSolaris, ... Només
necessiteu una versió recent g ++, el make instal·lat al sistema, a més
d’un navegador modern com Firefox o Chrome.

1.  Obriu una consola i feu cd al directori on us heu descarregat el
    codi font.

2.  Si, per exemple, teniu una versió de Linux en 64 bits, executeu:

    cp AIDummy.o.Linux64 AIDummy.o

    Amb altres arquitectures, cal escollir els objectes adequats que
    trobareu al directori.

3.  Executeu

    make all

    per compilar el joc i tots els jugadors. Tingueu en compte que el
    Makefile identifica com a jugador qualsevol fitxer que coincideixi
    amb AI*.cc

4.  Es crea un fitxer executable anomenat Game. Aquest executable us
    permet executar una partida mitjançant una comanda com la següent:

    ./Game Demo Demo Demo Demo -s 30 < default.cnf > default.res

    Aquesta comanda comença una partida, amb la llavor aleatòria 30, amb
    quatre instàncies del jugador Demo, al tauler definit a default.cnf.
    La sortida d’aquesta partida es redirigeix a default.res.

5.  Per veure una partida, obriu el fitxer visualitzador viewer.html amb
    el navegador, per exemple executant des d’un terminal la comanda
    firefox viewer.html, i carregueu el fitxer default.res.

Utilitzeu

./Game --help

per veure la llista de paràmetres que es poden usar. Particularment útil
és

./Game --list

per veure tots els noms de jugadors reconeguts.

En cas que sigui necessari, recordeu que podeu executar

make clean

per esborrar l’executable i els objectes i començar la compilació de
nou.

[image]

Afegir el vostre jugador

Per crear un jugador nou amb, per exemple, nom Harry, copieu AINull.cc
(un jugador buit que proporcionem com a plantilla) a un fitxer nou
AIHarry.cc. A continuació, editeu el fitxer nou i canvieu la línia

@#define PLAYER_NAME Null@

a

@#define PLAYER_NAME Harry@

El nom que trieu pel vostre jugador ha de ser únic, no ofensiu i tenir
com a màxim 12 caràcters. Aquest nom es mostrarà al lloc web i durant
les partides.

A continuació, podeu començar a implementar el mètode virtual @play()@,
heretat de la classe base @Player@. Aquest mètode, que serà cridat a
cada ronda, ha de determinar les ordres que s’enviaran a les vostres
unitats.

Podeu utilitzar definicions de tipus, variables i mètodes a la vostra
classe de jugador, però el punt d’entrada del vostre codi serà sempre el
mètode @play()@.

Des de la vostra classe jugador també podeu cridar funcions que trobareu
especificades als arxius següents:

- State.hh: accedir a l’estat del joc.

- Action.hh: donar ordres a les vostres unitats.

- Structs.hh: estructures de dades útils.

- Settings.hh: accedir als paràmetres del joc.

- Player.hh: mètode @me()@.

- Random.hh: generar nombre aleatoris.

Trobareu un resum de tota aquesta informació a l’arxiu api.pdf. També
podeu examinar el codi del jugador “Demo” a AIDemo.cc com a exemple de
com usar aquestes funcions.

Tingueu en compte que no heu d’editar el mètode @factory()@ de la classe
del vostre jugador, ni l’última línia que afegeix el vostre jugador a la
llista de jugadors disponibles.

Restriccions en enviar el vostre jugador

Quan creieu que el vostre jugador és prou fort per entrar a la
competició, podeu enviar-lo al Jutge. Degut a que s’executarà en un
entorn segur per prevenir trampes, algunes restriccions s’apliquen al
vostre codi:

- Tot el vostre codi font ha d’estar en un sol fitxer (com AIHarry.cc).

- No podeu utilitzar variables globals (en el seu lloc, utilitzeu
  atributs a la vostra classe).

- Només teniu permès utilitzar biblioteques estàndard com iostream,
  vector, map, set, queue, algoritme, cmath, …En molts casos, ni tan
  sols cal incloure la biblioteca corresponent.

- No podeu obrir fitxers ni fer cap altra crida a sistema (threads,
  forks, ...)

- El vostre temps de CPU i la memòria que utilitzeu seran limitats,
  mentre que no ho són al vostre entorn local quan executeu ./Game.

- El vostre programa no ha d’escriure a @cout@ ni llegir de @cin@. Podeu
  escriure informació de depuració a @cerr@, però els vostres enviaments
  al Jutge no han d’escriure res, ni tan sols a cerr. En cas de fer-ho,
  el comportament del vostre jugador pot no ser l’esperat.

- Qualsevol enviament al Jutge ha de ser un intent honest de jugar.
  Qualsevol intent de fer trampes de qualsevol manera serà durament
  penalitzat.

- Un cop hagueu enviat un jugador al Jutge que hagi derrotat al Dummy,
  podeu fer més enviaments però haureu de canviar el nom del jugador. És
  a dir, un cop un jugador ha vençut al Dummy, el seu nom queda
  bloquejat i no es pot reutilitzar.

Consells

- NO DONEU O DEMANEU EL VOSTRE CODI A NINGÚ. Ni tan sols una versió
  antiga. Ni fins i tot al vostre millor amic. Ni tans sols d’estudiants
  d’anys anteriors. Utilitzem detectors de plagi per comparar els
  vostres programes, també contra enviaments de jocs d’anys anteriors.
  No obstant, podeu compartir arxius objecte.

  Qualsevol plagi implicarà una nota de 0 en l’assignatura (no només del
  Joc) de tots els estudiants involucrats. Es podran també prendre
  mesures disciplinàries addicionals. Si els estudiants A i B es veuen
  implicats en un plagi, les mesures s’aplicaran als dos,
  independentment de qui va crear el codi original. No es farà cap
  excepció sota cap circumstància.

- Abans de competir amb els companys, concentreu-vos en derrotar al
  Dummy.

- Llegiu les capçaleres de les classes que aneu a utilitzar. No cal que
  mireu les parts privades o la implementació.

- Comenceu amb estratègies simples, fàcils d’implementar i depurar, ja
  que és exactament el que necessitareu al principi.

- Definiu mètodes auxiliars senzills (però útils) i assegureu-vos que
  funcionin correctament.

- Intenteu mantenir el vostre codi net. Això farà més fàcil canviar-lo i
  afegir noves estratègies.

- Com sempre, compileu i proveu el vostre codi sovint. És molt més fàcil
  rastrejar un error quan només heu canviat poques línies de codi.

- Utilitzeu @cerr@ per produir informació de depuració i afegiu asserts
  per assegurar-vos que el vostre codi fa el que hauria de fer. Recordeu
  eliminar (o comentar) els cerr abans d’enviar el vostre codi al
  Jutge.org.

- Quan depureu un jugador, elimineu els @cerr@s que tingueu en el codi
  d’altres jugadors, per tal de veure només els missatges que desitgeu.

- Podeu utilitzar comandes com el grep de Linux per tal de filtrar la
  sortida produïda per Game.

- Activeu l’opció DEBUG al Makefile, que us permetrà obtenir traces
  útils quan el vostre programa avorta. També hi ha una opció PROFILE
  que podeu utilitzar per optimitzar codi.

- Si l’ús de @cerr@ no és suficient per depurar el vostre codi, apreneu
  com utilitzar valgrind, gdb o qualsevol altra eina de depuració.

- Podeu analitzar els arxius produïts per Game, que descriuen com
  evoluciona el tauler a cada ronda.

- Conserveu una còpia de les versions antigues del vostre jugador.
  Feu-lo lluitar contra les seves versions anteriors per quantificar les
  millores.

- Assegureu-vos que el vostre programa sigui prou ràpid. El temps de CPU
  que es permet utilitzar és bastant curt.

- Intenteu esbrinar les estratègies dels altres jugadors observant
  diverses partides. D’aquesta manera, podeu intentar reaccionar als
  seus moviments, o fins i tot imiteu-los o milloreu-los amb el vostre
  propi codi.

- No espereu fins al darrer minut per enviar el jugador. Quan hi ha
  molts enviaments al mateix temps, el servidor triga més en executar
  les partides i podria ser ja massa tard!

- Podeu enviar noves versions del vostre programa en qualsevol moment.

- Recordeu: mantingueu el codi senzill, compileu-lo sovint i proveu-lo
  sovint, o us en penedireu.
