Here is the code I made (player versus computer). It is not AI, but the computer can play at the "beginner" level (for children) and "expert" (where it does not fail).
At the time I did to learn Java , so it is in this language, but it is easily adaptable to Python.
The code below is just the Java kernel (it does not include the GUI), but it has all the logic for you to convert to Python or any other language:
import java.util.Arrays;
import java.util.Random;
//import org.apache.commons.lang3.ArrayUtils;
/**
* Created by Rogério Dec (http://rogeriodec.com.br - [email protected]) on 20/01/2017.
*/
public class Velha {
public static int i, ContMatriz, jogada, jogadaX, numjogada = 0;
public static char[] MatrizJogo = new char[10];
public static int[][] JogadasPossiveis = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {1, 4, 7}, {2, 5, 8}, {3, 6, 9}, {1, 5, 9}, {3, 5, 7}};
public static int[][] Log = new int[2][10];
static Random rnd = new Random();
public static String Velha(int botao) {
if (JogoDaVelha.Iniciante.isSelected()) { // modo iniciante
if (botao == 0) // computador começa
PreencheVazio('O');
else {
MatrizJogo[botao] = 'X'; // armazena jogada humana na matriz, posição escolhida
ContMatriz++;
if (FazVelha('X') == 3) // Jogador X fez 3 casas (velha)?
return "X"; // humano ganhou
PreencheVazio('O');
if (FazVelha('O') == 3)
return "O"; // máquina ganhou
if (ContMatriz > 8) // não achou jogada possível, preenche qualquer um ...
return "E"; // empate
}
}
else { // modo experto
if (botao == 0) // computador começa
ataca();
else {
MatrizJogo[botao] = 'X'; // armazena jogada humana na matriz, posição escolhida
ContMatriz++; // incrementa contador da matrizes já utilizadas
// fechou velha?
if (FazVelha('X') == 3) // Jogador X fez 3 casas (velha)?
return "X"; // humano ganhou
jogadaX = jogada; // guarda para comparar jogadaX
if (FazVelha('O') == 2) {
jogadaX = jogada; // guarda para comparar jogadaX
defende();
return "O";
}
// humano consegue velha?
if (FazVelha('X') == 2) // Jogador X fez 2 casas, então pode fazer velha
defende();
else
ataca();
if (ContMatriz >= 8) // não achou jogada possível, preenche qualquer um ...
return "E"; // empate
// máquina consegue velha?
}
}
// ********** começa computador, modo experto, x = 3, 4, O = 5, 1 e ai faz 8 e 9 de uma vez
return null;
}
public static void desenha(){
if (MatrizJogo[1] != 'import java.util.Arrays;
import java.util.Random;
//import org.apache.commons.lang3.ArrayUtils;
/**
* Created by Rogério Dec (http://rogeriodec.com.br - [email protected]) on 20/01/2017.
*/
public class Velha {
public static int i, ContMatriz, jogada, jogadaX, numjogada = 0;
public static char[] MatrizJogo = new char[10];
public static int[][] JogadasPossiveis = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {1, 4, 7}, {2, 5, 8}, {3, 6, 9}, {1, 5, 9}, {3, 5, 7}};
public static int[][] Log = new int[2][10];
static Random rnd = new Random();
public static String Velha(int botao) {
if (JogoDaVelha.Iniciante.isSelected()) { // modo iniciante
if (botao == 0) // computador começa
PreencheVazio('O');
else {
MatrizJogo[botao] = 'X'; // armazena jogada humana na matriz, posição escolhida
ContMatriz++;
if (FazVelha('X') == 3) // Jogador X fez 3 casas (velha)?
return "X"; // humano ganhou
PreencheVazio('O');
if (FazVelha('O') == 3)
return "O"; // máquina ganhou
if (ContMatriz > 8) // não achou jogada possível, preenche qualquer um ...
return "E"; // empate
}
}
else { // modo experto
if (botao == 0) // computador começa
ataca();
else {
MatrizJogo[botao] = 'X'; // armazena jogada humana na matriz, posição escolhida
ContMatriz++; // incrementa contador da matrizes já utilizadas
// fechou velha?
if (FazVelha('X') == 3) // Jogador X fez 3 casas (velha)?
return "X"; // humano ganhou
jogadaX = jogada; // guarda para comparar jogadaX
if (FazVelha('O') == 2) {
jogadaX = jogada; // guarda para comparar jogadaX
defende();
return "O";
}
// humano consegue velha?
if (FazVelha('X') == 2) // Jogador X fez 2 casas, então pode fazer velha
defende();
else
ataca();
if (ContMatriz >= 8) // não achou jogada possível, preenche qualquer um ...
return "E"; // empate
// máquina consegue velha?
}
}
// ********** começa computador, modo experto, x = 3, 4, O = 5, 1 e ai faz 8 e 9 de uma vez
return null;
}
public static void desenha(){
if (MatrizJogo[1] != '%pre%') JogoDaVelha.b1.setText((Character.toString(MatrizJogo[1])));
if (MatrizJogo[2] != '%pre%') JogoDaVelha.b2.setText((Character.toString(MatrizJogo[2])));
if (MatrizJogo[3] != '%pre%') JogoDaVelha.b3.setText((Character.toString(MatrizJogo[3])));
if (MatrizJogo[4] != '%pre%') JogoDaVelha.b4.setText((Character.toString(MatrizJogo[4])));
if (MatrizJogo[5] != '%pre%') JogoDaVelha.b5.setText((Character.toString(MatrizJogo[5])));
if (MatrizJogo[6] != '%pre%') JogoDaVelha.b6.setText((Character.toString(MatrizJogo[6])));
if (MatrizJogo[7] != '%pre%') JogoDaVelha.b7.setText((Character.toString(MatrizJogo[7])));
if (MatrizJogo[8] != '%pre%') JogoDaVelha.b8.setText((Character.toString(MatrizJogo[8])));
if (MatrizJogo[9] != '%pre%') JogoDaVelha.b9.setText((Character.toString(MatrizJogo[9])));
numjogada++;
int jogador = 0;
for (int casa = 1; casa < 10; casa++) {
acha: {
if (MatrizJogo[casa] == '%pre%')
continue;
if (MatrizJogo[casa] == 'X')
jogador = 0;
if (MatrizJogo[casa] == 'O')
jogador = 1;
for (i = 1; i<10; i++) { // ve se a casa já havia sido registrada em aguma jogada
if (Log[jogador][i] == casa)
break acha; // se já havia sido registrada, vai para proxima casa
}
Log[jogador][numjogada] = casa;
}
}
}
private static int FazVelha (char jogador) {
int ContVelha, ContVelhaAnt = 0, jogadaAnt = 0;
for (jogada=0; jogada<8; jogada++) { // Rastreia Jogadas Possíveis, uma por uma para ver qual tem mais combinações
ContVelha = 0;
for (int casa = 0; casa < 3; casa++) { // compara
int CasaPossivel = JogadasPossiveis[jogada][casa];
if (MatrizJogo[CasaPossivel] == jogador)
ContVelha++;
else if (MatrizJogo[CasaPossivel] != '%pre%'){ // se casa estiver preenchida com do OUTRO jogador, anula esta jogada possível
ContVelha = 0;
break;
}
}
// if (ContVelha >= 3)
if (ContVelha >= (JogoDaVelha.Iniciante.isSelected() ? 3 : 2)) {
if (ContVelhaAnt < ContVelha) {
ContVelhaAnt = ContVelha;
jogadaAnt = jogada;
}
}
}
jogada = jogadaAnt;
return ContVelhaAnt;
}
private static void defende() {
int ContVazias = 0, casa, ContImpares = 0;
for (casa = 0; casa < 3; casa++) {
if (MatrizJogo[JogadasPossiveis[jogadaX][casa]] == '%pre%') // encontrou casa vazia
ContVazias++;
}
if (ContVazias == 0) {
PreencheVazio('O');
return;
}
if (ContVazias == 3) { // se as 3 casas da jogada escolhida estiverem vazias, joga numa que não seja par
int [] CasasImpares = new int [3];
for (casa = 0; casa < 3; casa++) { // conta quantas casas da jogada são impares
if (JogadasPossiveis[jogadaX][casa] % 2 != 0)
CasasImpares[ContImpares++] = JogadasPossiveis[jogadaX][casa];
}
if (ContImpares == 1) // se encontrou apenas 1 casa impar na jogada escolhida
casa = CasasImpares[0]; // pega a 1a casa impar encontrada
else
casa = CasasImpares[rnd.nextInt(ContImpares)]; // sorteia entre a 1a e a 2a casa impar encontrada
MatrizJogo[casa] = 'O';
}
else {
int CasaEscolhida = rnd.nextInt(ContVazias);
i = 0;
for (casa = 0; casa < 3; casa++) {
if (MatrizJogo[JogadasPossiveis[jogadaX][casa]] == '%pre%') {
if (i == CasaEscolhida) {
MatrizJogo[JogadasPossiveis[jogadaX][casa]] = 'O'; // preenche com O
break;
}
i++;
}
}
}
ContMatriz++;
}
private static void ataca() {
if (ContMatriz == 0) { // primeira jogada, computador começando
int [] primeiraJogada = {1,3,5,7,9};
i = rnd.nextInt(5);
MatrizJogo[primeiraJogada[i]] = 'O';
ContMatriz++;
return;
}
i=0;
int [] JogadasPossiveisO = new int [8];
int [] ProbabilidadeJogada = new int [8];
int ContProb=0; // contador de probabilides encontradas
// Rastreia Jogadas Possíveis para O (máquina)
for (jogada = 0; jogada < 8; jogada++) {
proxJogada: {
for (int casa = 0; casa < 3; casa++) { // compara
int CasaPossivel = JogadasPossiveis[jogada][casa];
if (MatrizJogo[CasaPossivel] == 'X') { // se encontrou algum X, a jogada não é possível, tenta outra jogada possível
if (ProbabilidadeJogada[i] > 0) {
ProbabilidadeJogada[i] = 0; // zera contador de probabilidade desta jogada
ContProb--; // volta no contador de probabilidades
}
break proxJogada;
}
if (MatrizJogo[CasaPossivel] == 'O') { // se encontrou algum O, aumenta a probabilidade da jogada se escolhida
ProbabilidadeJogada[i]++; // aumenta contador de probabilidade desta jogada
ContProb++; // mais uma probabilidade encontrada
}
}
JogadasPossiveisO[i++] = jogada;
}
} // aqui já tem todas as jogadas possívels para O suas probabilidades
if (i == 0) { // se não encontrou nenhuma jogada possível, preenche qualquer espaço vazio para acabar o jogo
PreencheVazio('O');
return;
}
int MelhorJogada = 0;
int JogadaEscolhida = 0;
int x = 0;
if (ContProb == 0)
MelhorJogada = rnd.nextInt(i);
else {
JogadaEscolhida = rnd.nextInt(ContProb); // define aleatoriamente qual das melhores jogadas encontradas será usada
for (i = 0; i < 8; i++) { // localiza a jogada de maior probabilidade
if (ProbabilidadeJogada[i] > 0) {
if (x == JogadaEscolhida) {
MelhorJogada = i; // define qual a melhor jogada
break;
}
x++;
}
}
}
jogadaX = JogadasPossiveisO[MelhorJogada]; // define a melhor jogada dentro da maior probabilidade. Se nenhuma probabilidade foi encontrada, pega a 1a jogada possível.
defende(); // preenche a jogada
}
private static void PreencheVazio(char jogador) {
int [] vazios = new int[10];
int ContVazios = 0;
for (i = 1; i <= 9; i++) { // procura primeiro espaço vazio
if (MatrizJogo[i] == '%pre%')
vazios[++ContVazios] = i;
}
if (ContVazios != 0) {
i = rnd.nextInt(ContVazios) + 1;
MatrizJogo[vazios[i]] = jogador;
}
ContMatriz++;
}
}
') JogoDaVelha.b1.setText((Character.toString(MatrizJogo[1])));
if (MatrizJogo[2] != '%pre%') JogoDaVelha.b2.setText((Character.toString(MatrizJogo[2])));
if (MatrizJogo[3] != '%pre%') JogoDaVelha.b3.setText((Character.toString(MatrizJogo[3])));
if (MatrizJogo[4] != '%pre%') JogoDaVelha.b4.setText((Character.toString(MatrizJogo[4])));
if (MatrizJogo[5] != '%pre%') JogoDaVelha.b5.setText((Character.toString(MatrizJogo[5])));
if (MatrizJogo[6] != '%pre%') JogoDaVelha.b6.setText((Character.toString(MatrizJogo[6])));
if (MatrizJogo[7] != '%pre%') JogoDaVelha.b7.setText((Character.toString(MatrizJogo[7])));
if (MatrizJogo[8] != '%pre%') JogoDaVelha.b8.setText((Character.toString(MatrizJogo[8])));
if (MatrizJogo[9] != '%pre%') JogoDaVelha.b9.setText((Character.toString(MatrizJogo[9])));
numjogada++;
int jogador = 0;
for (int casa = 1; casa < 10; casa++) {
acha: {
if (MatrizJogo[casa] == '%pre%')
continue;
if (MatrizJogo[casa] == 'X')
jogador = 0;
if (MatrizJogo[casa] == 'O')
jogador = 1;
for (i = 1; i<10; i++) { // ve se a casa já havia sido registrada em aguma jogada
if (Log[jogador][i] == casa)
break acha; // se já havia sido registrada, vai para proxima casa
}
Log[jogador][numjogada] = casa;
}
}
}
private static int FazVelha (char jogador) {
int ContVelha, ContVelhaAnt = 0, jogadaAnt = 0;
for (jogada=0; jogada<8; jogada++) { // Rastreia Jogadas Possíveis, uma por uma para ver qual tem mais combinações
ContVelha = 0;
for (int casa = 0; casa < 3; casa++) { // compara
int CasaPossivel = JogadasPossiveis[jogada][casa];
if (MatrizJogo[CasaPossivel] == jogador)
ContVelha++;
else if (MatrizJogo[CasaPossivel] != '%pre%'){ // se casa estiver preenchida com do OUTRO jogador, anula esta jogada possível
ContVelha = 0;
break;
}
}
// if (ContVelha >= 3)
if (ContVelha >= (JogoDaVelha.Iniciante.isSelected() ? 3 : 2)) {
if (ContVelhaAnt < ContVelha) {
ContVelhaAnt = ContVelha;
jogadaAnt = jogada;
}
}
}
jogada = jogadaAnt;
return ContVelhaAnt;
}
private static void defende() {
int ContVazias = 0, casa, ContImpares = 0;
for (casa = 0; casa < 3; casa++) {
if (MatrizJogo[JogadasPossiveis[jogadaX][casa]] == '%pre%') // encontrou casa vazia
ContVazias++;
}
if (ContVazias == 0) {
PreencheVazio('O');
return;
}
if (ContVazias == 3) { // se as 3 casas da jogada escolhida estiverem vazias, joga numa que não seja par
int [] CasasImpares = new int [3];
for (casa = 0; casa < 3; casa++) { // conta quantas casas da jogada são impares
if (JogadasPossiveis[jogadaX][casa] % 2 != 0)
CasasImpares[ContImpares++] = JogadasPossiveis[jogadaX][casa];
}
if (ContImpares == 1) // se encontrou apenas 1 casa impar na jogada escolhida
casa = CasasImpares[0]; // pega a 1a casa impar encontrada
else
casa = CasasImpares[rnd.nextInt(ContImpares)]; // sorteia entre a 1a e a 2a casa impar encontrada
MatrizJogo[casa] = 'O';
}
else {
int CasaEscolhida = rnd.nextInt(ContVazias);
i = 0;
for (casa = 0; casa < 3; casa++) {
if (MatrizJogo[JogadasPossiveis[jogadaX][casa]] == '%pre%') {
if (i == CasaEscolhida) {
MatrizJogo[JogadasPossiveis[jogadaX][casa]] = 'O'; // preenche com O
break;
}
i++;
}
}
}
ContMatriz++;
}
private static void ataca() {
if (ContMatriz == 0) { // primeira jogada, computador começando
int [] primeiraJogada = {1,3,5,7,9};
i = rnd.nextInt(5);
MatrizJogo[primeiraJogada[i]] = 'O';
ContMatriz++;
return;
}
i=0;
int [] JogadasPossiveisO = new int [8];
int [] ProbabilidadeJogada = new int [8];
int ContProb=0; // contador de probabilides encontradas
// Rastreia Jogadas Possíveis para O (máquina)
for (jogada = 0; jogada < 8; jogada++) {
proxJogada: {
for (int casa = 0; casa < 3; casa++) { // compara
int CasaPossivel = JogadasPossiveis[jogada][casa];
if (MatrizJogo[CasaPossivel] == 'X') { // se encontrou algum X, a jogada não é possível, tenta outra jogada possível
if (ProbabilidadeJogada[i] > 0) {
ProbabilidadeJogada[i] = 0; // zera contador de probabilidade desta jogada
ContProb--; // volta no contador de probabilidades
}
break proxJogada;
}
if (MatrizJogo[CasaPossivel] == 'O') { // se encontrou algum O, aumenta a probabilidade da jogada se escolhida
ProbabilidadeJogada[i]++; // aumenta contador de probabilidade desta jogada
ContProb++; // mais uma probabilidade encontrada
}
}
JogadasPossiveisO[i++] = jogada;
}
} // aqui já tem todas as jogadas possívels para O suas probabilidades
if (i == 0) { // se não encontrou nenhuma jogada possível, preenche qualquer espaço vazio para acabar o jogo
PreencheVazio('O');
return;
}
int MelhorJogada = 0;
int JogadaEscolhida = 0;
int x = 0;
if (ContProb == 0)
MelhorJogada = rnd.nextInt(i);
else {
JogadaEscolhida = rnd.nextInt(ContProb); // define aleatoriamente qual das melhores jogadas encontradas será usada
for (i = 0; i < 8; i++) { // localiza a jogada de maior probabilidade
if (ProbabilidadeJogada[i] > 0) {
if (x == JogadaEscolhida) {
MelhorJogada = i; // define qual a melhor jogada
break;
}
x++;
}
}
}
jogadaX = JogadasPossiveisO[MelhorJogada]; // define a melhor jogada dentro da maior probabilidade. Se nenhuma probabilidade foi encontrada, pega a 1a jogada possível.
defende(); // preenche a jogada
}
private static void PreencheVazio(char jogador) {
int [] vazios = new int[10];
int ContVazios = 0;
for (i = 1; i <= 9; i++) { // procura primeiro espaço vazio
if (MatrizJogo[i] == '%pre%')
vazios[++ContVazios] = i;
}
if (ContVazios != 0) {
i = rnd.nextInt(ContVazios) + 1;
MatrizJogo[vazios[i]] = jogador;
}
ContMatriz++;
}
}