Mini_rapport - TP - Copie

Mini Projet

Algorithme Min Max

Tic Tac Toe

Nom&Prénom: Boujmil Sarra Nom&Prénom: Shili Mohamed Propser Par : Dr. Lilia RajebGroupe : Master De recherche Informatique SPI

Date: 10/12/2013

Université De Sousse

Institut Supérieur des Sciences Applique et de Technologie de Sousse

Introduction

L'algorithme MINIMAX, dû à Von Neumann, à comme but l'élaboration d'une stratégie

optimale pour le joueur MAX.

À chaque tour le joueur MAX va choisir le coup qui va maximiser son score, tout en

minimisant les bénéfices de l'adversaire. Ces bénéfices sont évalués en termes de la

fonction d'évaluation statique utilisée pour apprécier les positions pendant le jeu.

Exemple. On considère que pendant une partie de Tic Tac Toe on est arrivé dans la

position présentée dans la racine de l`arbre de la figure 1 .On voit que le premier niveau

est coloré en jaune, donc c'est au tour du joueur X (le joueur MAX) de jouer.

Figure 1 : Exemple d`analyse pendant une partie de Tic Tac Toe

Les niveaux de décision pour le joueur MIN sont colorés en bleu et les positions

terminales sont présentées dans des zones vertes, ayant écrit au-dessous les valeurs de la

fonction d`évaluation statique.

Page 2

Interface Graphique de Jeu Tic Tac Toe

Figure 2 : Interface principale

Figure 3 : Partie en cours

Page 3

Figure 4: Nouvelle Partie

import javax.swing.*;

import java.awt.image.*;

import java.awt.event.*;

import java.awt.*;

import java.util.*;

import java.net.*;

public class TicTacToe extends JApplet implements ActionListener, Runnable

{

Thread Go;

Thread Player;

int PlayerMove = -1;

final static char vWinPattern[][] = new char[16][9];

char vTicTac[] = new char[9];

boolean vWait = false;

boolean btnEmpty[] = new boolean[9] ;

int ptsMoi = 0;

Page 4

int ptsVous = 0;

BorderLayout layout1 = new BorderLayout(35,10);

GridLayout layout2 = new GridLayout(3,3,0,0);

GridLayout layout3 = new GridLayout(5,1,10,10);

FlowLayout layout4 = new FlowLayout();

FlowLayout layout5 = new FlowLayout();

JLabel lblTitle = new JLabel("TIC TAC TOE !", JLabel.LEFT);

Font titleFont = new Font("Tahoma", 0, 24);

Font pts = new Font("Tahoma", 1, 14);

Font lblFnt = new Font("Tahoma", 0, 15);

JLabel lblMoi = new JLabel("Moi ", JLabel.RIGHT);

JLabel lblVous = new JLabel("Vous ", JLabel.RIGHT);

JLabel lblMoiPts = new JLabel(" 0 ", JLabel.LEFT);

JLabel lblVousPts = new JLabel(" 0 ", JLabel.LEFT);

JButton btnInit = new JButton("Initialiser");

Image ImageN;

Image ImageX;

Image ImageO;

JButton check[] = new JButton[9];

JPanel pnlBoard = new JPanel();

JPanel pnlRight = new JPanel();

JPanel pnlUp = new JPanel();

JPanel pnlDown = new JPanel();

JLabel lblMessage = new JLabel("Bienvenue au Tic Tac Toe !", JLabel.CENTER);

static int MiniMax(char[] vPattern)

{

Random rnd = new Random();

boolean NotEmpty = false;

for (int rs = 0; rs <=8; rs++)

{

Page 5

if (vPattern[rs] != 'n')

NotEmpty = true;

}

if (!NotEmpty)

{

return rnd.nextInt(8);

}

//***************************************************

char Temp1[] = new char[9];






int i = 0;

int ii = 0;

int iii = 0;

int iiii = 0;

int iiiii = 0;

int iiiiii = 0;

int p[] = new int[8];

int pp[] = new int[7];

int ppp[] = new int[6];

int pppp[] = new int[5];

int ppppp[] = new int[4];

int pppppp[] = new int[3];

int r = -1;

int rr = -1;

int rrr = -1;

int rrrr = -1;

Page 6

int rrrrr = -1;

int rrrrrr = -1;

int Min1;

int Min2;

int Min3;

int Max1;

int Max2;

int Max3;

int v;

int gst = -1;

//********************************

for (i = 0; i <=8; i++)

{

if (vPattern[i] == 'n')

{

r = r + 1;

p[r] = i;

}

}

//loop1

Max1 = 2;

for (i = 0; i <= r; i++)

{

For (v = 0; v <=8; v++)

{

Temp1[v] = vPattern[v];

}

Temp1[p[i]] = 'o';

v = CheckGagnant(Temp1);

if (v == 1 || v == 0)

Page 7

{

Max1 = -v;

gst = p[i];

break;

}

rr = -1;

//*********************************

for (ii = 0; ii <=8; ii++)

{

if (Temp1[ii] == 'n')

{

rr = rr + 1;

pp[rr] = ii;

} }

//loop2

Min1 = -2;

for (ii = 0; ii <= rr; ii++)

{

for (v = 0; v <= 8; v++) {

Temp2[v] = Temp1[v];

}

Temp2[pp[ii]] = 'x';


if (v == 1 || v == 0)

{

Min1 = v;

break;

}

rrr = -1;

Page 8

//***********************************

for (iii = 0; iii <= 8; iii++)

{

if (Temp2[iii] == 'n')

{

rrr = rrr + 1;

ppp[rrr] = iii;

}}

//loop3

Max2 = 2;

for (iii = 0; iii <= rrr; iii++)

{

for (v = 0; v <= 8; v++)

{


}

Temp3[ppp[iii]] = 'o';


if (v == 1 || v == 0)

{

Max2 = -v;

break;

}

rrrr = -1;

//***************************************

for (iiii = 0; iiii <= 8; iiii++)

{

if (Temp3[iiii] == 'n')

{

rrrr = rrrr + 1;

Page 9

pppp[rrrr] = iiii;

}

}

//loop4

Min2 = -2;

for (iiii = 0; iiii <= rrrr; iiii++)

{

for (v = 0; v <= 8; v++)

{


}

Temp4[pppp[iiii]] = 'x';


if (v == 1 || v == 0)

{

Min2 = v;

break; }

rrrrr = -1;

//***************************************

for (iiiii = 0; iiiii <= 8; iiiii++)

{

if (Temp4[iiiii] == 'n') {

rrrrr = rrrrr + 1;

ppppp[rrrrr] = iiiii;

} }

//loop5

Max3 = 2;

for (iiiii = 0; iiiii <= rrrrr; iiiii++)

{

for (v = 0; v <= 8; v++)

Page 10

{ Temp5[v] = Temp4[v];

}

Temp5[ppppp[iiiii]] = 'o';


if (v == 1 || v == 0)

{

Max3 = -v;

break;

}

rrrrrr = -1;

//***************************************

for (iiiiii = 0; iiiiii <= 8; iiiiii++)

{

if (Temp5[iiiiii] == 'n')

{

rrrrrr = rrrrrr + 1;

pppppp[rrrrrr] = iiiiii;

} }

//loop6

Min3 = -2;

for (iiiiii = 0; iiiiii <= rrrrrr; iiiiii++)

{ for (v = 0; v <=8; v++)

{ Temp6[v] = Temp5[v];

}

Temp6[pppppp[iiiiii]] = 'x';


if (v == 1)

{

Min3 = 1;

break;

Page 11

}

else

{

if (v > Min3)

Min3 = v;

} }

//***********************************************

if (Min3 < Max3)

Max3 = Min3;

}

//***********************************************

if (Max3 > Min2)

Min2 = Max3;

}

//*******************************************

if (Min2 < Max2)

Max2 = Min2;

}

//***********************************************

if (Max2 > Min1)

Min1 = Max2;

}

//************************************************

if (Min1 < Max1)

{

Max1 = Min1;

gst = p[i];

} }

//****************************************************

return gst;

Page 12

public void run()

{

if (Thread.currentThread() == Go)

PicComp(MiniMax(vTicTac));

else if (Thread.currentThread() == Player)

PicClick(PlayerMove);

}

public void PicClick(int Index)

{

lblMessage.setText("Partie en cours...");

if (vWait)

{

check[Index].setIcon(new ImageIcon(ImageX));

check[Index].setCursor(new Cursor(Cursor.DEFAULT_CURSOR));

vTicTac[Index] = 'x';

btnEmpty[Index] = false;

Chk();

}}

public void PicComp(int Index)

{

lblMessage.setText("Partie en cours...");

check[Index].setIcon(new ImageIcon(ImageO));

check[Index].setCursor(new Cursor(Cursor.DEFAULT_CURSOR));

vTicTac[Index] = 'o';

btnEmpty[Index] = false;

Chk();

}

public void Chk()

{ int v = CheckGagnant(vTicTac);

if (v == 1)

Page 13

{

lblMessage.setText("J'ai gagne!");

play(getCodeBase(), "sounds/laugh.wav");

ptsMoi += 1;

vWait = true;

try {

Thread.sleep(1600);

} catch (InterruptedException e) { }

RefreshCont();

}

else if (v == 0)

{

lblMessage.setText("Partie nulle !!!");

play(getCodeBase(), "sounds/glass.wav");

try {

Thread.sleep(1600);

} catch (InterruptedException e) { }

RefreshCont();

}

if (vWait)

{ vWait = false;

Go = null;

Go = new Thread(this);

Go.start();

}else

{ vWait = true;

}}

static int CheckGagnant(char[] vPattern)

{

int result = -1;

Page 14

if (vPattern[0] != 'n' && vPattern[1] != 'n' && vPattern[2] != 'n' &&

vPattern[3] != 'n' && vPattern[4] != 'n' && vPattern[5] != 'n' &&

vPattern[6] != 'n' && vPattern[7] != 'n' && vPattern[8] != 'n')

{

result = 0;

}

for (int i = 0; i <=15; i++)

{

if (CompareP(vWinPattern[i], vPattern))

{

result = 1;

}}

return result;

}

static boolean CompareP(char[] vPatternA, char[] vPatternB)

{

boolean v = true;

for (int i = 0; i <= 8; i++)

{

if (vPatternA[i] != vPatternB[i] && vPatternB[i] != 'w' && vPatternA[i] != 'w')

v = false;

}

return v;

}

public void RefreshCont()

{

for (int i = 0; i <=8; i++)

{

check[i].setIcon(new ImageIcon(ImageN));

check[i].setCursor(new Cursor(Cursor.HAND_CURSOR));

Page 15

vTicTac[i] = 'n';

lblMoiPts.setText(" " + String.valueOf(ptsMoi) + " ");

lblVousPts.setText(" " + String.valueOf(ptsVous) + " ");

btnEmpty[i] = true;

}}

public TicTacToe()

{ setSize(420,350);

vWinPattern[0][0] = 'o'; vWinPattern[0][1] = 'o'; vWinPattern[0][2] = 'o';

vWinPattern[0][3] = 'w'; vWinPattern[0][4] = 'w'; vWinPattern[0][5] = 'w';


vWinPattern[1][0] = 'x'; vWinPattern[1][1] = 'x'; vWinPattern[1][2] = 'x';















vWinPattern[6][0] = 'x'; vWinPattern[6][1] = 'w'; vWinPattern[6][2] = 'w';



vWinPattern[7][0] = 'o'; vWinPattern[7][1] = 'w'; vWinPattern[7][2] = 'w';


Page 16


vWinPattern[8][0] = 'w'; vWinPattern[8][1] = 'o'; vWinPattern[8][2] = 'w';



vWinPattern[9][0] = 'w'; vWinPattern[9][1] = 'x'; vWinPattern[9][2] = 'w';



vWinPattern[10][0] = 'w'; vWinPattern[10][1] = 'w'; vWinPattern[10][2] = 'o';



vWinPattern[11][0] = 'w'; vWinPattern[11][1] = 'w'; vWinPattern[11][2] = 'x';















Container pane = getContentPane();

pane.setBackground(new Color(230,230,255));

pane.setLayout(layout1);

pnlBoard.setLayout(layout2);

pnlRight.setLayout(layout3);

Page 17

for (int i = 0; i <= 8; i++)

{

check[i] = new JButton();

pnlBoard.add(check[i]);

check[i].setBackground(new Color(205,205,255));

check[i].setFocusable(false);

check[i].addActionListener(this);

check[i].setName(String.valueOf(i));

btnEmpty[i] = false;

}

check[0].setBorder(BorderFactory.createMatteBorder(0,0,1,1,new Color(0,0,150)));









pnlBoard.setBorder(BorderFactory.createEtchedBorder(Color.white, new Color(0,0,170)));

pane.add(pnlBoard, BorderLayout.CENTER);

lblTitle.setForeground(new Color(0,0,150));

lblMessage.setForeground(new Color(0,0,150));

lblTitle.setFont(titleFont);

lblMessage.setFont(titleFont);

pane.add(lblTitle, BorderLayout.NORTH);

pane.add(lblMessage, BorderLayout.SOUTH);

lblMoi.setFont(lblFnt);

lblVous.setFont(lblFnt);

lblMoiPts.setFont(pts);

Page 18

lblVousPts.setFont(pts);

btnInit.setFont(lblFnt);

lblMoiPts.setBorder(BorderFactory.createLineBorder(Color.black));

lblVousPts.setBorder(BorderFactory.createLineBorder(Color.black));

pnlUp.add(lblMoi);

pnlUp.add(lblMoiPts);

pnlDown.add(lblVous);

pnlDown.add(lblVousPts);

pnlRight.add(pnlUp);

pnlRight.add(pnlDown);

pnlRight.add(btnInit);

btnInit.addActionListener(this);

pnlUp.setBackground(new Color(230,230,255));

pnlDown.setBackground(new Color(230,230,255));

pnlRight.setBackground(new Color(230,230,255));

pnlBoard.setBackground(new Color(205,205,255));

lblMoiPts.setOpaque(true);

lblVousPts.setOpaque(true);

lblMoiPts.setBackground(Color.white);

lblVousPts.setBackground(Color.white);

pane.add(pnlRight, BorderLayout.EAST);

this.setContentPane(pane);

this.setVisible(true);

}

public void init()

{

ImageN = getImage(getCodeBase(), "images/null.gif");

ImageX = getImage(getCodeBase(), "images/x.gif");

ImageO = getImage(getCodeBase(), "images/o.gif");

Page 19

TicTacToe ttt = new TicTacToe();

for (int i = 0; i <=8; i++)

check[i].setIcon(new ImageIcon(ImageN));

}

public void actionPerformed(ActionEvent event)

{

JButton btn = (JButton)event.getSource();

if (btn.getText() == "" && btnEmpty[Integer.parseInt(btn.getName())] == true &&

vWait == true)

{

PlayerMove = Integer.parseInt(btn.getName());

Player = null;

Player = new Thread(this);

Player.start();

}

else if (btn.getText() == "Nouvelle Partie")

{

ptsMoi = 0;

ptsVous = 0;

vWait = true;

play(getCodeBase(), "sounds/carstart2.wav");//Son

RefreshCont();

lblMessage.setText("A vous de jouer !");

}}}

Page 20

Documents

Mini_rapport - TP - Copie