report.tex

\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[italian]{babel}
\usepackage{amsmath, amssymb, amsfonts}
\usepackage{epigraph}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{hyperref}
\usepackage{tikz}

\title{\textbf{Hopeless}\\
\vspace{0.2cm}\normalsize Relazione del progetto per il corso di Algoritmi\\
\normalsize Università di Bologna}
\date{2022 - 2023}

\begin{document}

\maketitle

\begin{flushright}
  Argonni Emanuele, 0001078626\linebreak
  Musiani Samuele, 0001069143
\end{flushright}


\section{Introduzione}

Il progetto consisteva nello sviluppare un programma che sapesse giocare nel 
miglior modo possibile il gioco \emph{Connect X}. Quest'ultimo è una 
generalizzazione del classico gioco Forza 4 resa possibile grazie a delle 
configurazioni che si distaccavano dalla classica tabella $6 \times 7$ presente 
nel gioco originale;

\section{Il giocatore Small e Big}

Se si da una veloce occhiata al codice si nota che in realtà il giocatore è 
diviso in due: Small e Big. Questa distinzione apparentemente arbitraria è 
necessaria in quanto, come spiegato più avanti nella sezione \ref{sec_bitboard},
la rappresentazione della tabella di gioco tramite Bitboard è possibile solo 
fino alla configurazione $7 \times 7$. Dove possibile quindi è stata adottata 
questa rappresentazione, mentre dove non lo era è stata mantenuta la classica
CXBoard fornita dal docente. Per questo il nome Small e Big: il giocatore Small 
può giocare solo le configurazioni più piccole della $7 \times 7$ compresa, 
mentre il giocatore Big, nonostante possa giocare tutte le configurazioni, si 
limita a quelle rimanenti.

\section{Caratteristiche generali}

Nonostante la divisione dei due giocatori in Small e Big, molti aspetti 
rimangono gli stessi tra i due. Di seguito sono quindi presentati tutti gli 
aspetti comuni ai due giocatori, lasciando per ultimi gli aspetti in cui 
differiscono.

\subsection{PVS}
Forza 4, e di conseguenza anche Connect X, è un gioco a somma-zero e a
informazione perfetta. Queste due proprietà del gioco permettono di implementare
una ricerca basata su MiniMax. Alla base di un qualsiasi giocatore artificiale
vi è infatti un algoritmo di ricerca che permette di esplorare l'albero di tutte
le mosse possibili e determinare quali sono vincenti e quali sono perdenti. In
particolare MiniMax è alla base della ricerca nei giochi a somma-zero e a
informazione perfetta.

L'algoritmo MiniMax, nonostante sia perfettamente funzionante e ritorni sempre
la mossa migliore, è particolarmente inefficiente in quanto richiede di 
esplorare l'intero albero di gioco. Questo porta a dei costi computazionali 
estremamente elevati. Prendiamo per esempio la classica configurazione di Forza 
4 con 6 righe e 7 colonne. Se volessi calcolare l'intero albero di gioco, e 
quindi tutte le possibili configurazioni che si possono ottenere, dovremmo 
considerare $3^{7 \cdot 6} = 3^{42} \approx 1.09 \cdot 10^{20}$ configurazioni. 
In realtà questo è un limite superiore, in quanto molte di queste configurazioni 
non sarebbero valide. Nonostante ciò le configurazioni restano comunque troppe 
per essere esplorate tutte in un tempo accettabile. Sono stati quindi inventati 
degli ulteriori algoritmi, che si basano comunque su MiniMax, ma che sono molto 
più efficienti rispetto a quest'ultimo. Il più famoso è AlphaBeta. Non 
riteniamo necessario spiegare il funzionamento di MiniMax e AlphaBeta, ma bensì 
vogliamo dedicare parte di questa relazione ad illustrare la variate di 
AlphaBeta adottata nel nostro giocatore: PVS, o meglio Principal Variation 
Search.

La PVS si basa sul fatto che se esploriamo per prima la linea di gioco 
principale (la Principal Variation), o meglio quella che entrambi i giocatori 
considerano migliore, allora risulta quasi superfluo esplorare completamente 
tutte le altre possibilità di gioco in quanto dovrebbero essere peggiori a 
quella già vista. Questo però non vuol dire che non le esploriamo, ma bensì che 
la loro esplorazione è fatta in modo approssimativo in quanto non mira a 
ottenere un punteggio preciso della variante come farebbe un classico algoritmo 
AlphaBeta, ma punta a capire soltanto se la variante è migliore di quella 
considerata come principale. Se la variante è peggiore il giocatore non fa nulla 
e continua a valutare le altre varianti secondarie finché non le ha concluse, se 
invece la ricerca veloce su quella variante ha ritornato che in realtà è 
migliore della principale si esegue una ricerca completa su quella variante per 
ritornare il punteggio corretto. È necessario infatti puntualizzare che la 
ricerca veloce non restituisce il punteggio corretto associato a quella 
variante, ma soltanto se è migliore o peggiore di quella considerata come 
principale. È quindi necessario eseguire una ricerca completa per determinare il
punteggio corretto se la variante secondaria risulta essere migliore della 
principale.

Nel caso peggiore, ovvero quello in cui ogni variante secondaria risulta essere
migliore della variante principale considerata in precedenza, l'algoritmo PVS 
risulta essere più lento del classico AlphaBeta. Questo caso pessimo però è 
molto raro, sopratutto se si integra PVS un ordinamento delle mosse in modo
da considerare prima quelle che risulta essere più promettenti.

Di seguito è presentata una versione in pseudo-codice dell'algoritmo PVS:

\begin{algorithm}[H]
  \caption{\textsc{PrincipalVariationSearch}}
  \label{alg_pvs}
  \begin{algorithmic}[0]
    \Function {PVS}{$Board$, $\alpha$, $\beta$, $depth$, $color$}

      \If{$depth = 0$ \textbf{or} $node$ is a leaf}
        \State \Return $color * \Call{Evaluate}{Board}$
      \EndIf
      \\
      \State $bSearchPV \gets true$
      \For{$move$ \textbf{in} \Call{Sorted}{$Board.availableMoves()$}}
        \State $B.makeMove(move)$
        \If{$bSearchPV$}
          \Comment{\`E la \emph{Principal Variation}}
          \State $score \gets -\Call{PVS}{B, -beta, -alpha, depth - 1, \textrm{not } color}$
        \Else
          \Comment{Ricerca veloce sulle varianti secondarie}
          \State $score \gets -\Call{fastSearch}{B, -alpha, depth - 1, \textrm{not } color}$
          \If{$\alpha < score < \beta$}
            \Comment{\`E un nodo interessante}
            \State $score \gets -\Call{PVS}{B, -beta, -alpha, depth - 1, \textrm{not } color}\}$
            \State $\alpha \gets \max\{\alpha, score\}$
          \EndIf
        \EndIf
        \State $B.unamkeMove()$
        \\
        \If{$score \geq \beta$}
        \Comment{Potatura $\alpha$-$\beta$}
        \State \textbf{return} beta;
        \EndIf
        \If{$score > alpha$}
          \State $\alpha \gets score$
        \EndIf
        \State $bSearchPV \gets false$
      \EndFor
      \State \Return $alpha$
    \EndFunction

  \end{algorithmic}
\end{algorithm}

Si noti che utilizzando la proprietà di somma-zero del gioco preso in analisi, 
si può utilizzare la stessa funzione di ricerca sia per il giocatore che 
massimizza sia per il giocatore che minimizza semplicemente negando la chiamata
alla funzione successiva e invertendo $\alpha$ e $\beta$.

La ricerca principale nell'algoritmo PVS è come un normalissimo AlphaBeta se non
si considerano le ricerche veloci. La chiamata iniziale di PVS è infatti con i
parametri $\alpha$ e $\beta$ rispettivamente $-\infty$ e $+\infty$. Quello che 
però appunto distingue PVS è la ricerca veloce.

La fastSearch non è altro che un AlphaBeta modificato in modo che i parametri 
$\alpha$ e $\beta$ riducano la finestra talmente tanto da risultare quasi nulla.
Questo permette di tagliare tantissimi rami e fare in modo che la ricerca sia
effettivamente più veloce.

\begin{algorithm}
  \caption{\textsc{fastSearch}}
  \label{alg_fastSeach}
  \begin{algorithmic}
    \Function {fastSearch}{$Board$, $\beta$, $depth$, $color$}

      \If{$depth = 0$ \textbf{or} $node$ is a leaf}
        \State \Return $color * \Call{Evaluate}{Board}$
      \EndIf
      \\
      \For{$move$ \textbf{in} $Board.availableMoves()$}
        \State $B.makeMove(move)$
        \State $score \gets -\Call{fastSearch}{B, 1 - beta, depth - 1, \textrm{not } color}$
        \State $B.unamkeMove()$
        \\
        \If{$score \geq \beta$}
        \Comment{Potatura $\alpha$-$\beta$}
        \State \textbf{return} beta;
        \EndIf
      \EndFor
      \State \Return $beta - 1$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\subsection{Iterative deepening}
Il framework Iterative Deepening (ID) è una tecnica di ricerca adottata come 
metodo base per la gestione del tempo nella scelta di una mossa negli algoritmi 
che sfruttano la ricerca in profondità (Depth-First search, DFS) come PVS. 
L'idea alla base di questa strategia è quella di effettuare una serie 
di iterazioni dell'algoritmo di ricerca in profondità, aumentando gradualmente 
la profondità massima dell'albero esplorato. A ogni iterazione, l'algoritmo 
effettua una ricerca in profondità limitata (Depth-Limited search) e, alla
conclusione, memorizza la mossa migliore fino a quel momento trovata. 
Successivamente ricomincia la ricerca con una profondità maggiore. Questo 
procedimento continua fino a che il tempo non scade, momento in cui la mossa 
migliore fino a quel momento viene ritornata.

\begin{algorithm}
  \caption{\textsc{iterativeDeepening}}
  \label{alg_iterativeDeepening}
  \begin{algorithmic}
    \State $previousDepthSearch \gets 2$
    \Comment{Variabili globali}
    \State $currentBestMove \gets 0$
    \\
    \Function {IterativeDeepening}{$Board$}
      \State $depth \gets 2$
      \If{$amIFirst$}
        \Comment{Sono il primo giocatore}
        \State $depth \gets \Call{max}{previousDepthSearch - 2, 2}$
      \Else
        \State $depth \gets \Call{max}{previousDepthSearch - 2, 1}$ 
      \EndIf
      \\
      \State $searchNotFinished \gets true$
      \While{searchNotFinished}
        \Comment{Non ho visitato ancora tutte le foglie} 
        \State $currentBestMove \gets \Call{movePVS}{Board, depth}$
        \If{GameTree is all visited}
          \Comment{Ho visitato tutto l'albero}
          \State $searchNotFinished \gets false$
        \EndIf
        \State $previousDepthSearch \gets depth$
        \State $depth \gets depth + 2$
      \EndWhile
      \State \Return $currentBestMove$
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\textsc{movePvSearch} è una variante di PVS in cui non viene ritornato il 
valore della posizione ma bensì la mossa migliore nella posizione attuale.

Si noti che nell'algoritmo presentato la profondità viene inizializzata in base 
al giocatore che inizia la partita. Inoltre l'aumento a ogni iterazione della 
profondità non è di 1 ma bensì di 2. È necessario fare entrambe queste 
variazioni all'algoritmo generale descritto sopra per valutare solo le 
profondità in cui entrambi i giocatori hanno lo stesso numero di pedine in 
gioco. Questo è necessario perché se si valutassero profondità finali con un 
numero diverso di pedine per i due giocatori, uno di essi risulterebbe sempre in 
vantaggio. Ovviamente siamo costretti a valutare posizioni intermedie in cui il
primo giocatore avrà posizionato una pedina in più rispetto al secondo, ma 
questo non avviene nello stadio finale della ricerca in cui è necessario 
scegliere la mossa migliore.

Se il tempo massimo che il giocatore ha per eseguire una mossa scade durante
la ricerca PVS, viene ritornata immediatamente la mossa migliore che è salvata
nella variabile globale $currentBestMove$.

La variabile $previousDepthSearch$ serve per memorizzare la profondità che il
giocatore ha raggiunto nella precedente chiamata a ID. In questo modo, se nella
precedente chiamata eseguiamo una ricerca a tutte le profondità fino alla numero 
$n$, nella chiamata successiva puntiamo direttamente alla profondità $n - 2$ in 
quanto siamo praticamente certi di poterla raggiungere nel tempo dato.


\subsection{Transposition table}
\label{sec_transpositionTable}
La Transposition table (o tabella delle trasposizioni) è una strutture dati 
che memorizza le posizioni di gioco esplorate insieme alla loro valutazione. 
Questo permette di evitare di ricalcolare nuovamente la stessa posizione durante 
l'esecuzione dell'algoritmo di ricerca. Quando infatti una posizione già 
memorizzata viene ritrovata, è possibile riutilizzare la valutazione 
precedentemente calcolata, risparmiando tempo e risorse computazionali.
Nei giochi da tavolo complessi, come gli scacchi, il Go e Forza 4 il numero di 
posizioni possibili cresce esponenzialmente all'aumentare della profondità di 
ricerca. L'impiego delle tabelle di trasposizione riduce notevolmente l'overhead 
computazionale, poiché evita di ricalcolare le stesse posizioni più volte. 
Questo è per consentire l'esplorazione di alberi decisionali più profondi.

L'effettiva implementazione della Transposition table è basta sulla classe
HashTable fornita dalla libreria di Java. La posizione viene memorizzata tramite
un hash della configurazione di gioco. L'effettivo metodo di hash però 
differisce per il giocatore Small e il giocatore Big, quindi viene lasciata 
nelle rispettive sezioni la spiegazione dettagliata del metodo specifico.

Si noti che oltre alla posizione stessa è importante memorizzare la profondità
a cui si è valutata, perché non sempre i valori all'interno della Transposition
table sono affidabili se la profondità è più bassa di quella richiesta nella
ricerca.

\subsection{Ordine delle mosse}
Quando si devono valutare tutte le possibili mosse in una determinata posizione
è importante l'ordine con cui si decide di valutarle. L'algoritmo PVS infatti 
basa proprio il suo principio sulla valutazione della variante principale come 
prima mossa e tutte le restanti come varianti secondarie. Se infatti si 
valutasse prima la mossa peggiore, le ricerche rapide di PVS ritornerebbero un
valore maggiore di quello riscontrato sulla prima ricerca completa e, come visto 
nella sezione riguardante PVS, questo farebbe perdere tempo al giocatore. Il 
caso in cui PVS performa meglio in assoluto è quando valuta lo mossa migliore 
come prima.

La tecnica base per ottenere questo è riordinare le mosse possibili in base 
al punteggio ottenuto nell'iterazione precedente memorizzato nella Transposition
table. Se infatti l'ordine non è più quello base che considera le mosse da 
sinistra a destra, ma bensì quello in cui la mossa con il punteggio maggiore è
la prima, è molto più probabile che PVS trovi la variazione principale nella 
prima mossa e quindi sia molto efficiente.

Nonostante a livello teorico il riordinamento delle mosse in base alla loro 
valutazione ottenuta nelle iterazioni precedenti sia il modo migliore per 
riordinare tutte le mosse se si sta utilizzando l'algoritmo PVS, a livello 
pratico il nostro giocatore non ha riscontrato nessun miglioramento. Questo 
secondo noi è dovuto a vari aspetti pratici:
\begin{enumerate}
  \item L'operazione di sorting fatta sulle mosse non è troppo dispendiosa 
    se la si considera singolarmente. Se però la si contestualizza 
    nell'algoritmo totale si scopre che in realtà viene eseguita tantissime 
    volte. Questo porta a un rallentamento generale dell'algoritmo che non 
    riesce più a esplorare in profondità come rispetto alla versione senza 
    questo tipo di ordinamento delle mosse.

  \item Per ordinare le mosse è necessario prima leggere i loro valori dalla 
    tabella delle trasposizioni. Per fare ciò però è necessario avere l'hash 
    relativo a ogni mossa che si vuole ordinare. Per come viene calcolato 
    l'hash \footnote{Spiegazioni più dettagliate si troveranno nella sezione
    dedicata. Per ora è necessario soltanto puntualizzare che l'obbligo di 
    eseguire una mossa sulla board per sapere l'hash della posizione è legato
    soltanto alle board piccole ($\leq 7 \times 7$) e non a quelle grandi 
    ($\geq 20 \times 20$). Nonostante ciò nelle board grandi il costo di 
    ordinamento di tutte le mosse è molto maggiore risultando comunque in un
    peggioramento} però è necessario eseguire ogni mossa singolarmente per 
    ottenerlo e poi annullarla. Questo porta a eseguire e ad annullare ogni 
    mossa almeno due volte: la prima quando si ordinano le mosse disponibili e 
    la seconda quando la si esegue per valutare un particolare ramo dell'albero
    di gioco. 

  \item Infine la nostra euristica non è sicuramente accurata abbastanza da 
    assegnare in modo sistematico il valore migliore alla linea principale di 
    gioco. È quindi probabile che anche con le mosse riordinate la PVS non sia
    comunque tra le prime, risultando in un rallentamento.
\end{enumerate}

La soluzione adottata per evitare di ordinare le mosse in ordine di valutazione
è stata quella di ordinarle rispetto alla loro posizione relativa al centro: 
mosse più vicine al centro vengono valutate prima di mosse lontane da esso.
L'algoritmo è quindi il seguente:

\begin{algorithm}
  \caption{\textsc{reorderMoves}}
 \begin{algorithmic}
   \Function{reorderMoves}{$Board$}
   \State $possibleMoves[] \gets Board.getPossibleMoves()$
     \Comment{Le mosse sono ordinate da sinistra a destra}
     \State $l \gets possibleMoves.length$
     \State $orderedMoves[]$ is an array of length $l$
     \State $delta \gets 0$
     \\
     \For{$i \gets 0$ \textbf{to} $i < l$ \textbf{step} $i \gets i + 1$}
       \If{$i$ is odd}
         \State $delta \gets delta + 1$

         \State $orderedMoves[i] \gets possibleMoves[l / 2 - delta]$
       \Else
         \State $orderedMoves[i] \gets possibleMoves[l / 2 + delta]$
       \EndIf
     \EndFor

     \State \Return $orderedMoves[]$
   \EndFunction
 \end{algorithmic} 
\end{algorithm}

\subsection{Euristica}
Non potendo raggiungere immediatamente i nodi terminali dell'albero di gioco è
necessario poter assegnare un punteggio relativo a una posizione in cui nessuno
dei due giocatori ha ancora vinto. In particolare il punteggio è 0 se la 
posizione risulta pari tra i due giocatori, oppure assume un valore positivo se
il giocatore che sta valutando è in vantaggio, o altrimenti negativo se la 
posizione è vantaggiosa per l'avversario. Questo permette di selezionare i rami
più promettenti e distinguerli da quelli perdenti.

L'approccio usato per la funzione di valutazione è quello di considerare 
le serie aperte di pedine che potrebbero in futuro dare una vittoria. In 
particolare vengono considerati anche gli spazi vuoti in quanto più spazi danno
una probabilità maggiore di riuscire a chiudere una determinata sequenza. Si 
noti però che il peso degli spazi nella valutazione è soltanto un terzo rispetto
a quello delle pedine effettivamente posizionate.

Vengono eseguiti soltanto controlli orizzontali e diagonali in quanto abbiano 
notato che i controlli verticali erano pressoché inutili. È infatti immediato 
per il giocatore avversario bloccare una linea verticale giocando la cella
immediatamente sopra.

Una proprietà interessante della funzione di valutazione è la linearità. 
Inizialmente infatti abbiamo tentanto un approccio in cui le sequenze di pedine 
venivano valutate tramite una funzione quadratica. Dopo svariati test è però 
stato necessario eliminare qualsiasi elevamento a potenza in quanto portava la 
valutazione a divergere troppo dal risultato corretto del ramo dell'albero di 
gioco.

Durante le fasi iniziale è stata anche adottata una valutazione delle mosse che
privilegiava quelle più vicine al centro. Dopo molti test abbiamo deciso però di
eliminare questa valutazione in quanto non portava nessun miglioramento.

\section{Bitboard in Small}
\label{sec_bitboard}
La vera differenza tra il gicatore Big e il giocatore Small e il modo in cui
viene rappresentata una configurazione di gioco. Il metodo sicuramente più
intuitivo per rappresentare una posizione di Forza 4 è quello di impegare una 
matrice in cui ogni cella è direttamente associata a una cesella della 
posizione e i valori della matrice indicano se una determinata cella è vuota, 
è presente una pedina del primo giocatore o è presente una pedina del secondo 
giocatore.

Questo metodo ovviamente funziona ed è anche molto semplice da implementare. La
classe fornita dal docente che si occupava delle configurazioni di gioco 
utilizza infatti una matrice. Il problema della rappresentazione tramite matrice
sorge quando si deve valutare se un determinato giocatore ha vinto. Per vincere
in Connect X bisogna allineare esattamente \emph{X} pedine in verticale, 
orizzontale o diagonale. Quindi il controllo consiste nel guardare tutte le 
colonne, tutte le righe e infine tutte le diagonali per scoprire se un giocatore
è riuscito ad allineare \emph{X} pedine. Questo controllo va eseguito ogni volta
che un giocatore esegue una mossa, risultando quindi estremamente dispendioso.
Nella classe CXBoard è però presente un'ottimizzazione: essendo il controllo 
eseguito per ogni singola mossa giocata, non è necessario controllare tutte le
righe, colonne e diagonali della posizione, ma soltanto quelle interessate 
dall'ultima mossa.

Esiste però un modo per rappresentare tutte le configurazioni di gioco tramite
due interi a 64 bit e controllare se un giocatore ha vinto senza l'utilizzo di
loop e solo grazie alle operazioni tra bit.

\subsection{Funzionamento}
Rappresentiamo un board di dimensioni $M \times N$ tramite due interi a 64 bit
che chiameremo \emph{position} e \emph{mask}. L'idea è quella di associare ogni
singola cella di una posizione ad un bit della \emph{position} e ad un bit della
\emph{mask}. Prendiamo la classica tabella di Forza 4 che ha dimensioni $M = 6$ 
e $N = 7$ e numeriamo le caselle come mostrato in figura \ref{fig_bitNumbers}.

\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}
    \tikzstyle{every node}=[font=\LARGE]
    \draw  (0,0) rectangle ++(12,11.5);

    \draw  (1.15,1.13) circle (0.7cm);
    \draw  (2.75,1.13) circle (0.7cm);
    \draw  (4.35,1.13) circle (0.7cm);
    \draw  (5.95,1.13) circle (0.7cm);
    \draw  (7.55,1.13) circle (0.7cm);
    \draw  (9.20,1.13) circle (0.7cm);
    \draw  (10.8,1.13) circle (0.7cm);

    \draw  (1.15,2.96) circle (0.7cm);
    \draw  (2.75,2.96) circle (0.7cm);
    \draw  (4.35,2.96) circle (0.7cm);
    \draw  (5.95,2.96) circle (0.7cm);
    \draw  (7.55,2.96) circle (0.7cm);
    \draw  (9.20,2.96) circle (0.7cm);
    \draw  (10.8,2.96) circle (0.7cm);

    \draw  (1.15,4.79) circle (0.7cm);
    \draw  (2.75,4.79) circle (0.7cm);
    \draw  (4.35,4.79) circle (0.7cm);
    \draw  (5.95,4.79) circle (0.7cm);
    \draw  (7.55,4.79) circle (0.7cm);
    \draw  (9.20,4.79) circle (0.7cm);
    \draw  (10.8,4.79) circle (0.7cm);

    \draw  (1.15,6.62) circle (0.7cm);
    \draw  (2.75,6.62) circle (0.7cm);
    \draw  (4.35,6.62) circle (0.7cm);
    \draw  (5.95,6.62) circle (0.7cm);
    \draw  (7.55,6.62) circle (0.7cm);
    \draw  (9.20,6.62) circle (0.7cm);
    \draw  (10.8,6.62) circle (0.7cm);

    \draw  (1.15,8.45) circle (0.7cm);
    \draw  (2.75,8.45) circle (0.7cm);
    \draw  (4.35,8.45) circle (0.7cm);
    \draw  (5.95,8.45) circle (0.7cm);
    \draw  (7.55,8.45) circle (0.7cm);
    \draw  (9.20,8.45) circle (0.7cm);
    \draw  (10.8,8.45) circle (0.7cm);

    \draw  (1.15,10.28) circle (0.7cm);
    \draw  (2.75,10.28) circle (0.7cm);
    \draw  (4.35,10.28) circle (0.7cm);
    \draw  (5.95,10.28) circle (0.7cm);
    \draw  (7.55,10.28) circle (0.7cm);
    \draw  (9.20,10.28) circle (0.7cm);
    \draw  (10.8,10.28) circle (0.7cm);

    \node at (1.15,1.13) {$0$};
    \node at (2.75,1.13) {$7$};
    \node at (4.35,1.13) {$14$};
    \node at (5.95,1.13) {$21$};
    \node at (7.55,1.13) {$28$};
    \node at (9.20,1.13) {$35$};
    \node at (10.8,1.13) {$42$};

    \node at (1.15,2.96) {$1$};
    \node at (2.75,2.96) {$8$};
    \node at (4.35,2.96) {$15$};
    \node at (5.95,2.96) {$22$};
    \node at (7.55,2.96) {$29$};
    \node at (9.20,2.96) {$36$};
    \node at (10.8,2.96) {$43$};

    \node at (1.15,4.79) {$2$};
    \node at (2.75,4.79) {$9$};
    \node at (4.35,4.79) {$16$};
    \node at (5.95,4.79) {$23$};
    \node at (7.55,4.79) {$30$};
    \node at (9.20,4.79) {$37$};
    \node at (10.8,4.79) {$44$};

    \node at (1.15,6.62) {$3$};
    \node at (2.75,6.62) {$10$};
    \node at (4.35,6.62) {$17$};
    \node at (5.95,6.62) {$24$};
    \node at (7.55,6.62) {$31$};
    \node at (9.20,6.62) {$38$};
    \node at (10.8,6.62) {$45$};

    \node at (1.15,8.45) {$4$};
    \node at (2.75,8.45) {$11$};
    \node at (4.35,8.45) {$18$};
    \node at (5.95,8.45) {$25$};
    \node at (7.55,8.45) {$32$};
    \node at (9.20,8.45) {$39$};
    \node at (10.8,8.45) {$46$};

    \node at (1.15,10.28){$5$};;
    \node at (2.75,10.28){$12$};;
    \node at (4.35,10.28){$19$};;
    \node at (5.95,10.28){$26$};;
    \node at (7.55,10.28){$33$};;
    \node at (9.20,10.28){$40$};;
    \node at (10.8,10.28){$47$};;
\end{tikzpicture}
\caption{Ordine dei bit in una tabella $6 \times 7$}
  \label{fig_bitNumbers}
\end{figure}

A ogni cella corrisponde il numero del bit indicato. L'intero \emph{position} 
memorizza la posizione del giocatore che dovrà fare la prossima mossa. In 
particolare avrà uguale a 1 tutti i bit in cui è presente una sua pedina e a 0
tutti quelli in cui vi è una pedina dell'avversario o non vi è nessuna pedina. 
L'intero \emph{mask} memorizza invece le pedine occupate indipendentemente dal
giocatore. In particolare se le celle sono vuote i bit corrispondenti saranno a 0, 
mentre se le celle contengono una pedina i bit corrispondenti saranno a 1. 
Vale quindi che quando tutte le celle sono vuote $position = 0$ e $mask = 0$. Se 
volessimo rappresentare la posizione mostrata in figura \ref{fig_exaplePosition},
la $position$ e la $mask$ assumerebbero i seguenti valori:
\begin{align*}
  position &= 0000000\; 0000000\; 0000011\; 0001101\; 0001000\; 0000000\; 0000000\\
  mask &= 0000000\; 0000001\; 0000011\; 0011111\; 0001111\; 0000000\; 0000000\;
\end{align*}
\begin{figure}[!ht]
  \centering
  \begin{tikzpicture}
    \tikzstyle{every node}=[font=\LARGE]
    \draw  (0,0) rectangle ++(12,11.5);

    \draw  (1.15,1.13) circle (0.7cm);
    \draw  (2.75,1.13) circle (0.7cm);
    \draw[fill=red!60!white]  (4.35,1.13) circle (0.7cm);
    \draw[fill=yellow!70!white]  (5.95,1.13) circle (0.7cm);
    \draw[fill=yellow!70!white]  (7.55,1.13) circle (0.7cm);
    \draw[fill=red!60!white]  (9.20,1.13) circle (0.7cm);
    \draw  (10.8,1.13) circle (0.7cm);

    \draw  (1.15,2.96) circle (0.7cm);
    \draw  (2.75,2.96) circle (0.7cm);
    \draw[fill=red!60!white]  (4.35,2.96) circle (0.7cm);
    \draw[fill=red!60!white]  (5.95,2.96) circle (0.7cm);
    \draw[fill=yellow!70!white]  (7.55,2.96) circle (0.7cm);
    \draw  (9.20,2.96) circle (0.7cm);
    \draw  (10.8,2.96) circle (0.7cm);

    \draw  (1.15,4.79) circle (0.7cm);
    \draw  (2.75,4.79) circle (0.7cm);
    \draw[fill=red!60!white] (4.35,4.79) circle (0.7cm);
    \draw[fill=yellow!70!white]  (5.95,4.79) circle (0.7cm);
    \draw  (7.55,4.79) circle (0.7cm);
    \draw  (9.20,4.79) circle (0.7cm);
    \draw  (10.8,4.79) circle (0.7cm);

    \draw  (1.15,6.62) circle (0.7cm);
    \draw  (2.75,6.62) circle (0.7cm);
    \draw[fill=yellow!70!white]  (4.35,6.62) circle (0.7cm);
    \draw[fill=yellow!70!white]  (5.95,6.62) circle (0.7cm);
    \draw  (7.55,6.62) circle (0.7cm);
    \draw  (9.20,6.62) circle (0.7cm);
    \draw  (10.8,6.62) circle (0.7cm);

    \draw  (1.15,8.45) circle (0.7cm);
    \draw  (2.75,8.45) circle (0.7cm);
    \draw  (4.35,8.45) circle (0.7cm);
    \draw[fill=red!60!white]  (5.95,8.45) circle (0.7cm);
    \draw  (7.55,8.45) circle (0.7cm);
    \draw  (9.20,8.45) circle (0.7cm);
    \draw  (10.8,8.45) circle (0.7cm);

    \draw  (1.15,10.28) circle (0.7cm);
    \draw  (2.75,10.28) circle (0.7cm);
    \draw  (4.35,10.28) circle (0.7cm);
    \draw  (5.95,10.28) circle (0.7cm);
    \draw  (7.55,10.28) circle (0.7cm);
    \draw  (9.20,10.28) circle (0.7cm);
    \draw  (10.8,10.28) circle (0.7cm);
\end{tikzpicture}
\caption{Posizione di esempio nel gioco per comprendere il funzionamento dei bit}
  \label{fig_exaplePosition}
\end{figure}

Se si vuole ottenere la posizione del giocatore avversario basta eseguire uno
XOR tra i bit della \emph{position} e i bit della \emph{mask}. La posizione
dell'avversario come mostrato in figura infatti risulta essere:
\begin{align*}
  &0000000\; 0000000\; 0000011\; 0001101\; 0001000\; 0000000\; 0000000 \oplus\\
  &0000000\; 0000001\; 0000011\; 0011111\; 0001111\; 0000000\; 0000000 = \;\\
  &0000000\; 0000001\; 0000000\; 0010010\; 0000111\; 0000000\; 0000000\;
\end{align*}
Si noti come alcuni numeri sono mancati, come se ci fosse una riga fantasma 
sopra a quelle visibili. Più avanti verrà spiegato perché è necessario 
utilizzare una riga in più per la rappresentazione.


\subsection{Fare una mossa e annullarla}
Se avessimo usato una semplice matrice per la rappresentazione di una posizione
di gioco, le mosse dei giocatori sarebbero state effettivamente semplici da
memorizzare: bastava infatti modificare la cella della matrice associata. 
Utilizzando però la rappresentazione tramite bit, l'operazione di giocare una
pedina è leggermente più complicata. 

Innanzitutto ci ricordiamo che la variabile \emph{position} rappresenta la 
configurazione del giocatore che dovrà giocare la prossima mossa, mentre la 
variabile \emph{mask} rappresenta le pedine sulla board. Quando un giocatore
decide di fare una mossa le operazioni che vengono eseguite per memorizzarla
sono quelle rappresentate nel seguente speudo-codice.

\begin{algorithm}
  \caption{\textsc{MarkColumn}}
  \begin{algorithmic}
    \Function{markColumn}{$col$}
      \State $position \gets position \oplus mask$
      \State $mask \gets mask | (mask + (1 \ll (col * (Rows + 1))))$
      \\
      \If{\Call{isWinningMove}{}}
        \If{next to play is Player 2}
          \State $gameState \gets $ first player win
        \Else
          \State $gameState \gets $ second player win 
        \EndIf
      \ElsIf{the board if full}
          \State $gameState \gets $ draw
      \EndIf
    \EndFunction
  \end{algorithmic}
\end{algorithm}

Riteniamo che sia necessario dare una spiegazione dei simboli usati:
\begin{itemize}
  \item $\oplus$ è il simbolo di XOR tra bit.
  \item $|$ è il simbolo di OR tra bit.
  \item $\ll$ è il simbolo di shift a sinistra tra bit.
  \item $*$ è il simbolo di moltiplicazione tra numeri interi.
  \item $+$ è il simbolo di somma tra numeri interi.
\end{itemize}
Analizziamo quindi le operazioni sequenzialmente: la prima riga mostra come
venga fatta l'operazione di XOR tra la $position$ e la $mask$. Questo, come già
spiegato in precedenza, permette di ottenere la posizione dell'avversario. 
Nonostante quindi la mossa del giocatore corrente non sia ancora stata segnata, 
la variabile $position$ viene portata a indicare la posizione del giocatore che 
deve muovere al prossimo turno. Avviene quindi nella seconda riga la 
memorizzazione della mossa. Essendo ora la variabile $position$ modificata per
indicare la posizione dell'avversario, è soltanto necessario inserire la mossa
fatta nella $mask$, in quanto è l'unica a memorizzare le posizione di entrambi i 
giocatori. Per fare ciò si sposta un singolo bit fino alla cella base della 
colonna giocata: $1 \ll (col * (Rows + 1)))$, e successivamente lo si somma con
la maschera: $mask + (1 \ll (col * (Rows + 1))))$. In questo modo, essendo i
bit ordinati in senso crescente rispetto alle righe, il bit sommato alla base 
della colonna viene "propagato" fino alla prima cella libera di tale colonna, 
dove quindi il giocatore avrà fatto la sua mossa. Durante la "propagazione" del
bit però, alcune celle potrebbero diventare nulle in quanto in binario $1 + 1 = 
10$. È quindi necessario sovrascrivere quelle celle eseguendo un OR tra la 
$mask$ originale e quella derivata dalla somma con il bit.

Quando invece si vuole annullare l'ultima mossa giocata vengono eseguite operazioni
estremamente simili, solo nell'ordine inverso. In particolare le due operazioni
chiave sono:

\begin{align*}
  &mask = mask \oplus (1 \ll ((Rows + 1) * col + row))\\
  &position = position \oplus mask;
\end{align*}
Nella prima riga viene riportato a 0 il bit riguardo la mossa appena giocata,
mentre nella seconda viene riportata la posizione al giocatore precedente, 
quello cioè che ha annullato la mossa. Si noti che $Rows$ è il numero di colonne
totali nella board, mentre $col$ e $row$ sono rispettivamente la colonna e la
riga in cui l'ultima mossa è stata giocata.

\subsection{Valutazione di una vittoria}
Per il momento l'utilizzo di una rappresentazione tramite bit di una 
configurazione di gioco sembra solo aver complicato maggiormente il codice. 
La scelta però di adottare questa rappresentazione viene completamente 
giustificata da come viene valutata una vittoria.

\subsubsection{Allineare 4 pedine}
Vincere una partita per un giocatore equivale ad allineare 4 pedine consecutive
in verticale, orizzontale o diagonale. Avendo una rappresentazione tramite bit è
possibile fare i controlli necessari solo utilizzando operazioni tra di essi.
L'idea alla base è quella che per allineare 4 pedine, è necessario prima 
allineare 2 coppie da 2 pedine. Se infatti ci troviamo ad avere 2 coppie da 2
pedine sulla stessa colonna, e queste coppie sono adiacenti, allora avremo 
trovato 4 pedine consecutive e uno dei due giocatori avrebbe vinto. Per 
controllare quindi una vittoria, prima si controllano le coppie e 
successivamente si controlla se queste ultime sono allineate.

Prendiamo ora una board $5 \times 5$ in cui in una colonna sono presenti 4 pedine
di uno stesso giocatore, mentre in una ulteriore colonna sono presenti solo 3
pedine del giocatore avversario. La rappresentazione tramite bit risulterebbe 
quindi come segue:
\begin{align*}
  position &= 000000\; 001111\; 000000\; 000000\; 000000\\
  mask &= 000000\; 001111\; 000000\; 000111\; 000000\;
\end{align*}
Innanzitutto controlliamo se esistono delle coppie: per fare ciò basta eseguire
un AND tra la $position$ e la $position$ spostata di un bit a sinistra. Applicato
all'esempio di prima l'operazione risulta:
\begin{align*}
  pairs = &position \land (position \ll 1) =\\
  &000000\; 001111\; 000000\; 000000\; 000000 \land \\
  &000000\; 011110\; 000000\; 000000\; 000000 = \\
  &000000\; 001110\; 000000\; 000000\; 000000\\
\end{align*}
Come si può vedere dal risultato finale, le coppie presenti sono 3 e non 2 come
ci si aspetterebbe. In realtà il risultato è corretto in quanto l'operazione
considera tutte le coppie, anche quelle già parzialmente analizzate. Se infatti
abbia 4 pedine, le coppie saranno formate dalle pedine numero $(0-1)$, $(1-2)$ e 
$(2-3)$.

Infine è necessario controllare che le coppie stesse siano allineate per 
verificare se il giocatore analizzato ha effettivamente vinto. È però necessario
che tali coppie non siano perfettamente adiacenti in quanto se eseguissimo le 
stesse operazioni precedenti considereremmo anche due volte la pedina condivisa 
tra le coppie. Ne consegue che lo shift verso sinistra va eseguito di 2 bit 
invece che 1. Risulta quindi:
\begin{align*}
  win = &pairs \land (pairs \ll 2) =\\
  &000000\; 001110\; 000000\; 000000\; 000000 \land \\
  &000000\; 111000\; 000000\; 000000\; 000000 = \\
  &000000\; 001000\; 000000\; 000000\; 000000\\
\end{align*}
Se il giocatore ha vinto la variabile $win$ sarà diversa da 0, se invece non ha
nessuna sequenza vincente nessun bit sarà uguale a 1 e quindi la variabile sarà
nulla.

Facciamo un ulteriore esempio ora considerando una posizione più complessa, come
la seguente:
\begin{align*}
  position &= 000000 \; 001111 \; 000101 \; 000000 \; 000111\\
  mask &= 000011 \; 001111 \; 001111 \; 000011 \; 011111\\
\end{align*}
Controlliamo quindi le pedine che formano delle coppie e successivamente se tali 
coppie formano una sequenza vincente:
\begin{align*}
  pairs = &position \land (position \ll 1) =\\
  &000000 \; 001111 \; 000101 \; 000000 \; 000111 \land \\
  &000000 \; 011110 \; 001010 \; 000000 \; 001110 = \\
  &000000 \; 001110 \; 000000 \; 000000 \; 000110\\
  \\
  win = &pairs \land (pairs \ll 2) =\\
  &000000 \; 001110 \; 000000 \; 000000 \; 000110 \land \\
  &000000 \; 111000 \; 000000 \; 000000 \; 011000 = \\
  &000000 \; 001000 \; 000000 \; 000000 \; 000000\\
\end{align*}
Il giocatore preso in considerazione ha vinto in quanto $win \neq 0$.\medskip

Per controllare tutte direzioni mancanti le operazioni sono le stesse, con
l'unica differenza riguardo allo shift. Quest'ultimo infatti corrisponde a 1 bit
soltanto quando si vuole controllare le pedine verticalmente, mentre deve
variare se si vogliono controllare le altre direzioni. Lo speudo-codice per il
controllo di una vittoria con 4 pedine è lasciato di seguito.

\begin{algorithm}
  \caption{isWinningMove4} 
  \begin{algorithmic}
    \Function{isWinningMove4}{$position$}
      \State $shift \gets Rows + 1$
      \Comment{Controllo orizzontale}
      \State $pair \gets position \land (position \ll shift)$
      \State $win \gets pair \land (pair \ll (2 * shift))$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $pair \gets position \land (position \ll 1)$
      \Comment{Controllo verticale}
      \State $win \gets pair \land (pair \ll 2)$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $shift \gets Rows$
      \Comment{Controllo diagonale $\backslash$} 
      \State $pair \gets position \land (position \ll shift)$
      \State $win \gets pair \land (pair \ll (2 * shift))$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $shift \gets Rows + 2$
      \Comment{Controllo diagonale $\slash$}
      \State $pair \gets position \land (position \ll shift)$
      \State $win \gets pair \land (pair \ll (2 * shift))$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State \Return{false}
      \Comment{Il giocatore non ha vinto, la partita continua}
    \EndFunction
  \end{algorithmic}
\end{algorithm}

Come è possibile notare, per controllare una vittoria non sono stati utilizzati
loop, ma soltanto operazioni tra bit.

\subsubsection{Allineare 5 pedine}
Essendo presenti nel gioco configurazioni in cui la vittoria è data da 5 pedine
allineate e non più da 4 è necessario fare un piccola modifica al codice. Per 
controllare infatti che 5 pedine siano allineate, si controlla prima che 4 lo 
siano e successivamente si controlla che ai lati di quelle 4 ci sia un'ulteriore
pedina. Prendiamo come esempio la seguente situazione:
\begin{align*}
  position &= 000000\; 011111\; 000000\; 000000\; 000000\\
  mask &= 000000\; 011111\; 000000\; 001111\; 000000\;
\end{align*}
Possiamo notare che sulla quarta colonna sono presenti 5 pedine allineate. 
Eseguiamo quindi gli stessi passaggi illustrati in precedenza per controllare 
che 4 pedine siano allineate:
\begin{align*}
  pairs = &position \land (position \ll 1) =\\
  &000000\; 011111\; 000000\; 000000\; 000000 \land \\
  &000000\; 111110\; 000000\; 000000\; 000000 = \\
  &000000\; 011110\; 000000\; 000000\; 000000\\
  \\
  quaterns = &pairs \land (pairs \ll 2) =\\
  &000000\; 011110\; 000000\; 000000\; 000000 \land \\
  &000001\; 111000\; 000000\; 000000\; 000000 = \\
  &000000\; 011000\; 000000\; 000000\; 000000\\
\end{align*}
Nell'ultima variabile vediamo 2 bit a 1. Questo significa che sono stati trovati
due gruppi da 4 pedine consecutive: $(0-1-2-3-4)$ e $(1-2-3-4-5)$. È però 
necessario aggiungere un'ulteriore operazione per verificare se 5 pedine sono
consecutive, o meglio se esiste un'ulteriore pedina attaccata a un gruppo da 4:
\begin{align*}
  win = &position \land (quaterns \ll 1) =\\
  &000000\; 011111\; 000000\; 000000\; 000000 \land \\
  &000000\; 110000\; 000000\; 000000\; 000000 = \\
  &000000\; 010000\; 000000\; 000000\; 000000 = \\
\end{align*}
Come visto in precedenza se $win \neq 0$ il giocatore ha vinto. Lo speudo-codice
è lasciato di seguito.

\begin{algorithm}
  \caption{isWinningMove5} 
  \begin{algorithmic}
    \Function{isWinningMove5}{$position$}
      \State $shift \gets Rows + 1$
      \Comment{Controllo orizzontale}
      \State $pair \gets position \land (position \ll shift)$
      \State $quaterns \gets pair \land (pair \ll (2 * shift))$
      \State $win \gets position \land (quaterns \ll shift)$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $pair \gets position \land (position \ll 1)$
      \Comment{Controllo verticale}
      \State $quaterns \gets pair \land (pair \ll 2)$
      \State $win \gets position \land (quaterns \ll 1)$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $shift \gets Rows$
      \Comment{Controllo diagonale $\backslash$} 
      \State $pair \gets position \land (position \ll shift)$
      \State $quaterns \gets pair \land (pair \ll (2 * shift))$
      \State $win \gets position \land (quaterns \ll shift)$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State $shift \gets Rows + 2$
      \Comment{Controllo diagonale $\slash$}
      \State $pair \gets position \land (position \ll shift)$
      \State $quaterns \gets pair \land (pair \ll (2 * shift))$
      \State $win \gets position \land (quaterns \ll shift)$
      \If{$win \neq 0$}
        \State \Return{true}
      \EndIf
      \\
      \State \Return{false}
      \Comment{Il giocatore non ha vinto, la partita continua}
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\subsubsection{La riga fantasma}
Fino a questo momento abbiamo sempre utilizzato una riga in più rispetto alla
board che volevamo rappresentare. Per rappresentare infatti tutte le 
configurazioni di un gioco con dimensioni $6 \times 7$ avevamo necessità di 
utilizzare $7 \cdot 7 = 49$ bit. La ragione dell'impiego di una riga aggiuntiva
è dovuto a dei falsi positivi che si verrebbero a creare se non la impiegassimo
nella rappresentazione. Consideriamo la seguente posizione di una board 
$5 \times 5$ rappresentata senza la riga aggiuntiva:
\begin{align*}
  position &= 01000\; 00001\; 11100\; 00001\; 00001\\
  mask &= 11111\; 00001\; 11111\; 00001\; 00001\;
\end{align*}
Nonostante non ci sia nessuna sequenza vincente, i passaggi illustrati in 
precedenza produrrebbero un falso positivo:
\begin{align*}
  pairs = &position \land (position \ll 1) =\\
  &01000 \; 00001 \; 11100 \; 00001 \; 00001 \land \\
  &10000 \; 00011 \; 11000 \; 00010 \; 00010 = \\
  &00000 \; 00001 \; 11000 \; 00000 \; 00000 = \\
  \\
  win = &pairs \land (pairs \ll 2) =\\
  &00000 \; 00001 \; 11000 \; 00000 \; 00000 \land \\
  &00000 \; 00111 \; 00000 \; 00000 \; 00000 = \\
  &00000 \; 00001 \; 00000 \; 00000 \; 00000 \\
\end{align*}
Come possiamo notare la variavile $win$ è diversa da 0 e quindi dovrebbe esserci
una vittoria, questo però non è affatto vero. Con l'impiego della riga aggiuntiva
è però possibile evitare errori di valutazione:
\begin{align*}
  position = &001000\; 000001\; 011100\; 000001\; 000001\\
  mask = &011111\; 000001\; 011111\; 000001\; 000001\; \\
  \\
  pairs = &position \land (position \ll 1) =\\
  &001000 \; 000001 \; 011100 \; 000001 \; 000001 \land \\
  &010000 \; 000010 \; 111000 \; 000010 \; 000010 = \\
  &000000 \; 000000 \; 011000 \; 000000 \; 000000 = \\
  \\
  win = &pairs \land (pairs \ll 2) =\\
  &000000 \; 000000 \; 011000 \; 000000 \; 000000 \land \\
  &000000 \; 000001 \; 100000 \; 000000 \; 000000 = \\
  &000000 \; 000000 \; 000000 \; 000000 \; 000000 \\
\end{align*}

% \subsection{Controllo di una casella specifica}

\subsection{Limitazioni rappresentative}
Compresa la necessità della riga fantasma per la rappresentazione di una 
posizione è necessari chiedersi in quali configurazioni di gioco è possibile
utilizzare la rappresentazione tramite bit. Come già visto i bit necessari per
rappresentare una board di $M$ righe e $N$ colonne sono:
\begin{equation*}
  bits = (M + 1) \cdot N
\end{equation*}
I calcolatori attuali sono basati su \emph{word} da 64 bit. Questo implica che
si possono rappresentare soltanto board fino a $8 \times 7 \xrightarrow{} 63\; 
bits$. Per questo motivo il giocatore è diviso in due: il primo dedicato a tutte 
le board che possono essere rappresentate tramite bit, e il secondo dedicato a 
tutte le rimanenti.

\subsection{Hash di una posizione}
Utilizzando una Transposition table è necessario poter calcolare l'hash di una
determinata posizione. Utilizzando la rappresentazione tramite bit questo è 
facilmente ottenibile sommando la posizione alla maschera:
\begin{equation*}
  hash = position + mask
\end{equation*}

\section{Zobrist: hash per Big}
L'algoritmo di Zobrist è una tecnica largamente utilizzata nella programmazione
di algoritmi di giochi da tavolo, e serve in particolare a calcolare un valore
hash per ogni singola configurazione di gioco.

L'idea alla base dell'algoritmo è quella di rappresentare uno stato di gioco
come un numero intero, ottenuto dalla combinazione di valori associati a 
singoli pezzi in specifiche posizioni. In particolare esiste un numero associato
a ogni cella della board, rispettivamente per il giocatore uno o il giocatore 
due. L'hash di una posizione è quindi ottenuto combinando tutti i numeri 
relativi alle pedine in gioco e relativi alla loro posizione attraverso 
l'operazione di XOR.\medskip

Durante l'inizializzazione del giocatore è quindi necessario costruire la 
matrice in cui verranno salvati i valori associati alle pedine e alla loro 
posizione. In particolare per ogni cella, se è vuota il valore è 0, se no 
esistono due valori distinti in base a quale giocatore la occupa con una pedina.

Dato l'hash di una posizione, se si esegue una mossa, per trovare l'hash della
nuova posizione è semplicemente richiesto fare uno XOR tra il vecchio hash e il
valore associato alla pedina giocata nella cella interessata. Per annullare la
mossa il procedimento è il medesimo.

\begin{algorithm}
  \caption{Zobrist}
  \begin{algorithmic}
    \State $position$
    \Comment{Intero a 64 bit che corrisponde all'hash}
    \State $table[][]$
    \Comment{Matrice di interi}
    \\
    \Function{initZobrist}{}
      \State $position \gets 0$
      \State $table[][]$ matrix of dimensions $2 * Rows$ and $2 * Columns$

      \For{every cell \textbf{in} table}
      \State $cell \gets $ a random number
      \EndFor
    \EndFunction
    \\
    \Function{makeMove}{$row$, $col$}
      \If{player one had played last}
        \State $position = position \oplus table[row][col]$
      \Else
        \State $position = position \oplus table[Rows + row][Columns + col]$
      \EndIf
    \EndFunction
  \end{algorithmic}
\end{algorithm}

\section{Costo computazionale}
Definiamo:
\begin{itemize}
  \item $b$ come \emph{fattore di diramazione}, ovvero il numero medio di
    sottoalberi appartenenti a ogni nodo.
  \item $d$ come la profondità a cui viene svolta la ricerca.
\end{itemize}

Se si analizza il costo computazionale risulta che il metodo principale, ovvero 
quello adibito alla scelta della mossa, ha complessità  dominata  dal costo di
\textsc{IterativeDeepening} e \textsc{PVS}. È facile osservare però che il primo 
ha complessità trascurabile rispetto al secondo in quanto il costo totale viene
assorbito dall'ultima ricerca a profondità massima eseguita da PVS. 

Il costo della ricerca è compreso tra quello di \textsc{MiniMax} $O(b^d)$, 
dove tutti i rami vengono analizzati, e quello di \textsc{AlphaBeta} 
\emph{con ordinamento perfetto} $O(\sqrt{b^d})$, dove soltanto i nodi 
strettamente necessari vengono visitati.\medskip

Nella valutazione del costo complessivo è necessario anche quantificare 
il costo dell'euristica, in quanto viene invocata al raggiungimento della 
profondità richiesta o al raggiungimento di un nodo terminale. Quest'ultima, 
controllando tutte le diagonali e le righe, ha costo $O(\textrm{max}\{Rows \cdot 
Columns, (Rows + Columns) \cdot \sqrt{Columns^2 + Rows^2}\}) = O((Rows + Columns) 
\cdot \sqrt{Columns^2 + Rows^2})$. Si noti che $Rows + Columns$ è una soglia 
massima del numero di diagonali presenti, il numero reale è inferiore. Inoltre 
$\sqrt{Columns^2 + Rows^2}$ è la lunghezza della diagonale massima.\medskip

Giocare una mossa ha costo costante nelle board che utilizzano la rappresentazione 
tramite bit. Il costo invece per la rappresentazione usata nelle board rimanenti
è dato dal controllo sull'ultima mossa se ha generato una vittoria. Questi 
controlli sono proporzionali alla lunghezza della sequenza che porta a una 
vittoria.\medskip

Il costo per la generazione delle chiavi di hash relative a una posizione e 
l'accesso alla tabella delle trasposizioni è costante.

\section{Fonti consultate}
La fonte principale per tutti gli algoritmi implementati: 
\href{chessprogramming.org}{\texttt{chessprogramming.org}}\medskip

Riguardo la rappresentazione tramite bit e la valutazione di una vittoria in 
tempo costante abbia preso spunto sia da \href{http://blog.gamesolver.org/solving-connect-four/06-bitboard/}{\texttt{blog.gamesolver.org}},
sia da \href{https://towardsdatascience.com/creating-the-perfect-connect-four-ai-bot-c165115557b0}{\texttt{towardsdatascience.com}}.
Nonostante ciò si è comunque dovuta fare un lavoro di generalizzazioni in quanto 
le fonti citate riguardano soltanto la configurazione classica di Forza 4.

\end{document}