· 7 years ago · Mar 05, 2019, 06:28 PM
1
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3<html>
4<!--
5
6JOGO DA VELHA
7Um exercÃcio de busca competitiva usando algoritmo MiniMax
8
9Mestrado em Computação - PPGC/UFPel
10Disciplina : Fundamentos de IA
11Professores: Ricardo Araújo e Paulo Ferreira Jr.
12
13Desenvolvido por Henrique Avila Vianna [hvianna (at) gmail.com]
14maio de 2011
15
16-->
17<head>
18<title>Jogo da Velha - Fundamentos de IA</title>
19
20<style>
21body {
22 font: 13px Verdana;
23}
24h1 {
25 margin-bottom: 0;
26 font: 29px "arial black";
27}
28h2 {
29 margin-top: 0;
30 margin-bottom: 50px;
31 font: bold italic 18px arial;
32}
33#container {
34 width: 780px;
35 margin: auto;
36}
37#quadroesq {
38 float: left;
39 width: 400px;
40}
41#quadrodir {
42 float: left;
43 width: 360px;
44}
45#tabuleiro {
46 border-collapse: collapse;
47}
48#tabuleiro td {
49 width: 100px;
50 height: 100px;
51 font: 60px "arial";
52 text-align: center;
53 vertical-align: center;
54 color: #000;
55}
56#p00,#p01,#p02, #p10,#p11,#p12 {
57 border-bottom: 4px solid #000;
58}
59#p00,#p01, #p10,#p11, #p20,#p21 {
60 border-right: 4px solid #000;
61}
62.clear {
63 clear: both;
64}
65.bloco {
66 float: left;
67 width: 76px;
68 background: url(fundo.png) no-repeat 10px 12px;
69 padding-left: 8px;
70 text-align: center;
71}
72.ativo {
73 background-color: #eee;
74}
75</style>
76
77<!-- Google +1 & Analytics -->
78<script type="text/javascript" src="http://apis.google.com/js/plusone.js"></script>
79<script type="text/javascript">
80 var _gaq = _gaq || [];
81 _gaq.push(['_setAccount', 'UA-23747942-1']);
82 _gaq.push(['_trackPageview']);
83
84 (function() {
85 var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
86 ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
87 var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
88 })();
89</script>
90<!-- end of Google code -->
91
92<script type="text/javascript">
93
94var estado = []; // estado do tabuleiro na tela
95var raiz; // primeiro nodo da arvore
96var atual; // ponteiro para o nodo que representa o estado atual do jogo
97
98var pilha = []; // array de ponteiros para nodo - usada para construir a árvore
99var nodos = 0; // nodos na árvore
100
101/* objeto nodo:
102
103 { pai: ponteiro para nodo,
104 estado: array[3][3] de char,
105 filhos: array de ponteiros para nodo,
106 jogador: char,
107 minimax: int }
108*/
109
110function inicializa() {
111 estado = [ [],[],[] ];
112 raiz = null;
113 atual = null;
114
115 exibeEstado(estado);
116
117 document.getElementById("CPUcomeca").style.display = '';
118 document.getElementById("reiniciar").style.display = 'none';
119 document.getElementById("info").style.display = 'none';
120 document.getElementById("infoFilhos").style.display = 'none';
121 document.getElementById("quadroFilhos").innerHTML = '';
122 mostraNetos();
123}
124
125function geraArvore() {
126 pilha = []; // limpa pilha
127 nodos = 0;
128 // gera nodo raiz a partir do estado do tabuleiro na tela (vazio ou com a primeira jogada do humano)
129 raiz = {pai: null, estado: estado, filhos: [], jogador: "O", minimax: null};
130 pilha.push(raiz); // coloca na pilha
131
132 document.getElementById("CPUcomeca").style.display = 'none';
133 document.getElementById("info").style.display = '';
134 document.getElementById("info").innerHTML = "Gerando árvore, aguarde...";
135
136 while (pilha.length) { // enquanto houver elementos na pilha
137 nodo = pilha.pop(); // retira um nodo
138 geraFilhos(nodo); // e gera filhos desse nodo
139 }
140
141 calculaMinimax(raiz); // calcula valores Minimax a partir da raiz
142
143 document.getElementById("info").innerHTML = "Tamanho da árvore: "+nodos+" nodos";
144 atual = raiz; // situação atual do jogo
145}
146
147
148function geraFilhos(pai) {
149 var estado = [];
150 var x,y,minimax;
151 var jogador = (pai.jogador=="X")?"O":"X"; // verifica de quem é a vez de jogar nesse nÃvel
152
153 for (y=0; y<3; y++)
154 for (x=0; x<3; x++)
155 if (pai.estado[y][x] == undefined) { // se encontrou espaço vago no tabuleiro
156 estado = copiaEstado(pai.estado); // gera uma cópia do estado atual
157 estado[y][x] = jogador; // adiciona a jogada
158 var nodo = {pai: pai, estado: estado, filhos: [], jogador: jogador, minimax: null}; // cria um novo nodo para o filho
159
160 nodo.minimax = ehTerminal(nodo.estado,0); // se for nodo terminal, recebe valor de utilidade
161 pai.filhos.push(nodo); // adiciona esse nodo no array de filhos do nodo pai
162 nodos++;
163
164 if (!nodo.minimax) // se filho não é terminal, vai para a pilha, para gerar os filhos dele
165 pilha.push(nodo);
166 }
167}
168
169function calculaMinimax(nodo) { // calcula o valor minimax de um nodo
170 var i, min, max;
171 for (i=0; i < nodo.filhos.length; i++) { // percorre todos os filhos do nodo
172 if (nodo.filhos[i].minimax === null) // se um filho ainda não tem um valor minimax (não é folha da árvore)
173 calculaMinimax(nodo.filhos[i]); // chama a função recursivamente para aquele filho
174
175 if (max == undefined || nodo.filhos[i].minimax > max) // guarda valor max (maior minimax entre os filhos)
176 max = nodo.filhos[i].minimax;
177 if (min == undefined || nodo.filhos[i].minimax < min) // guarda valor min (menor minimax entre os filhos)
178 min = nodo.filhos[i].minimax;
179 }
180 if (nodo.jogador == "O")
181 nodo.minimax = max; // se a próxima jogada é da CPU, retorna valor max
182 else
183 nodo.minimax = min; // caso contrário, retorna valor min
184}
185
186function ehTerminal(estado,encerra) { // verifica se estado é terminal, retornando seu valor de utilidade
187 var x,y; // retorna null caso não seja estado terminal
188 var brancos = 0; // encerra = 0 para calcular o valor de utilidade durante a geração da árvore
189 var utilidade = null; // = 1 para encerrar o jogo quando estado for terminal
190
191 for (y=0; y<3; y++) // testa linhas
192 if (estado[y][0] != undefined && estado[y][0] == estado[y][1] && estado[y][0] == estado[y][2]) {
193 utilidade = (estado[y][0] == "X")? 1: -1; // utilidade 1 para X (CPU), -1 para O (humano)
194 break;
195 }
196 if (!utilidade) // testa colunas
197 for (x=0; x<3; x++)
198 if (estado[0][x] != undefined && estado[0][x] == estado[1][x] && estado[0][x] == estado[2][x]) {
199 utilidade = (estado[0][x] == "X")? 1: -1;
200 break;
201 }
202 if (!utilidade) // testa diagonais
203 if ( estado[1][1] != undefined && (
204 (estado[0][0] == estado[1][1] && estado[0][0] == estado[2][2]) ||
205 (estado[0][2] == estado[1][1] && estado[0][2] == estado[2][0]) ) )
206 utilidade = (estado[1][1] == "X")? 1: -1;
207
208 for (y=0; y<3; y++)
209 for (x=0; x<3; x++)
210 if (estado[y][x] == undefined) // conta espaços em branco no tabuleiro
211 brancos++;
212
213 if (utilidade) // se achou um vencedor
214 if (encerra)
215 if (utilidade > 0) // utilidade > 0 venceu CPU
216 termina("Eu ganhei!");
217 else
218 termina("Você ganhou!"); // essa mensagem nunca será exibida :)
219 else
220 return utilidade*(brancos+1); // retorna valor de utilidade - nº de casas vagas dá um peso maior,
221 // favorecendo a escolha da jogada vitoriosa no nÃvel mais raso
222 else
223 if (!brancos) // se não tem mais espaços em branco também é terminal...
224 if (encerra)
225 termina("Empatamos!");
226 else
227 return 0; // ...com utilidade 0 (empate)
228 else
229 return null; // se ainda tem brancos, não é terminal
230}
231
232
233function jogaHumano(elemento) {
234 var i = Number(elemento.id.substr(1,1)); // pega linha a partir da id do elemento (ex. "p02")
235 var j = Number(elemento.id.substr(2,1)); // pega coluna a partir da id do elemento
236
237 if (estado[i][j] != undefined) {
238 alert("Posição inválida");
239 return;
240 }
241 else {
242 estado[i][j] = "O"; // coloca a jogada do humano
243 exibeEstado(estado); // atualiza tabuleiro na tela
244 }
245
246 if (!ehTerminal(estado,1)) { // verifica se jogada do humano resultou em um estado terminal
247 if (!raiz) // se raiz é null, árvore ainda não foi gerada (humano começa o jogo)
248 geraArvore(); // a raiz será o estado atual, já com a jogada do humano
249 else
250 for (i=0;i < atual.filhos.length; i++) // procura nos filhos do estado atual, qual representa a situação após a jogada do humano
251 if (comparaEstados(estado,atual.filhos[i].estado)) {
252 atual = atual.filhos[i];
253 break;
254 }
255 jogaCPU(); // passa a vez para a CPU
256 }
257}
258
259function jogaCPU() {
260 var max;
261 var opcoes = []; // array das opções de jogadas
262 var i,r;
263
264 if (!raiz) // se raiz é null, árvore ainda não foi gerada (CPU começa o jogo)
265 geraArvore();
266
267 document.getElementById("infoFilhos").style.display = ''; // limpa exibição dos filhos e netos
268 document.getElementById("quadroFilhos").innerHTML = '';
269 mostraNetos();
270
271 // avalia qual a melhor opção de jogada, dentre as possÃveis (filhos do estado atual)
272 for (i=0;i < atual.filhos.length; i++) {
273 mostraFilho(atual.filhos[i],i,0);
274 if (atual.filhos[i].minimax != null && (max == undefined || atual.filhos[i].minimax > max))
275 max = atual.filhos[i].minimax; // salva maior valor minimax dos filhos
276 }
277
278 // percorre novamente os filhos, checando todos que tenham o mesmo valor minimax ótimo
279 for (i=0;i < atual.filhos.length; i++)
280 if (atual.filhos[i].minimax == max)
281 opcoes.push(i); // coloca Ãndice deste filho no array de opções de jogada
282
283 // e escolhe aleatoriamente um deles, para dar mais variedade às jogadas
284 r = Math.floor(Math.random()*opcoes.length);
285 atual = atual.filhos[opcoes[r]];
286 estado = atual.estado;
287 exibeEstado(estado);
288
289 ehTerminal(estado,1); // Verifica se atingiu estado terminal, encerrando o jogo
290}
291
292/* funções de display */
293
294function exibeEstado(estado) { // atualiza tabuleiro na tela
295 for (var i=0; i<3; i++)
296 for (var j=0; j<3; j++) {
297 elemento = document.getElementById("p"+i+j);
298 if (estado[i][j] == undefined)
299 elemento.innerHTML = " ";
300 else
301 elemento.innerHTML = estado[i][j];
302 }
303}
304
305function mostraFilho(nodo,i,n) { // adiciona um nodo aos blocos de filhos ou netos, abaixo do tabuleiro
306 var html; // n=0 filhos, n=1 netos
307 var x,y;
308
309 if (n == 0)
310 html = "<div class='bloco' id='b"+i+"' onClick='mostraNetos("+i+")'><pre>"; // gera blocos de filhos
311 else
312 html = "<div class='bloco ativo'><pre>"; // gera blocos de netos
313
314 for (y=0; y<3; y++) {
315 for (x=0; x<3; x++)
316 if (nodo.estado[y][x] == undefined)
317 html += " ";
318 else
319 html += nodo.estado[y][x]+" ";
320 html += "\n";
321 }
322 html += nodo.minimax+"</pre></div>\n";
323
324 if (n == 0) {
325 document.getElementById("quadroFilhos").innerHTML += html;
326 document.getElementById("quadroNetos"+i).innerHTML = '';
327 for (x=0; x < nodo.filhos.length; x++)
328 mostraFilho(nodo.filhos[x],i,1); // chama a função para gerar os blocos de netos
329 }
330 else
331 document.getElementById("quadroNetos"+i).innerHTML += html;
332}
333
334function mostraNetos(n) { // mostra/oculta blocos de netos
335 var i;
336 if (n != undefined)
337 if (document.getElementById("quadroNetos"+n).style.display == '') // se já está exibido, tem que ocultar
338 n = undefined;
339 for (i=0; i<9; i++) { // oculta todos os blocos
340 document.getElementById("quadroNetos"+i).style.display = 'none';
341 if (document.getElementById("b"+i))
342 document.getElementById("b"+i).className = 'bloco'; // desmarca os pais (tira classe 'ativo')
343 }
344 if (n != undefined) { // exibe o bloco desejado
345 document.getElementById("quadroNetos"+n).style.display = '';
346 if (document.getElementById("b"+n))
347 document.getElementById("b"+n).className = 'bloco ativo'; // marca o bloco do pai
348 }
349}
350
351function termina(msg) {
352 alert(msg);
353 document.getElementById("reiniciar").style.display = '';
354 document.getElementById("CPUcomeca").style.display = 'none';
355}
356
357/* funções auxiliares */
358
359function copiaEstado(estado) {
360 var retorno = [];
361 for(var i = 0; i < estado.length; i++) // copia elementos do array
362 retorno[i] = estado[i].slice(0); // necessário para evitar a cópia por referência
363
364 return retorno;
365}
366
367function comparaEstados(estado1,estado2) {
368 for (var i=0; i<3; i++)
369 for (var j=0; j<3; j++)
370 if (estado1[i][j] != estado2[i][j])
371 return false;
372
373 return true;
374}
375
376
377</script>
378</head>
379
380<body onLoad="inicializa();">
381
382<div id="container">
383 <div style="float:right">
384 <!-- Google +1 button -->
385 <g:plusone></g:plusone>
386 </div>
387 <h1>Jogo da Velha - Fundamentos de IA</h1>
388 <h2>Um exercÃcio de busca competitiva usando algoritmo MiniMax</h2>
389 <div id="quadroesq">
390 <table id="tabuleiro">
391 <tr>
392 <td id="p00" onClick="jogaHumano(this);"></td>
393 <td id="p01" onClick="jogaHumano(this);"></td>
394 <td id="p02" onClick="jogaHumano(this);"></td>
395 </tr>
396 <tr>
397 <td id="p10" onClick="jogaHumano(this);"></td>
398 <td id="p11" onClick="jogaHumano(this);"></td>
399 <td id="p12" onClick="jogaHumano(this);"></td>
400 </tr>
401 <tr>
402 <td id="p20" onClick="jogaHumano(this);"></td>
403 <td id="p21" onClick="jogaHumano(this);"></td>
404 <td id="p22" onClick="jogaHumano(this);"></td>
405 </tr>
406 </table>
407 </div>
408
409 <div id="quadrodir">
410 <br>
411 <form>
412 X = CPU<br>
413 O = Humano<br><br>
414 Clique em uma posição do tabuleiro para jogar<br><br><br>
415 <input type="button" id="CPUcomeca" value=" CPU começa " onClick="jogaCPU();">
416 <input type="button" id="reiniciar" value=" Jogar novamente " onClick="inicializa();">
417 </form>
418
419 <br><br>
420 <div id="info"></div>
421 </div>
422
423 <div id="infoFilhos" class="clear"><br>Nodos avaliados para esta jogada: (clique em um para ver seus sucessores)</div>
424 <div id="quadroFilhos" class="clear"></div>
425 <div id="quadroNetos0" class="clear"></div>
426 <div id="quadroNetos1" class="clear"></div>
427 <div id="quadroNetos2" class="clear"></div>
428 <div id="quadroNetos3" class="clear"></div>
429 <div id="quadroNetos4" class="clear"></div>
430 <div id="quadroNetos5" class="clear"></div>
431 <div id="quadroNetos6" class="clear"></div>
432 <div id="quadroNetos7" class="clear"></div>
433 <div id="quadroNetos8" class="clear"></div>
434</div>
435
436</body>
437</html>