Aki ficam com um algoritmo para o jogo do galo impossível de vencer. O algoritmo faz apenas algumas comparações simples de padrões.
Talvez mais tarde me dedique a fazer um algoritmo adaptativo para o jogo do galo.
O código fonte está em Objective-C.
AI.h
@interface AI : NSObject {
char ttt[9];
int firstMove;
int rotation;
int play;
}
- (int) userPlay:(int) input;
- (int) analiseGame;
- (void) visualizeBoard;
- (int) rightMove;
- (int) patternMatchWin;
- (int) patternMatchBlock;
- (int) patternMatchBlock2Moves;
- (int) firstEmptySpace;
- (void) reconvertMatrix;
- (int) convertValueToTrueMatrix:(int) aValue;
- (void) rotate90;
- (int) play;
@end
AI.m
//
// AI.m
// TTT
//
// Created by KhAoTiK TaChYoN on 12/24/05.
// Copyright 2005 __MyCompanyName__. All rights reserved.
//
#import "AI.h"
@implementation AI
- (id) init
{
self = [super init];
firstMove = 1;
rotation = 0;
return self;
}
- (int) userPlay:(int) input
{
if (ttt[input] != \\'\0\\') return -2; // Error... that square is already taken
ttt[input] = \\'X\\';
if ([self analiseGame] != 2)
{
[self visualizeBoard];
return [self analiseGame];
}
play = [self rightMove];
ttt[play] = \\'O\\';
[self visualizeBoard];
return [self analiseGame];
}
- (void) visualizeBoard
{
int i;
char vis[9];
for (i = 0; i < 9; i++) {
if (ttt[i] == \\'\0\\') vis[i] = \\' \\';
else vis[i] = ttt[i];
}
NSLog(@"%c %c %c n", vis[0], vis[1], vis[2]);
NSLog(@"%c %c %c n", vis[3], vis[4], vis[5]);
NSLog(@"%c %c %c n", vis[6], vis[7], vis[8]);
}
- (int) analiseGame
{
// 1 = AI wins
// -1 = User wins
// 0 = Draw
// 2 = In play
if (ttt[0] == \\'O\\' && ttt[1] == \\'O\\' && ttt[2] == \\'O\\') return 1;
if (ttt[0] == \\'X\\' && ttt[1] == \\'X\\' && ttt[2] == \\'X\\') return -1;
if (ttt[3] == \\'O\\' && ttt[4] == \\'O\\' && ttt[5] == \\'O\\') return 1;
if (ttt[3] == \\'X\\' && ttt[4] == \\'X\\' && ttt[5] == \\'X\\') return -1;
if (ttt[6] == \\'O\\' && ttt[7] == \\'O\\' && ttt[8] == \\'O\\') return 1;
if (ttt[6] == \\'X\\' && ttt[7] == \\'X\\' && ttt[8] == \\'X\\') return -1;
if (ttt[0] == \\'O\\' && ttt[3] == \\'O\\' && ttt[6] == \\'O\\') return 1;
if (ttt[0] == \\'X\\' && ttt[3] == \\'X\\' && ttt[6] == \\'X\\') return -1;
if (ttt[1] == \\'O\\' && ttt[4] == \\'O\\' && ttt[7] == \\'O\\') return 1;
if (ttt[1] == \\'X\\' && ttt[4] == \\'X\\' && ttt[7] == \\'X\\') return -1;
if (ttt[2] == \\'O\\' && ttt[5] == \\'O\\' && ttt[8] == \\'O\\') return 1;
if (ttt[2] == \\'X\\' && ttt[5] == \\'X\\' && ttt[8] == \\'X\\') return -1;
if (ttt[0] == \\'O\\' && ttt[4] == \\'O\\' && ttt[8] == \\'O\\') return 1;
if (ttt[0] == \\'X\\' && ttt[4] == \\'X\\' && ttt[8] == \\'X\\') return -1;
if (ttt[2] == \\'O\\' && ttt[4] == \\'O\\' && ttt[6] == \\'O\\') return 1;
if (ttt[2] == \\'X\\' && ttt[4] == \\'X\\' && ttt[6] == \\'X\\') return -1;
if ([self firstEmptySpace] < 0) return 0;
return 2;
}
- (int) rightMove
{
int i, res;
if (firstMove == 1)
{
/*
1st move:
- center if user hasn\\'t chosen the center
- corner if user chose the center
*/
firstMove = 0;
if (ttt[4] == \\'\0\\') return 4;
else return 0;
}
for (i = 0; i < 4; i++)
{
res = [self patternMatchWin];
if (res >= 0) {
res = [self convertValueToTrueMatrix: res];
[self reconvertMatrix];
return res;
}
[self rotate90];
}
for (i = 0; i < 4; i++)
{
res = [self patternMatchBlock];
if (res >= 0) {
res = [self convertValueToTrueMatrix: res];
[self reconvertMatrix];
return res;
}
[self rotate90];
}
res = [self patternMatchBlock2Moves];
if (res >= 0) {
res = [self convertValueToTrueMatrix: res];
[self reconvertMatrix];
return res;
}
return [self firstEmptySpace];
// if < 0, game is over...
}
- (int) patternMatchWin
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'O\\' && ttt[2] == \\'O\\') return 0;
if (ttt[0] == \\'\0\\' && ttt[3] == \\'O\\' && ttt[6] == \\'O\\') return 0;
if (ttt[0] == \\'\0\\' && ttt[4] == \\'O\\' && ttt[8] == \\'O\\') return 0;
if (ttt[1] == \\'\0\\' && ttt[0] == \\'O\\' && ttt[2] == \\'O\\') return 1;
if (ttt[1] == \\'\0\\' && ttt[4] == \\'O\\' && ttt[7] == \\'O\\') return 1;
return -1;
}
- (int) patternMatchBlock
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'X\\' && ttt[2] == \\'X\\') return 0;
if (ttt[0] == \\'\0\\' && ttt[3] == \\'X\\' && ttt[6] == \\'X\\') return 0;
if (ttt[0] == \\'\0\\' && ttt[4] == \\'X\\' && ttt[8] == \\'X\\') return 0;
if (ttt[1] == \\'\0\\' && ttt[0] == \\'X\\' && ttt[2] == \\'X\\') return 1;
if (ttt[1] == \\'\0\\' && ttt[4] == \\'X\\' && ttt[7] == \\'X\\') return 1;
return -1;
}
- (int) patternMatchBlock2Moves
{
int i;
for (i = 0; i < 4; i++)
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'\0\\' && ttt[2] == \\'X\\' &&
ttt[3] == \\'\0\\' && ttt[4] == \\'X\\' && ttt[5] == \\'\0\\' &&
ttt[6] == \\'O\\' && ttt[7] == \\'\0\\' && ttt[8] == \\'\0\\') return 0;
[self rotate90];
}
for (i = 0; i < 4; i++)
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'\0\\' && ttt[2] == \\'X\\' &&
ttt[3] == \\'\0\\' && ttt[4] == \\'O\\' && ttt[5] == \\'\0\\' &&
ttt[6] == \\'X\\' && ttt[7] == \\'\0\\' && ttt[8] == \\'\0\\') return 1;
[self rotate90];
}
for (i = 0; i < 4; i++)
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'X\\' && ttt[2] == \\'\0\\' &&
ttt[3] == \\'X\\' && ttt[4] == \\'O\\' &&
ttt[6] == \\'\0\\') return 0;
[self rotate90];
}
for (i = 0; i < 4; i++)
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'X\\' && ttt[2] == \\'\0\\' &&
ttt[3] == \\'\0\\' && ttt[4] == \\'O\\' &&
ttt[6] == \\'X\\') return 0;
[self rotate90];
}
for (i = 0; i < 4; i++)
{
if (ttt[0] == \\'\0\\' && ttt[1] == \\'\0\\' && ttt[2] == \\'X\\' &&
ttt[3] == \\'X\\' && ttt[4] == \\'O\\' &&
ttt[6] == \\'\0\\') return 0;
[self rotate90];
}
return -1;
}
- (int) firstEmptySpace
{
int i;
for (i = 0; i < 9; i++)
{
if (ttt[i] == \\'\0\\') return i;
}
return -1;
}
- (void) reconvertMatrix
{
while (rotation > 0)
[self rotate90];
}
- (int) convertValueToTrueMatrix:(int) aValue
{
if (rotation == 0 || aValue == 4) return aValue;
if (rotation == 1) {
switch (aValue)
{
case 0: return 2;
case 1: return 5;
case 2: return 8;
case 3: return 1;
case 5: return 7;
case 6: return 0;
case 7: return 3;
case 8: return 6;
}
}
if (rotation == 2) {
switch (aValue)
{
case 0: return 8;
case 1: return 7;
case 2: return 6;
case 3: return 5;
case 5: return 3;
case 6: return 2;
case 7: return 1;
case 8: return 0;
}
}
if (rotation == 3) {
switch (aValue)
{
case 0: return 6;
case 1: return 3;
case 2: return 0;
case 3: return 7;
case 5: return 1;
case 6: return 8;
case 7: return 5;
case 8: return 2;
}
}
// Cannot reach this.
return 111111;
}
- (void) rotate90
{
int holder;
holder = ttt[6];
ttt[6] = ttt[0];
ttt[0] = ttt[2];
ttt[2] = ttt[8];
ttt[8] = holder;
holder = ttt[3];
ttt[3] = ttt[1];
ttt[1] = ttt[5];
ttt[5] = ttt[7];
ttt[7] = holder;
rotation = (rotation + 1) % 4;
}
- (int) play
{
return play;
}