Hallo zusammen,
danke für die netten Kommentare. Die AI ist ja wie schon erwähnt ein NegaMax-Algorithmus. Da der Code ca. 1000 Zeilen umfasst kann ich ihn nicht ganz posten aber ich hab die wichtigsten Stellen gepostet. Wenn du oder jemand anderes Intresse am gesamten Code hat schicke ich ihm gerne eine PM. Es tut mir leid wenn der Code an einigen Stellen unleserlich ist, ich sollte ihn bei Gelegenheit noch mal überarbeiten, weil ich relativ unsauber programmiert habe. Der Algorithmus ist ja wie schon gesagt abgetippt. Der NegaMax-Algorithmus ist nur einer von vielen, den man verwenden kann, wikipedia liefert eine ganz gute Übersicht, du musst unten in den links gucken, d stehen halt noch die anderen:
http://de.wikipedia.org/wiki/Minimax-Algorithmus
Hier sind noch ein paar links die mir geholfen haben den Algorithmus zu verstehen:
http://www.aihorizon.com/essays/basiccs/trees/minimax.htm
http://en.literateprograms.org/Tic_Tac_Toe_%28C_Plus_Plus%29
http://www.experts-exchange.com/Programming/Game/AI_Physics/Q_21994259.html
http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/A_rot/060125_Proj_AlphaBetaPruning_Norvig_Russell_FINAL. pdf
http://www.osix.net/modules/article/?id=801
http://www.chessandpoker.com/tic_tac_toe_strategy.html
http://www.angelfire.com/wi/wickmann/cs002.html
Die sind zwar alle bis auf einen auf Englisch aber du wirst damit gut klargekommen. Allerdings beschäftigt sich nur der letzte Link explizit mit dem "NegaMax-Algorithmus", von dem hab ich auch abgetippt. Hier ist mein Code:
#include <avr/io.h>
#include "USART_Util.h"
#include <util/delay.h>
#include <avr/interrupt.h>
#include <stdlib.h>
unsigned char Board[3][3]={{2,2,2},
{2,2,2},
{2,2,2}};
int ply=0;
int toggle=1,win=0;
unsigned char a[9] = {0,0,0,0,0,0,0,0,0};
unsigned char led[9] = {0,0,0,0,0,0,0,0,0};
unsigned int c_flag,npc=2;
volatile unsigned char k=100;
unsigned char OtherPlayer(unsigned char inPlayer)
{
if(inPlayer==1)return 0;
return 1;
}
char doWin(unsigned char inBoard[3][3],unsigned char inPlayer)
{
if((inBoard[0][0]==inPlayer)&(inBoard[0][1]==inPlayer)&(inBoard[0][2]==inPlayer))
{
return 1;
}
if((inBoard[0][0]==inPlayer)&(inBoard[1][0]==inPlayer)&(inBoard[2][0]==inPlayer))
{
return 1;
}
if((inBoard[2][0]==inPlayer)&(inBoard[2][1]==inPlayer)&(inBoard[2][2]==inPlayer))
{
return 1;
}
if((inBoard[2][2]==inPlayer)&(inBoard[1][2]==inPlayer)&(inBoard[0][2]==inPlayer))
{
return 1;
}
if((inBoard[1][0]==inPlayer)&(inBoard[1][1]==inPlayer)&(inBoard[1][2]==inPlayer))
{
return 1;
}
if((inBoard[0][1]==inPlayer)&(inBoard[1][1]==inPlayer)&(inBoard[2][1]==inPlayer))
{
return 1;
}
if((inBoard[0][0]==inPlayer)&(inBoard[1][1]==inPlayer)&(inBoard[2][2]==inPlayer))
{
return 1;
}
if((inBoard[0][2]==inPlayer)&(inBoard[1][1]==inPlayer)&(inBoard[2][0]==inPlayer))
{
return 1;
}
return 0;
}
int NegaMax(unsigned char inBoard[3][3], unsigned char inPlayer)
{
if(doWin(inBoard,inPlayer)==1)
{
return 1;
}
if(doWin(inBoard,OtherPlayer(inPlayer))==1)
{
return -1;
}
int best=-2;
int i;
for(i=0;i<3;i++)
{
int j;
for(j=0;j<3;j++)
{
if(inBoard[i][j]==2)
{
inBoard[i][j]=inPlayer;
int value=-NegaMax(inBoard,OtherPlayer(inPlayer));
inBoard[i][j]=2;
if(value>best)
{
best=value;
}
}
}
}
if(best==-2)
{
return 0;
}
return best;
}
void moveComputer(unsigned char inBoard[3][3])
{
if(ply<4){
ply++;
int i;
int j;
int best=0;
unsigned char besti=0;
unsigned char bestj=0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(Board[i][j]==2)
{
Board[i][j]=1;
best=-NegaMax(inBoard,0);
Board[i][j]=2;
besti=i;
bestj=j;
}
}
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
if(inBoard[i][j]==2)
{
inBoard[i][j]=1;
int score=-NegaMax(inBoard,0);
if(score>best)
{
besti=i;
bestj=j;
best=score;
}
inBoard[i][j]=2;
}
}
}
Board[besti][bestj]=1;
}
}
void pc (void){
int q,u;
c_flag=1;
for(unsigned int e=0;e<5;e++){
while(c_flag){
if(led[0]==0){
PORTA |= (1<<PA0);
PORTB &=~ (1<<PB0);
}
if(led[1]==0){
PORTA |= (1<<PA1);
PORTB &=~ (1<<PB1);
}
if(led[2]==0){
PORTA |= (1<<PA2);
PORTB &=~ (1<<PB2);
}
if(led[3]==0){
PORTA |= (1<<PA3);
PORTB &=~ (1<<PB3);
}
if(led[4]==0){
PORTA |= (1<<PA4);
PORTB &=~ (1<<PB4);
}
if(led[5]==0){
PORTA |= (1<<PA5);
PORTB &=~ (1<<PB5);
}
if(led[6]==0){
PORTA |= (1<<PA6);
PORTB &=~ (1<<PB6);
}
if(led[7]==0){
PORTA |= (1<<PA7);
PORTB &=~ (1<<PB7);
}
if(led[8]==0){
PORTC |= (1<<PC7);
PORTD &=~ (1<<PD5);
}
_delay_us(10);
if(led[0]==0){
DDRA &=~ (1<<PA0);
PORTA &=~ (1<<PA0);
}
if(led[1]==0){
DDRA &=~ (1<<PA1);
PORTA &=~ (1<<PA1);
}
if(led[2]==0){
DDRA &=~ (1<<PA2);
PORTA &=~ (1<<PA2);
}
if(led[3]==0){
DDRA &=~ (1<<PA3);
PORTA &=~ (1<<PA3);
}
if(led[4]==0){
DDRA &=~ (1<<PA4);
PORTA &=~ (1<<PA4);
}
if(led[5]==0){
DDRA &=~ (1<<PA5);
PORTA &=~ (1<<PA5);
}
if(led[6]==0){
DDRA &=~ (1<<PA6);
PORTA &=~ (1<<PA6);
}
if(led[7]==0){
DDRA &=~ (1<<PA7);
PORTA &=~ (1<<PA7);
}
if(led[8]==0){
DDRC &=~ (1<<PC7);
PORTC &=~ (1<<PC7);
}
_delay_ms(k-75);
a[2] = (PINA & (1<<PINA2));
a[3] = (PINA & (1<<PINA3));
a[5] = (PINA & (1<<PINA5));
_delay_ms(10);
a[4] = (PINA & (1<<PINA4));
_delay_ms(65);
a[0] = (PINA & (1<<PINA0));
a[1] = (PINA & (1<<PINA1));
a[6] = (PINA & (1<<PINA6));
a[7] = (PINA & (1<<PINA7));
a[8] = (PINC & (1<<PINC7));
DDRA = 0xFF;
DDRC = 0xFF;
if((a[0]!=0)&&(led[0]==0)){
PORTB |= (1<<PB0);
c_flag = 0;
c[0]=0;
Board[0][0]=0;
led[0]=1;
_delay_ms(120);
}
if(a[1]!=0){
PORTB |= (1<<PB1);
c_flag = 0;
c[1]=0;
Board[0][1]=0;
led[1]=1;
_delay_ms(120);
}
if(a[2]!=0){
PORTB |= (1<<PB2);
c_flag = 0;
c[2]=0;
Board[0][2]=0;
led[2]=1;
_delay_ms(120);
}
if(a[3]!=0){
PORTB |= (1<<PB3);
c_flag = 0;
c[3]=0;
Board[1][0]=0;
led[3]=1;
_delay_ms(120);
}
if(a[4]!=0){
PORTB |= (1<<PB4);
c_flag = 0;
c[4]=0;
Board[1][1]=0;
led[4]=1;
_delay_ms(120);
}
if(a[5]!=0){
PORTB |= (1<<PB5);
c_flag = 0;
c[5]=0;
Board[1][2]=0;
led[5]=1;
_delay_ms(120);
}
if(a[6]!=0){
PORTB |= (1<<PB6);
c_flag = 0;
c[6]=0;
Board[2][0]=0;
led[6]=1;
_delay_ms(120);
}
if(a[7]!=0){
PORTB |= (1<<PB7);
c_flag = 0;
c[7]=0;
Board[2][1]=0;
led[7]=1;
_delay_ms(120);
}
if(a[8]!=0){
PORTD |= (1<<PD5);
c_flag = 0;
c[8]=0;
Board[2][2]=0;
led[8]=1;
_delay_ms(120);
}
}
c_flag=1;
moveComputer(Board);
led_2();
if_win();
if(win==1){
for(q=0;q<3;q++){
for(u=0;u<3;u++){
Board[q][u]=2;
}
}
ply = 0;
win=0;
break;
}
}
}
Die wichtigsten Funktionen sind OtherPLayer, doWin, NegaMax, moveComputer und pc. USART_Util.h ist eine selbst geschriebene Binliothek, die die wichtigsten USART-Funktionen beinhaltet.
KR-500