[C] TicTacToe (mit ncurses)

[blackberry]

Hi,

habe mal ncurses ausprobiert.

Bedienung:
Einfach starten und mit den Pfeiltasten navigieren.
Markierungen setzt man mit ENTER, oder durch drücken der Zahlen 0 bis 8.
Zum Verlassen einfach die Leertaste drücken.

Das Spiel neu starten kann man nicht direkt (war mir zu doof die paar Zeilen auch noch zu tippen), also muss man eben das Spiel mit der Leertaste beenden und nochmal starten.

Der Code:

/*
all : ttt

ttt : ttt.c
	gcc -lncurses -o ttt ttt.c

test : ttt
	./ttt

win : ttt
	echo 72386 | ./ttt
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <curses.h>

typedef enum { PLAYER_NONE, PLAYER_X, PLAYER_O, DRAW } E_PLAYERS;
typedef struct _FIELDPOS
{
	WINDOW *wnd;
	struct
	{
		int x;
		int y;
	} start, end;
} FIELDPOS;
#define GETPLAYER(state, fieldid) (((state) >> (2 * fieldid)) & 3)
#define SETPLAYER(state, fieldid, player) state = ((state) & ~(3 << (2 * (fieldid)))) | ((player) << (2 * (fieldid)))
#define OTHERPLAYER(player) (((player) == PLAYER_X) ? PLAYER_O : PLAYER_X)


unsigned int checkwin_player(unsigned int state, E_PLAYERS player)
{
	unsigned int winarr[] = {
		// horizontally
		7, 56, 448,
		// vertically
		73, 146, 292,
		// across
		84, 273
	};
	int i;
	unsigned int checkstate = 0;
	for(i = 0; i < 9; i++)
		if (GETPLAYER(state, i) == player)
			checkstate |= 1 << i;
	for(i = 0; i < sizeof(winarr) / sizeof(winarr[1]); i++)
		if ((checkstate & winarr[i]) == winarr[i])
			return winarr[i];
	return 0;
}

E_PLAYERS checkwin(unsigned int state)
{
	int i;
	if (checkwin_player(state, PLAYER_X))
		return PLAYER_X;
	if (checkwin_player(state, PLAYER_O))
		return PLAYER_O;
	for(i = 0; i < 9; i++)
		if (GETPLAYER(state, i) == PLAYER_NONE)
			return PLAYER_NONE;
	return DRAW;
}

unsigned int ttt_ai_move(unsigned int state, E_PLAYERS ai)
{
	int i;
	unsigned int highest_priority;
	unsigned int pos = 4;
	unsigned int prioritygrid[9];
	int winmoves[][8] = {
		/* 0 */ {1, 2, 3, 6, 4, 8,-1,-1},
		/* 1 */ {0, 2, 4, 8,-1,-1,-1,-1},
		/* 2 */ {0, 1, 5, 8, 5, 6,-1,-1},
		/* 3 */ {0, 6, 4, 5,-1,-1,-1,-1},
		/* 4 */ {0, 1, 2, 3, 5, 6, 7, 8},
		/* 5 */ {3, 4, 2, 8,-1,-1,-1,-1},
		/* 6 */ {0, 3, 7, 8, 4, 2,-1,-1},
		/* 7 */ {6, 8, 1, 4,-1,-1,-1,-1},
		/* 8 */ {6, 7, 2, 5, 0, 4,-1,-1}
	};
	
	memset(prioritygrid, 0, sizeof(prioritygrid));
	
	// we prefer the middle
	prioritygrid[4] = 1;
	
	// detect one-step wins
	for(i = 0; i < 9; i++)
	{
		if (GETPLAYER(state, i) == PLAYER_NONE)
		{
			SETPLAYER(state, i, ai);
			if (checkwin_player(state, ai))
				return i;
			SETPLAYER(state, i, PLAYER_NONE);
		}
	}
	
	// if the other play may win with his/her next move the
	// AI will try to avert this
	for(i = 0; i < 9; i++)
	{
		if (GETPLAYER(state, i) == PLAYER_NONE)
		{
			SETPLAYER(state, i, OTHERPLAYER(ai));
			if (checkwin_player(state, OTHERPLAYER(ai)))
				return i;
			SETPLAYER(state, i, PLAYER_NONE);
		}
	}
	
	// create priority grid
	for(i = 0; i < 9; i++)
	{
		if (GETPLAYER(state, i) != PLAYER_NONE)
		{
			int j;
			for(j = 0; j < 8 && winmoves[i][j] != -1; j++)
			{
				if (GETPLAYER(state, winmoves[i][j]) == PLAYER_NONE)
					prioritygrid[winmoves[i][j]] += 2;
			}
		}
	}
	
	// find best move
	for(i = 0, highest_priority = 0; i < 9; i++)
	{
		if (GETPLAYER(state, i) == PLAYER_NONE && highest_priority < prioritygrid[i])
		{
			highest_priority = prioritygrid[i];
			pos = i;
		}
	}
	return pos;
}

int isgameover(unsigned int state, E_PLAYERS theplayer, WINDOW *info, FIELDPOS fieldpositions[9])
{
	unsigned int fieldid;
	E_PLAYERS winner;
	
	if ((winner = checkwin(state)) != PLAYER_NONE)
	{
		int i;
		char *winstr;
		if (winner == DRAW)
		{
			for(i = 0; i < 9; i++)
			{
				wbkgd(fieldpositions[i].wnd, COLOR_PAIR(3));
				wrefresh(fieldpositions[i].wnd);
			}
			winstr = "Draw.";
		}
		else if (winner == theplayer)
		{
			unsigned int winline = checkwin_player(state, theplayer);
			for(i = 0; i < 9; i++)
			{
				if (winline & (1 << i))
				{
					wbkgd(fieldpositions[i].wnd, COLOR_PAIR(4));
					wrefresh(fieldpositions[i].wnd);
				}
			}
			winstr = "You win!";
		}
		else
		{
			unsigned int winline = checkwin_player(state, OTHERPLAYER(theplayer));
			for(i = 0; i < 9; i++)
			{
				
				if (winline & (1 << i))
				{
					wbkgd(fieldpositions[i].wnd, COLOR_PAIR(3));
					wrefresh(fieldpositions[i].wnd);
				}
			}
			winstr = "You fail!";
		}
		wprintw(info, "\n\n\n----------\n%s\n", winstr);
		wrefresh(info);
		return 1;
	}
	return 0;
}

int main(void)
{
	FIELDPOS fieldpositions[9];
	WINDOW *wnd = 0;
	WINDOW *info = 0;
	int i;
	int gameover = 0;
	E_PLAYERS theplayer = PLAYER_X;
	E_PLAYERS otherplayer = OTHERPLAYER(PLAYER_X);
	int ch;
	struct { int x, y; } cursorpos;
	unsigned int state = 0;
	char *board =
		"(---------------X---------------X---------------)\n"
		"|0              |1              |2              |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|              0|              1|              2|\n"
		"#---------------+---------------+---------------*\n"
		"|3              |4              |5              |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|              3|              4|              5|\n"
		"#---------------+---------------+---------------*\n"
		"|6              |7              |8              |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|               |               |               |\n"
		"|              6|              7|              8|\n"
		"'---------------U---------------U---------------/\n"
	;
	char *boardptr;
	char *playermarks[4] = {
		//---------------
		"               "
		"               "
		"               "
		"               "
		"               "
		"               ",
		//---------------
		"XXXX       XXXX"
		"   XXXX XXXX   "
		"      XXX      "
		"      XXX      "
		"   XXXX XXXX   "
		"XXXX       XXXX",
		//---------------
		"   OOOOOOOOO   "
		" OOOO     OOOO "
		"OO           OO"
		"OO           OO"
		" OOOO     OOOO "
		"   OOOOOOOOO   ",
		//---------------
		"               "
		"               "
		"     state     "
		"     ERROR     "
		"               "
		"               "
		//---------------
	};
	
	cursorpos.x = 0;
	cursorpos.y = 0;
	
	initscr();
	noecho();
	start_color();
	keypad(stdscr, 1);
	//raw();
	
	init_pair(1, COLOR_WHITE, COLOR_BLACK);
	init_pair(2, COLOR_WHITE, COLOR_BLUE);
	init_pair(3, COLOR_WHITE, COLOR_RED);
	init_pair(4, COLOR_WHITE, COLOR_GREEN);
	bkgd(COLOR_PAIR(1));
	
	memset(fieldpositions, 0, sizeof(fieldpositions));
	
	// print the board
	for(boardptr = board; *boardptr; boardptr++)
	{
		chtype ch = 0;
		switch(*boardptr)
		{
			case '(': ch = ACS_ULCORNER; break;
			case ')': ch = ACS_URCORNER; break;
			case '\'': ch = ACS_LLCORNER; break;
			case '/': ch = ACS_LRCORNER; break;
			case '-': ch = ACS_HLINE; break;
			case '|': ch = ACS_VLINE; break;
			case 'X': ch = ACS_TTEE; break;
			case '+': ch = ACS_PLUS; break;
			case '#': ch = ACS_LTEE; break;
			case '*': ch = ACS_RTEE; break;
			case 'U': ch = ACS_BTEE; break;
			case '\n':
				if (!info)
				{
					int x, y;
					getyx(stdscr, y, x);
					info = newwin(20, 25, y + 1, x + 2);
					//wbkgd(info, COLOR_PAIR(2));
				}
				// no break!
			case ' ':
				ch = *boardptr;
		}
		if (*boardptr >= '0' && *boardptr <= '9')
		{
			FIELDPOS *fpos = &fieldpositions[*boardptr - '0'];
			if (fpos->start.x == 0)
			{
				getyx(stdscr, fpos->start.y, fpos->start.x);
			}
			else
			{
				getyx(stdscr, fpos->end.y, fpos->end.x);
				fpos->wnd = newwin(
					fpos->end.y - fpos->start.y + 1,
					fpos->end.x - fpos->start.x + 1,
					fpos->start.y,
					fpos->start.x
				);
			}
			ch = ' ';
		}
		if (ch) addch(ch);
	}
	refresh();
	
	// main loop
	do
	{
		// clear old selection
		if (!gameover && wnd)
		{
			wbkgd(wnd, COLOR_PAIR(1));
			wrefresh(wnd);
		}
		
		// highlight current selection
		if (!gameover)
		{
			wnd = fieldpositions[3 * cursorpos.y + cursorpos.x].wnd;
			wbkgd(wnd, COLOR_PAIR(2));
			wrefresh(wnd);
		}
		
		// print player marks
		for(i = 0; i < 9; i++)
		{
			int mark = GETPLAYER(state, i);
			mvwaddstr(fieldpositions[i].wnd, 0, 0, playermarks[mark]);
			wrefresh(fieldpositions[i].wnd);
		}
		
		switch(ch = getch())
		{
			case KEY_UP:
				if (cursorpos.y > 0) cursorpos.y--;
				break;
			case KEY_DOWN:
				if (cursorpos.y < 2) cursorpos.y++;
				break;
			case KEY_LEFT:
				if (cursorpos.x > 0) cursorpos.x--;
				break;
			case KEY_RIGHT:
				if (cursorpos.x < 2) cursorpos.x++;
				break;
			case '0': case '1': case '2':
			case '3': case '4': case '5':
			case '6': case '7': case '8':
			case '\n':
				if (checkwin(state) != PLAYER_NONE) break;
				
				if (ch != '\n')
				{
					ch -= '0';
					cursorpos.x = ch % 3;
					cursorpos.y = (ch - cursorpos.x) / 3;
				}
				
				i = 3 * cursorpos.y + cursorpos.x;
				if (GETPLAYER(state, i) == PLAYER_NONE)
				{
					unsigned int fieldid;
					E_PLAYERS winner;
					SETPLAYER(state, i, theplayer);
					
					if (isgameover(state, theplayer, info, fieldpositions))
						{ gameover = 1; break; }
					
					fieldid = ttt_ai_move(state, otherplayer);
					SETPLAYER(state, fieldid, otherplayer);
					wprintw(info, "AI -> %d\n", fieldid);
					wrefresh(info);
						
					if (isgameover(state, theplayer, info, fieldpositions))
						{ gameover = 1; break; }
				}
		}
	}
	while(ch != ' ');
	endwin();
	return 0;
}

oder:
http://pastie.org/2532868

Compilieren einfach via GCC. Oben im Sourcecode ist auch noch der Inhalt für ein Makefile im Kommentar, wenn jemand lieber so compiliert.

Über den Code:
Das Feld wird in einem int gespeichert. Dabei werden pro Zelle im Feld je zwei Bits genutzt. Die Werte sehen so aus:

0 = 00b: Zelle ist frei
1 = 01b: Zelle enthält ein "X"
2 = 10b: Zelle enthält ein "O"
3 = 11b: wird nicht benutzt

Die Felder sind wie folgt durchnummeriert:

0 1 2
3 4 5
6 7 8

Das Makro um den Wert auszulesen sieht so aus:
#define GETPLAYER(state, fieldid) (((state) >> (2 * fieldid)) & 3)

Will man eine Markierung setzen macht man das mit diesem Makro:
#define SETPLAYER(state, fieldid, player) state = ((state) & ~(3 << (2 * (fieldid)))) | ((player) << (2 * (fieldid)))
Dabei ist das Makro im Prinzip komplizierter als notwenig, da es die Bits an der Stelle erst alle auf 0 setzt und dann erst den Wert setzt. Das verhindert, dass man irgendwie "X"(=01b) und "O"(=10b) mischt und dann auf den nicht genutzen Zustand kommt (=11b). Im Prinzip wird dieser Fall aber bereits durch die Programmlogik abgefangen (man kann nicht auf bereits gesetzte Felder setzen)...

Der Aufwand mit den Bits scheint zwar überdimensioniert, jedoch vereinfacht sich das Überprüfen gewisser Gewinnsituationen erheblich.
Die Funktion "checkwin" nimmt das Feld als Parameter und ruft "checkwin_player" zwei mal auf. Diese Funktion prüft jeweils, ob ein gewisser Spieler gewonnen hat (darum zwei mal -- jeweils für X und O). Dabei wird das Spielfeld noch einmal komprimiert: ist auf dem i-ten Feld eine Markierung von dem Spieler, der gerade geprüft wird, dann wird das i-te Bit in einem weiteren int auf 1 gesetzt (i=0,...,8).
Nun kann man alle möglichen Gewinnkombinationen in Form von Bitmasken realisieren und dann prüfen, ob die entsprechenden Markierungen gesetzt sind:
if ((checkstate & winarr[i]) == winarr[i])
checkstate ist hier das Feld mit den gesetzten Bits und winarr[i] durchläuft alle möglichen Bitkombinationen:

unsigned int winarr[] = {
	// horizontally
	7, 56, 448,
	// vertically
	73, 146, 292,
	// across
	84, 273
};

Beispielsweise ist 84 = 001010100b und entspricht also dem Feld:

_ _ Z
_ Z _
Z _ _

(Reihenfolge beachten!)

Vielleicht noch kurz zur "KI":
Der Zug wird in 3 Schritten entschieden (wobei nach dem ersten und zweiten Schritt bereits abgebrochen werden kann):
1: es wird geprüft, ob die KI sofort gewinnen kann -- wenn ja wird natürlich sofort dieser Zug genutzt
2: es wird geprüft, ob der Gegner sofort gewinnen könnte -- wenn ja wird natürlich sofort der Zug des Gegners blockiert
3: ist weder 1 noch 2 erfolgreich, so wird eine Wertigkeitstabelle angelegt. Auf die freie Zelle mit der höchsten Wertigkeit wird gesetzt (haben mehrere Zellen die gleiche Wertigkeit, so wird auf die erste von diesen gesetzt).

Die Bewertung erfolgt so:
Das mittlere Feld bekommt von Haus aus eine Wertigkeit von 1 und alle anderen eine von 0 (von der Mitte aus hat man natürlich die meisten Optionen).
Nun wird das Feld anhand der bereits gelegten Steine bewertet. Jedes Feld, das Benutzt werden kann, um zu gewinnen bzw. vom Gegner genutzt werden kann um zu gewinnen wird von der Wertigkeit um 2 erhöht.
Hat man also dieses Feld:

_ _ _
_ _ _
X _ _

so erhält man als Wertigkeitstabelle:

2 0 2
2 3 0
# 2 2
^--- "#" soll hier ein besetztes Feld andeuten;
     diese werden von der KI logischer Weise nicht
     für Züge in Erwägung gezogen)

Dies resultiert also in einem Zug auf die Mitte:

_ _ _
_ O _
X _ _

Im nächsten Schritt setzen wir vielleicht mal auf auf die erste Zelle:

X _ _
_ O _
X _ _

Dies resultiert in:

# 4 4
6 # 2
# 4 6 (hoffentlich habe ich mich hier nicht verrechnet ^-^)

Also wird links neben die Mitte gesetzt (weil höchste Wertung =6 und dies das erste Feld mit dieser Wertung ist):

O _ _
O O _
X _ _

Wie man sieht ist hier kein Zufall involviert (also auch nicht, wenn mehrere Felder die gleiche Wertigkeit erhalten) und die KI handelt immer gleich.
Dass das im Prinzip auch wieder suboptimal ist wird sofort klar, wenn man die Kombination der Züge auf 7, 2, 3, 8, 6 betrachtet, die immer zu einem Sieg führen (wer das ändern will: die Auswahl des Zuges nach der Wertigkeit geht ab Zeile 130 los).


MfG. blackberry