eval.c

一遗传算法的例子源程序

#include <string.h>
#include "lithos.h"

#define boardSize 19
#define squares (boardSize * boardSize)

#define DISPUTED 3

static char board[boardSize][boardSize];
#define boardv (board[0])

static char oldBoard[boardSize][boardSize];
static char mark[boardSize][boardSize];

static int score0, score1;
static int pass;
static int prisoners;

static int liberty2(int i, int j)
{
	int color;
	if (mark[i][j])
		return 0;
	mark[i][j] = 1;
	color = board[i][j];
	if (i > 0)
	{
		int color1 = board[i - 1][j];
		if (!color1)
			return 1;
		if (color1 == color && liberty2(i - 1, j))
			return 1;
	}
	if (i < boardSize - 1)
	{
		int color1 = board[i + 1][j];
		if (!color1)
			return 1;
		if (color1 == color && liberty2(i + 1, j))
			return 1;
	}
	if (j > 0)
	{
		int color1 = board[i][j - 1];
		if (!color1)
			return 1;
		if (color1 == color && liberty2(i, j - 1))
			return 1;
	}
	if (j < boardSize - 1)
	{
		int color1 = board[i][j + 1];
		if (!color1)
			return 1;
		if (color1 == color && liberty2(i, j + 1))
			return 1;
	}
	return 0;
}

static int liberty(int i, int j)
{
	if (!board[i][j])
		return 1;
	memset(mark, 0, sizeof mark);
	return liberty2(i, j);
}

static void removeGroup(int i, int j)
{
	int color = board[i][j];
	board[i][j] = 0;
	prisoners++;
	if (i > 0 && board[i - 1][j] == color)
		removeGroup(i - 1, j);
	if (i < boardSize - 1 && board[i + 1][j] == color)
		removeGroup(i + 1, j);
	if (j > 0 && board[i][j - 1] == color)
		removeGroup(i, j - 1);
	if (j < boardSize - 1 && board[i][j + 1] == color)
		removeGroup(i, j + 1);
}

static void capture2(int i, int j)
{
	if (!liberty(i, j))
		removeGroup(i, j);
}

static void capture(int i, int j)
{
	prisoners = 0;
	if (i > 0)
		capture2(i - 1, j);
	if (i < boardSize - 1)
		capture2(i + 1, j);
	if (j > 0)
		capture2(i, j - 1);
	if (j < boardSize - 1)
		capture2(i, j + 1);
}

static int move(Instruction *code, int size, int *memory, int color)
{
	int i, j;
	if (color > 0)
	{
		for (i = 0; i < squares; i++)
			memory[i] = boardv[i];
		memory[squares] = score0;
		memory[squares + 1] = -score1;
	}
	else
	{
		for (i = 0; i < squares; i++)
			memory[i] = -boardv[i];
		memory[squares] = score1;
		memory[squares + 1] = -score0;
	}
	exec(code, size, memory);
	j = pop();
	i = pop();
	if (i < 0 || i >= boardSize ||
		j < 0 || j >= boardSize ||
		board[i][j])
	{
		if (pass)
			return 0;
		pass = 1;
		return 1;
	}
	board[i][j] = color;
	capture(i, j);
	if (!prisoners && !liberty(i, j))
	{
		board[i][j] = 0;
		if (pass)
			return 0;
		pass = 1;
		return 1;
	}
	pass = 0;
	return 1;
}

static void play(int size0, int size1)
{
	int i;
	memset(board, 0, sizeof board);
	memset(memory0, 0, maxMemory * sizeof(int));
	memset(memory1, 0, maxMemory * sizeof(int));
	score0 = 0;
	score1 = 0;
	pass = 0;
	for (i = 0; i < maxMoves; i++)
	{
		if (!move(code0, size0, memory0, 1))
			break;
		score0 += prisoners;
		if (!move(code1, size1, memory1, -1))
			break;
		score1 += prisoners;
	}
}

static int disputes(int i, int j, int color)
{
	int color1 = board[i][j];
	if (color1 == DISPUTED)
		return 1;
	if (color1 < 0 && color > 0 ||
		color1 > 0 && color < 0)
		return 1;
	return 0;
}

static int sign(int x)
{
	if (x < 0)
		return -1;
	if (x > 0)
		return 1;
	return 0;
}

static void markTerritory()
{
	int i, j;
	int changed;
	for (i = 0; i < squares; i++)
		boardv[i] *= 2;

	do
	{
		changed = 0;
		for (i = 0; i < boardSize; i++)
			for (j = 0; j < boardSize; j++)
			{
				int color = board[i][j];
				if (color < -1 || color > 1)
					continue;

				if (i > 0 && disputes(i - 1, j, color) ||
					i < boardSize - 1 && disputes(i + 1, j, color) ||
					j > 0 && disputes(i, j - 1, color) ||
					j < boardSize - 1 && disputes(i, j + 1, color))
				{
					board[i][j] = DISPUTED;
					changed = 1;
					continue;
				}

				if (color)
					continue;

				if (i > 0)
				{
					int color1 = board[i - 1][j];
					if (color1)
					{
						board[i][j] = sign(color1);
						changed = 1;
						continue;
					}
				}
				if (i < boardSize - 1)
				{
					int color1 = board[i + 1][j];
					if (color1)
					{
						board[i][j] = sign(color1);
						changed = 1;
						continue;
					}
				}
				if (j > 0)
				{
					int color1 = board[i][j - 1];
					if (color1)
					{
						board[i][j] = sign(color1);
						changed = 1;
						continue;
					}
				}
				if (j < boardSize - 1)
				{
					int color1 = board[i][j + 1];
					if (color1)
					{
						board[i][j] = sign(color1);
						changed = 1;
						continue;
					}
				}
			}
	}
	while (changed);

	for (i = 0; i < squares; i++)
		if (boardv[i] == DISPUTED)
			boardv[i] = 0;
		else
			boardv[i] = sign(boardv[i]);
}

static void printBoard()
{
	int i, j;
	for (i = 0; i < boardSize; i++)
	{
		for (j = 0; j < boardSize; j++)
			switch (oldBoard[i][j])
			{
			case -1:
				putchar('O');
				break;
			case 0:
				putchar('.');
				break;
			case 1:
				putchar('*');
				break;
			}
		putchar(' ');
		for (j = 0; j < boardSize; j++)
			switch (board[i][j])
			{
			case -1:
				putchar('O');
				break;
			case 0:
				putchar('.');
				break;
			case 1:
				putchar('*');
				break;
			}
		putchar('\n');
	}
}

void evaluate()
{
	int i, j;
	Program *p = &programs[evaluated];
	unpack(p, code0);
	p->fitness -= p->size;

	for (i = 0; i < population; i++)
	{
		if (i == evaluated)
			continue;

		unpack(&programs[i], code1);
		play(p->size, programs[i].size);

		if (evaluated == 0 && i == 1)
			memcpy(oldBoard, board, sizeof board);

		markTerritory();
		for (j = 0; j < squares; j++)
			switch (boardv[j])
			{
			case -1:
				score1++;
				break;
			case 1:
				score0++;
				break;
			}

		if (score0 > score1)
			p->fitness += maxSize + 1;
		else
			programs[i].fitness += maxSize + 1;

		if (evaluated == 0 && i == 1)
		{
			score = score0;
			printBoard();
		}
	}
}