|
|
Umsetzung
|
Im Grunde genommen ist es relativ einfach eine mittelmäßig gut spielende KI für ein 4-Gewinnt-Spiel zu schreiben.
Meine KI "Liebschy" denkt 8 Züge voraus bevor er sich für seinen nächsten Zug entscheidet. Das sind also 4 eigene Züge und
4 mögliche Züge des Gegners. Für alle gefundenen Zugkombinationen wird das Spielfeld bewertet. Diese Bewertungsfunktion und
die Tiefe der Suche ist ausschlaggebend für die Stärke des Computers. Liebschy's oberste Priorität
gilt dem Vereiteln des gegnerischen Sieges. Danach verfolgt die KI einen einfachen Denkansatz:
Um so mehr 3er und 2er Reihen im Spiel gefunden werden, umso besser wird die Position bewertet.
Die eigene Position ist also umso besser um so mehr eigene 3er und 2er und umso weniger gegnerische 3er
und 2er vorhanden sind. Der Ansatz ist natürlich relativ einfach aber führt schon zu ganz aktzeptablen
Spiel. Beim Berechnen des nächsten Zuges geht der Algorithmus stets davon aus, dass der Gegner den
(nach der Bewertungsfunktion) besten Zug macht.
Man könnte jetzt an dieser Stelle einen einfachen Suchbaum aufspannen und wirklich alle Kombinationen
durchkämmen. Genau das macht der Minimax-Algorithmus mit seinen zwei rekursiven Funktionen minValue und maxValue
die sich gegenseitig aufrufen.
Jedoch müssten dann 7*7*7*7*7*7*7*7 = 5.764.801 mögliche Spielpositionen bewertet werden
was selbstverständlich viel zu lange dauern würde.
Man kann die Suche deutlich verkürzen indem nicht alle Suchpfade durchlaufen werden sondern vorher schon festgestellt
wird, ob der Suchpfad ein besseres Ergebnis liefern kann oder nicht.
Diese optimierte Suche ist auch unter der AlphaBeta-Suche bekannt. Detallierte Beschreibungen finden sich zu genüge im Netz.
Vielleicht werde ich hier noch ein paar exemplarische Grafiken zum besseren Verständnis reinstellen.
|
Hier erstmal der Quelltext in C
/*
QuadRulezOut game
QuadRulezOut engine - Liebschy 0.9.7
Author: Maik Pflugradt
last modified: 20. January 2009
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SEARCH_DEPTH 6
#define BOARD_Y_LENGTH 6
#define RED_STONE 1
#define YELLOW_STONE -1
#define EMPTY 0
#define VALUE_PAIR 2
#define VALUE_TRIPPLE 10
#define VALUE_QUAD 1000
#define MAX_RESULT 10000
#define MIN_RESULT -10000
#define DEBUG
int board[7][BOARD_Y_LENGTH];
void init_board();
void print_board();
void copy_board(int a[7][BOARD_Y_LENGTH], int b[7][BOARD_Y_LENGTH]);
void undo_last_move(int column);
void swap(int i, int j);
void fill_column_array();
int insert_stone(int stone,int column);
int get_horizontal_lines(int length,int color);
int get_vertical_lines(int length,int color);
int get_diagonal_lines(int length,int color);
int evaluate_position(int color);
int is_board_full();
int get_random_number(int x);
char ch;
char solution;
int color = 1;
int columnArray[6];
int main()
{
init_board();
printf(">> ");
ch = getch();
printf("%c \n",ch);
while(ch != 'e'){
switch(ch){
case '0': insert_stone(color,0); color *= -1; break;
case '1': insert_stone(color,1); color *= -1; break;
case '2': insert_stone(color,2); color *= -1; break;
case '3': insert_stone(color,3); color *= -1; break;
case '4': insert_stone(color,4); color *= -1; break;
case '5': insert_stone(color,5); color *= -1; break;
case '6': insert_stone(color,6); color *= -1; break;
case 'i': init_board();break;
case 'p': print_board(); break;
case 's': printf("red score: %d yellow score: %d \n",evaluate_position(RED_STONE),evaluate_position(YELLOW_STONE)); break;
case 'c':
//maxValue(color,SEARCH_DEPTH);
maxValueAB(color,SEARCH_DEPTH,MIN_RESULT,MAX_RESULT);
insert_stone(color,solution);color *= -1;
printf("Liebschy chose column %d\n",solution);
break;
default: printf("invalid command\n");
}
if(evaluate_position(RED_STONE)>=VALUE_QUAD)
printf("RED has won!\n");
if(evaluate_position(YELLOW_STONE)>=VALUE_QUAD)
printf("YELLOW has won!\n");
if(is_board_full())
if(abs(evaluate_position(RED_STONE)) <= VALUE_QUAD)
printf("draw!\n");
printf(">> ");
ch = getch();
printf("%c \n",ch);
}
return 0;
}
int get_random_number(int i){
return 0;
} /* implementation for generating random numbers comes here */
void fill_column_array(){
int t1,t2,i;
for(i=0; i<=6; i++)
columnArray[i] = i;
for(i=0; i<=6; i++){
t1 = get_random_number(7);
t2 = get_random_number(7);
swap(t1,t2);
}
}
void swap(int i, int j){
int temp = columnArray[i];
columnArray[i] = columnArray[j];
columnArray[j] = temp;
}
int maxValueAB(int color, int depth,int alpha, int beta){
int i;
int t;
int currentValue;
if(depth == 0)
return evaluate_position(color);
for(i=0;i<=6;i++){
t = columnArray[i];
if(insert_stone(color,t) != -1){
if(is_board_full()!=1)
currentValue = minValueAB(color*(-1),depth-1,alpha,beta);
else
currentValue = minValueAB(color*(-1),0,alpha,beta);
undo_last_move(t);
if (currentValue >= beta)
return beta;
if (currentValue > alpha){
if(depth == SEARCH_DEPTH )
solution = t;
alpha = currentValue;
}
}
}
return alpha;
} /* advanced minimax algorithm using alpha beta search */
int minValueAB(int color, int depth, int alpha, int beta){
int i;
int t;
int currentValue;
if (depth == 0)
return evaluate_position(color);
for(i=0;i<=6;i++){
t = columnArray[i];
if(insert_stone(color,t) != -1){
if(is_board_full()!=1)
currentValue = maxValueAB(color*(-1),depth-1,alpha,beta);
else
currentValue = maxValueAB(color*(-1),0,alpha,beta);
undo_last_move(t);
if (currentValue <= alpha)
return alpha;
if (currentValue < beta)
beta = currentValue;
}
}
return beta;
} /* advanced minimax algorithm using alpha beta search */
int maxValue(int color,int depth){
int result = MIN_RESULT;
int currentValue;
int i;
for(i=0; i<=6; i++){
if(insert_stone(color,i) != -1){
if(depth <= 0)
currentValue = (evaluate_position(color));
else
currentValue = minValue(color*(-1),depth-1);
undo_last_move(i);
if(currentValue > result){
result = currentValue;
if(depth == SEARCH_DEPTH )
solution = i;
}
}
}
return result;
} /* find best own move using minimax algorithm*/
int minValue(int color,int depth){
int result = MAX_RESULT;
int currentValue;
int i;
for(i=0; i<=6; i++){
if((insert_stone(color,i) != -1)){
if(depth <= 0)
currentValue = evaluate_position(color);
else
currentValue = maxValue(color*(-1),depth-1);
undo_last_move(i);
if(currentValue < result)
result = currentValue;
}
}
return result;
} /* find best move for opponent using minimax algorithm */
void copy_board(int a[7][BOARD_Y_LENGTH] ,int b[7][BOARD_Y_LENGTH]){
int x,y;
for(x=0;x<7;x++)
for(y=0;y<BOARD_Y_LENGTH;y++)
a[x][y] = b[x][y];
} /* copy board array
bad idea, very time consuming*/
int evaluate_position(int color){
int result = 0;
if ((get_horizontal_lines(4,color*(-1)) || (get_vertical_lines(4,color*(-1)) || get_diagonal_lines(4,color*(-1))))){
return (-1)*VALUE_QUAD;
}
if ((get_horizontal_lines(4,color) || (get_vertical_lines(4,color) || get_diagonal_lines(4,color)))){
return VALUE_QUAD;
}
result += (VALUE_TRIPPLE) * (get_horizontal_lines(3,color) + get_vertical_lines(3,color) + get_diagonal_lines(3,color));
result += VALUE_PAIR * (get_horizontal_lines(2,color) + get_vertical_lines(2,color) + get_diagonal_lines(2,color));
result -= VALUE_TRIPPLE * (get_horizontal_lines(3,color*(-1)) + get_vertical_lines(3,color*(-1)) + get_diagonal_lines(3,color*(-1)));
result -= VALUE_PAIR * (get_horizontal_lines(2,color*(-1)) + get_vertical_lines(2,color*(-1)) + get_diagonal_lines(2,color*(-1)));
return result;
} /* count all pairs , tripples and quads
returns an integer between [-VALUE_QUAD,VALUE_QUAD]
positive numbers represent a good position
negative numbers represent a bad position
*/
int get_horizontal_lines(int length,int color){
int y,x,t = 0;
int hit,total_hits = 0;
if(length>4 || length<2)
return 0;
for(y=0;y<BOARD_Y_LENGTH;y++){
for(x=0;x<=(7-length);x++){
hit = 1;
for(t=1;t<length;t++){
if((board[x+t][y] != board[x][y]) || (board[x+t][y]!=color))
hit = 0;
}
total_hits += hit;
}
}
return total_hits;
} /* counts horizontal groups in each row */
int get_vertical_lines(int length, int color){
int y,x,t = 0;
int hit,total_hits = 0;
if(length>4 || length<2)
return 0;
for(x=0;x<7;x++){
for(y=0;y<=(BOARD_Y_LENGTH-length);y++){
hit = 1;
for(t=1;t<length;t++){
if((board[x][y+t] != board[x][y]) || (board[x][y+t]!=color))
hit = 0;
}
total_hits += hit;
}
}
return total_hits;
} /* counts vertical groups in each column */
int get_diagonal_lines(int length, int color){
int y,x,t = 0;
int hit,total_hits = 0;
for(x=0;x<=(7-length);x++){
for(y=0;y<=(BOARD_Y_LENGTH-length);y++){
hit = 1;
for(t=1;t<length;t++){
if((board[x+t][y+t] != board[x][y]) || (board[x+t][y+t]!=color))
hit = 0;
}
total_hits += hit;
}
}
for(x=6;x>=(length-1);x--){
for(y=0;y<=(BOARD_Y_LENGTH-length);y++){
hit = 1;
for(t=1;t<length;t++){
if((board[x-t][y+t] != board[x][y]) || (board[x-t][y+t]!=color))
hit = 0;
}
total_hits += hit;
}
}
return total_hits;
} /* count diagonal groups */
int insert_stone(int stone, int column){
int y=BOARD_Y_LENGTH-1;
if(board[column][y]!=EMPTY)
return -1;
if(column<0 || column>6)
return -1;
while(y>0 && board[column][y-1]==EMPTY)
y--;
board[column][y] = stone;
return 0;
} /* inserts stone into board
return 0 on valid move
return -1 on invalid move */
void undo_last_move(int column){
int y=BOARD_Y_LENGTH-1;
while(y >= 0){
if(board[column][y] != EMPTY){
board[column][y] = EMPTY;
return;
}
y--;
}
} /* removes stone inserted in board */
void print_board(){
int x,y = 0;
printf(" -------\n");
for(y=BOARD_Y_LENGTH-1; y>=0; y--){
printf("|");
for(x=0; x<7;x++){
switch(board[x][y]){
case EMPTY: printf(" "); break;
case RED_STONE: printf("x"); break;
case YELLOW_STONE: printf("o"); break;
}
}
printf("|\n");
}
printf(" -------\n 0123456\n\n");
} /* print board on console */
int is_board_full(){
int x,y = 0;
for(x=0; x<7; x++)
for(y=0;y<BOARD_Y_LENGTH; y++)
if(board[x][y] == EMPTY)
return 0;
return 1;
}
void init_board(){
int x,y = 0;
fill_column_array();
for(x=0; x<7; x++)
for(y=0;y<BOARD_Y_LENGTH; y++)
board[x][y] = EMPTY;
}
|
|