Archived from groups: comp.ai.games (
More info?)
Reinhard Gantar a écrit :
> Dear c.a.g.,
>
> I remember a nifty algorithm for finding and judging
> stable disks on the edges of a reversi board. The
> algorithm used a finite state machine for edge-processing,
> scanning each edge as a string of discs (or empty
> fields). The program ("othello.c") has gone from the web and I
> never saved a copy. What's worse: I was not interested
> in the details of the implementation at that time, but
> now I am. I found a few places on the web where the
> method is mentioned, but never with any specifics.
> Any idea where I can find a discussion (or source code)
> of this algorithm? The meat is in how stable disks
> are weighted, and finding out the best weights is
> probably a lot of work.
>
> Kind regards, tip of the propellor hat
> Gantar
>
I don't know what is the algorithm you are refering, but
* You can get an underestimation of stable squares in the edge from the
following simple statements :
- all squares are stable on a full edge.
- corners are stable
- a disc adjacent to a stable disc of the same color is stable
Implementing this in a program is trivial.
* You can get an exact evaluation of stable squares by filling the board
with simulated moves and by noting which squares remain stable. Here is
a simple program showing a possible implementation in C language :
/*
* Compute edge stability
*/
#include <ctype.h>
#include <stdio.h>
/* From a parent edge, produce a child edge
* by playing a 'player' disc at an empty position 'x' */
void move(const char *parent, char *child, int x, char player) {
const char opponent = (player == 'x' ? 'o' : 'x');
int i;
for(i = 0; i < 8; i++) child
= parent;
i = x; while(--i > 0 && child == opponent);
if (child == player)
while(++i < x) child = player;
i = x; while(++i < 7 && child == opponent);
if(child == player)
while(--i > x) child = player;
child[x] = player;
}
/* Look at squares in 'parent' edge that remains stable in the 'child'
edge, store them in the 'stable' array and return the number of
stable squares */
int update_stable(const char *parent, const char *child, char *stable) {
int i, n;
for (i = n = 0; i < 8; i++) {
stable &= (parent == child);
n += stable;
}
return n;
}
/* Confirm the stability of squares in 'parent' edge,
'stable' values initially set to 1 are turned off if unstable */
void confirm_stable(const char *parent, char *stable) {
char child[8];
int i;
for (i = 0; i < 8; i++)
if (parent == '-') {
move(parent, child, i, 'x');
confirm_stable(child, stable);
if (update_stable(parent, child, stable) == 0) return;
move(parent, child, i, 'o');
confirm_stable(child, stable);
if (update_stable(parent, child, stable) == 0) return;
}
}
/* Convert stable booleans into a printable string,
with stable squares seen as upper characters */
void highlight_stable(const char *edge, char *stable) {
int i;
for (i = 0; i < 8; i++) {
if (stable) stable = toupper(edge);
else stable = tolower(edge);
}
}
/* Compute and display stable squares */
void test(const char *edge) {
char stable[] = {1,1,1,1,1,1,1,1};
confirm_stable(edge, stable);
highlight_stable(edge, stable);
printf("%8s -> %8s\n", edge, stable);
}
int main(void) {
test("xxxxxxxx");
test("xxox-xxo");
test("xx-xxxx-");
test("x-oxxxx-");
test("--oxxooo");
test("-xoxxxx-");
test("-x-xxxx-");
return 0;
}
--
Richard
Facebook
Twitter
Instagram