<file_sep># Uni
My work for uni
<file_sep># Graph coloring

Goal : coloring the vertices of a graph such that no two adjacent vertices are of the same color

Condition : Use lp_solve API with cpp program, take in entry a graph (dimacs format) and resolve it.
<file_sep>package infection;

/**
 * Classe qui représente l'intelligence artificielle associée à un joueur Le
 * raisonnement se fait avec l'algorithme minMax. Le but est de trouver le
 * meilleur coup à jouer en fonction des suivants.
 */
public class IA {

	/**
	 * Définition du joueur qui raisonne, celui pour qui on doit avoir le score
	 * maximal.
	 */
	protected int joueurRaisonne;

	/**
	 * Booléan pour utilisation de l'élégage alphabeta
	 */
	protected boolean cut;

	/**
	 * Nombre d'appels de MinMax ou de Alphabeta
	 */
	public static long cptAppels = 0;

	/**
	 * Définition de constantes pour les algorithmes qui nécessitent des bornes
	 * inatteignables.
	 */
	private static final int MINUS_INFINITE = -10;
	private static final int PLUS_INFINITE = 10;

	/**
	 * Constructeur avec paramètre, on associe un joueur à l'IA
	 * 
	 * @param joueurRaisonne Le joueur auquel on s'intérresse
	 */
	public IA(int joueurRaisonne, boolean cut) {
		this.joueurRaisonne = joueurRaisonne;
		this.cut = cut;
	}

	/**
	 * Méthode qui permet de trouver le noeud qui donne le plus de chance de gagner.
	 * On parcours tout le graphe des possibilités en appelant au niveau de
	 * profondeur 2 l'algorithme minMax. Le meilleur coup est renvoyé.
	 * 
	 * @param s          L'état du plateau courant
	 * @param profondeur La profondeur de recherche de l'IA
	 * @return Le Move qui donne le plus de chance de gagner la partie
	 */
	public Move decide(State s, int profondeur) {
		double b = MINUS_INFINITE;
		double m = 0;
		State snew = null;
		Move c = new Move(0, 0, 0, 0, false);
		for (Move mv : s.getMoves(s.getCurrentPlayer())) {
			snew = s.play(mv);
			if (this.cut) {
				m = alphabeta(snew, MINUS_INFINITE, PLUS_INFINITE, profondeur - 1);
			} else {
				m = miniMax(snew, profondeur - 1);
			}
			if (b < m) {
				b = m;
				c = mv;
			}
		}
		return c;
	}

	/**
	 * Algorithme minMax qui parcours l'ensemble des possibilités de l'arbre de
	 * recherche et récupère la valeur qui donne le plus de chance de gagner la
	 * partie pour le joueur qui raisonne.
	 * 
	 * @param s          L'état actuel du plateau
	 * @param profondeur La profondeur de recherche de l'algorithme
	 * @return La meilleur valeur de la fonction d'évaluation
	 */
	private double miniMax(State s, int profondeur) {
		IA.cptAppels++;
		State snew = null;
		double b, m;
		// Si le jeu est terminé, on ne peut pas descendre plus bas dans la profondeur
		if (profondeur == 0 || s.isFinished()) {
			// Score du joueur qui raisonne
			return s.getScore(this.joueurRaisonne);
		} else {
			if (s.getCurrentPlayer() == this.joueurRaisonne) {
				b = MINUS_INFINITE;
				for (Move mv : s.getMoves(s.getCurrentPlayer())) {
					snew = s.play(mv);
					m = miniMax(snew, profondeur - 1);
					b = b < m ? m : b;
				}
			} else {
				b = PLUS_INFINITE;
				for (Move mv : s.getMoves(s.getCurrentPlayer())) {
					snew = s.play(mv);
					m = miniMax(snew, profondeur - 1);
					b = b > m ? m : b;
				}
			}
			return b;
		}
	}

	/**
	 * Algorithme Alphabeta, version optimisée de MinMax avec élégage des branches
	 * qui ne rapportent pas de points au joueur. L'arbre des possibilités est
	 * réduit.
	 * 
	 * @param s          Le plataeu de jeu courant
	 * @param alpha      Valeur minimun pour le joueur qui raisonne
	 * @param beta       Valeur maximum pour le joueur qui raisonne
	 * @param profondeur Profondeur de recherche de l'algorithme
	 * @return La valeur du noeud qui apporte le plus au joueur
	 */
	private double alphabeta(State s, double alpha, double beta, int profondeur) {
		IA.cptAppels++;
		double m = 0;
		if (profondeur == 0 || s.isFinished()) {
			return s.getScore(this.joueurRaisonne);
		} else {
			if (s.currentPlayer == this.joueurRaisonne) {
				for (Move mv : s.getMoves(s.currentPlayer)) {
					m = this.alphabeta(s.play(mv), alpha, beta, profondeur - 1);
					alpha = alpha > m ? alpha : m;
					if (alpha >= beta) {
						return alpha;
					}
				}
				return alpha;
			} else {
				for (Move mv : s.getMoves(s.getCurrentPlayer())) {
					m = this.alphabeta(s.play(mv), alpha, beta, profondeur - 1);
					beta = beta < m ? beta : m;
					if (alpha >= beta) {
						return beta;
					}
				}
				return beta;
			}
		}
	}
}
<file_sep>package infection;

/**
 * Classe représentant un mouvement de pion. La position de départ, la position
 * d'arrivée sous forme de coordonnées d'entiers. Le type de mouvement est un
 * booléen.
 */
public class Move {

	/** Couple position départ */
	protected int startX;
	protected int startY;

	/** Couple position d'arrivée */
	protected int endX;
	protected int endY;

	/**
	 * Type de mouvement possible du pion :
	 * <ul>
	 * <li>True : dupliquer</li>
	 * <li>false ; déplacement</li>
	 */
	protected boolean type;

	/**
	 * Constructeur avec paramètres, coordonnées du point de départ et du point
	 * d'arrivée. Le type est spécifié également.
	 * 
	 * @param x1 Position x de départ
	 * @param y1 Position y de départ
	 * @param x2 Position x d'arrivée
	 * @param y2 Position y d'arrivée
	 * @param type Type de mouvement
	 */
	public Move(int x1, int y1, int x2, int y2, boolean type) {
		this.startX = x1;
		this.startY = y1;
		this.endX = x2;
		this.endY = y2;
		this.type = type;
	}

	@Override
	public String toString() {
		return "(" + this.startX + "," + this.startY + ");(" + this.endX + "," + this.endY + ") : " + this.type + "\n";
	}
}
<file_sep># Game and rules

Infection set

It's a board game with two players. A field of m * n squares is empty. Each player (black and white) has a checker in the opposite corners of the board.

Each player plays in turn, one checker can move two squares in the four cardinal directions and into an empty square (even over another checker). Or a checker can duplicate itself in one of the four cardinal positions if no checker is already there. After duplicating, it changes the colour of the pieces that touch it to its own colour. The game is over if one of the two players has no more possible moves, it has run out of checkers, or the board is full.

## Resolution

The algorithm used is that of minimax and alphabeta (pruning of minimax). The search depth is given in the command line.
The score function of a player is the proportion of pieces of his color on the board compared to the total number of pieces.<file_sep>#include <lpsolve/lp_lib.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <math.h>
#include <string>
#include <sstream> 
#include <cstdlib>
// g++ Mycielski.cpp -llpsolve55 -lcolamd -ldl -o Mycielski
// ./Mycielski graph.dimacs

// Need lp_solve and liblpsolve55-dev to compile and execute

void vider_row(REAL row[], const int& taille);

int main(int argc, char* argv[])
{
	lprec* lp;
	int nbNoeuds = 0, nbArcs = 0;
	if(argv[1] == nullptr)
	{
		std::cout << "Fichier graphe en paramètre nécessaire." << std::endl;
		exit(EXIT_FAILURE);
	}
	std::ifstream fichier (argv[1]);
	if (!fichier.is_open())
	{
		std::cout << "Impossible d'ouvrir le fichier du graphe." << std::endl;
		exit(EXIT_FAILURE);
	}
	std::string ligne;
	while (getline(fichier, ligne))
	{
		std::string mot;
		std::istringstream iss(ligne);
		iss >> mot;
		if (mot == "p")
		{
			iss >> mot;
			iss >> mot;
			nbNoeuds = stoi(mot);
			iss >> mot;
			nbArcs = stoi(mot);
			break;
		}
	}
	lp = make_lp(0, nbNoeuds*nbNoeuds+nbNoeuds);
	REAL row[nbNoeuds*nbNoeuds+nbNoeuds + 1];
	vider_row(row, nbNoeuds*nbNoeuds+nbNoeuds+1);
	for (int i = 1; i <= (nbNoeuds*nbNoeuds+nbNoeuds); i++)
	{
		row[i] = 1.0;
		set_int(lp, i, true);
		add_constraint(lp, row, GE, 0);
		add_constraint(lp, row, LE, 1);
		row[i] = 0.0;
	}
	for (int i = 0; i < nbNoeuds; i++)
	{
		for (int j = 0; j < nbNoeuds; j++)
		{
			row[i*nbNoeuds+j+1] = 1.0;
		}
		add_constraint(lp, row, EQ, 1);
		vider_row(row, nbNoeuds*nbNoeuds+nbNoeuds+1);
	}
	while (getline(fichier, ligne))
	{
		std::string mot;
		std::istringstream iss(ligne);
		iss >> mot;
		if (mot == "e")
		{
			iss >> mot;
			int premierNode = stoi(mot);
			iss >> mot;
			int secondNode = stoi(mot);

			for (int i = 1; i <= nbNoeuds; i++)
			{
				row[premierNode*nbNoeuds-nbNoeuds+i] = 1.0;
				row[secondNode*nbNoeuds-nbNoeuds+i] = 1.0;
				row[(nbNoeuds*nbNoeuds+1)+i] = -1.0;
				add_constraint(lp, row, LE, 0);
				vider_row(row, nbNoeuds*nbNoeuds+nbNoeuds+1);
			}
		}
	}
	for (int i = 0; i < nbNoeuds; i++)
	{
		row[nbNoeuds*nbNoeuds+i+1] = 1.0;
	}
	set_obj_fn(lp, row);
	vider_row(row, nbNoeuds*nbNoeuds+nbNoeuds+1);

	if (solve(lp) != 0)
	{
		fprintf(stderr, "INFEASIBLE\n");
		return(1);
	}
	else
	{
		get_variables(lp, row);
		int cptCol = 0;
		for (int i = 0; i < nbNoeuds ; i++)
		{
			for (int j = 1; j < nbNoeuds; j++)
			{
				cptCol++;
				if(row[i*nbNoeuds+j] == 1) {break;};
			}
			std::cout << "Noeud" << (i+1) << ", couleur :" << cptCol << std::endl;
			cptCol = 0;
		}
		print_objective(lp);
	}
	return(0);
}

void vider_row(REAL row[], const int& taille)
{
	for (int i = 0; i < taille; i++)
	{
		row[i] = 0.0;
	}
}

