Looking for an influence function (in javascript)

oca · Post by **oca** » Mon Dec 15, 2014 4:35 am

Hi all,

I'm looking for an "influence" function in javascript.

Something I can use like :

var influenceArray = buildInfluence(gameArray);

So before I build my own, did anybody allready have something to share ?

RBerenguel · Post by **RBerenguel** » Mon Dec 15, 2014 5:16 am

oca wrote:Hi all,

I'm looking for an "influence" function in javascript.

Something I can use like :
Code: Select all
var influenceArray = buildInfluence(gameArray);
So before I build my own, did anybody allready have something to share ?

I don't

peepo.com used to show a influence function, as well as some other sites, see here: http://senseis.xmp.net/?InfluenceMap

And you'll definitely be able to use this: http://gameschoolgems.blogspot.com.es/2 ... aps-i.html to avoid having to think too much while implementing a JS version, too.

oca · Post by **oca** » Tue Dec 16, 2014 3:56 am

So Let's try to build one...

May let's start with a simple Zorbist like function...
I'm not 100% sure exactly what the algorythm is but I think it's something like this :
each black stones get a value of 50
each white stones get a value of -50

each position that is adjacent to a black stone get +1 (per adjacent black stone)
each position that is adjacent to a white stone get -1 (per adjacent white stone)
repeat that 4 times ...

so... for a 5x5 borad with only one black stone in the center :

1) set it's value to 50
0 0 0 0 0
0 0 0 0 0
0 0 50 0 0
0 0 0 0 0
0 0 0 0 0

2) apply the transformation one time

0 0 0 0 0
0 0 1 0 0
0 1 50 1 0
0 0 1 0 0
0 0 0 0 0

two times :

0 0 1 0 0
0 2 2 2 0
1 2 54 2 1
0 2 2 2 0
0 0 1 0 0

three times :

0 2 2 2 0
2 4 6 4 2
2 6 58 6 2
2 4 6 4 2
0 2 2 2 0

for times :

2 4 5 4 2
4 8 10 8 4
5 10 62 10 5
4 8 10 8 4
2 4 5 4 2

so given that method, we have got some influence on the whole board here ...

let's try with a black stone and a white stone :

Position :

. . . . .
. . . . .
. X . O .
. . . . .
. . . . .

Influence (after 4 iterations):

x x . o o
x x . o o
x X . O o
x x . o o
x x . o o

4 4 0 -4 -4
7 8 0 -8 -7
8 59 0 -59 -8
7 8 0 -8 -7
4 4 0 -4 -4

One thing that surprise me is that the distance to the border is not taken into consideration... that's weird to me as a stone near the border as not the same influence as a stone in the center is it ?
Anyway... I will now try to see what happend with adding an erosion function (Bouzy's method) like discribed here :

http://www.delorie.com/gnu/docs/gnugo/gnugo_201.html

The code so far is attached to this post.
If you want to try, you can open the html file in a browser on see the message in the console (the inf.js file must be in the same repository than the html file).

or for whose who have node.js intalled, you can just use it too.

Code: Select all

>node inf.js

RobertJasiek · Post by **RobertJasiek** » Tue Dec 16, 2014 4:38 am

What is the purpose of the influence function? I can't help feeling that the only purpose is getting its javascript implementation. However, does really any bad function do or are you asking for a meaningful function?

oca · Post by **oca** » Tue Dec 16, 2014 5:28 am

RobertJasiek wrote:What is the purpose of the influence function? I can't help feeling that the only purpose is getting its javascript implementation. However, does really any bad function do or are you asking for a meaningful function?

Hi Robert,

Well... by curiousity... as I'm interested in understanding how the influence tools works.
And also for study purpose, even if I know that the results is not accurate.

I'm a weak player and still have problems in lots of area, including choosing the best area to play in.

when I play against the computer, I noticed that using the "territory button" help me in deciding where to play and I win more ofen.

I don't use systematicaly that button, which would be a very bad habit I think, I try to separate the games where I play "alone" from the one wher I play "in study mode" with the help of a joseki book, territory analysis tool or "hint" button)

I would by far prefer playing more ofen with a real strong player but I don't have that much opportunity to do that, and the computer is still way better than me anyway so wining without handicap stones is still a big challenge for me.

RBerenguel · Post by **RBerenguel** » Tue Dec 16, 2014 5:39 am

oca wrote:
RobertJasiek wrote:What is the purpose of the influence function? I can't help feeling that the only purpose is getting its javascript implementation. However, does really any bad function do or are you asking for a meaningful function?
Hi Robert,

Well... by curiousity... as I'm interested in understanding how the influence tools works.
And also for study purpose, even if I know that the results is not accurate.

I'm a weak player and still have problems in lots of area, including choosing the best area to play in.

when I play against the computer, I noticed that using the "territory button" help me in deciding where to play and I win more ofen.

I don't use systematicaly that button, which would be a very bad habit I think, I try to separate the games where I play "alone" from the one wher I play "in study mode" with the help of a joseki book, territory analysis tool or "hint" button)

I would by far prefer playing more ofen with a real strong player but I don't have that much opportunity to do that, and the computer is still way better than me anyway so wining without handicap stones is still a big challenge for me.

I love writing exploratory code just for the sake of it, but as for games... Are you sure it's that hard to play with a strong opponent online? I mean, I don't play that much online, but roughly 50% of my opponents are "strong"

or at least, they can beat me

Play more with people and less with computers!

mimano · Post by **mimano** » Tue Dec 16, 2014 6:16 am

Yes but you forget about the not-being-able-to-fall-asleep-plus-having-kids-part! OCA,I understand you

RBerenguel · Post by **RBerenguel** » Tue Dec 16, 2014 6:21 am

mimano wrote:Yes but you forget about the not-being-able-to-fall-asleep-plus-having-kids-part! OCA,I understand you

Yes, I don't have kids, so my free time is more fluid. But I'd rather not play than play computers!

RobertJasiek · Post by **RobertJasiek** » Tue Dec 16, 2014 6:55 am

oca, for just understanding how the influence tool works, you do not even need influence but you can use something similar: proximity. You can start with a simple proximity function: +1 for 'adjacent to more black than white stones', 0 for 'not adjacent to any stone' or 'adjacent to equally many black and white stones', -1 for 'adjacent to more white than black stones'. If this is too simple, then measure Manhattan distances.

Influence is not proximity, so if you really want influence, you must measure influence.

I have defined influence as a 6-tuple per intersection carefully, but for you such a careful influence function is beyond the computational complexity of your program, I suppose. Influence is degrees of connection, life and territory for either player, therefore a 6-tuple. One can treat territory separately, so you can ignore it if you like. The next simplification is consideration of influence at an intersection for only the player having the greater influence degree of a kind there (in your influence function, then positive values favour and denote Black, negative White). This leaves you with two values per intersection.

Connection and life can meaningfully produce different values, but nevertheless you can further simplify and combine the degrees for connection and life: take the value AMBIGUOUS if one value favours Black and the other value favours White or if both values are negative for both players, take the non-negative value n to be the minimum of the connection and life degrees. Here you find the definitions of the degrees:

http://senseis.xmp.net/?NConnection
http://senseis.xmp.net/?NAlive

Further simplification: allow only the values 0, 1 or 2+ for n.

Yes, determination of the minimal value requires the program to read. However, in return you get a very meaningful influence value!

***

Alternative approach: instead of using influence, you can mark the influence stones with significant outside impact (details to be worked out by you), +1 per black influence stone, -1 per white influence stone. Then you can determine a region's influence stone difference from all surrounding influence stones.

Influence stone difference is a concept different from and simpler than influence, but maybe it is good enough for your purpose. It is already much more useful than proximity.

EDITS

oca · Post by **oca** » Tue Dec 16, 2014 7:59 am

RBerenguel wrote: Play more with people and less with computers!

Sure I agree with that advice,

Really, when I have 2 hours available to spent on go, I always choose to go online (IGS for me) and play a real person.
but that's not that ofen that I can play someone that accept to give me stones.
I'm not that a fan of "long term game"... I like to play a "one shot" intense game.

now to the balance coding/playing, well that's a question that comes ofen in my head... "you should play instead of writing code"
but I like writing code too... and I like taking a problem form diffrents prespectives, that helps me to memorize things.

I play against the computer during my travel time to work which is 20 minutes long.
Most of the time, I perfer spending this time doing something else than playing a computer (mainly reading a book, doing a tsumego, or watching a badukmovies video)

oca · Post by **oca** » Wed Dec 17, 2014 12:30 am

Hi Robert,

Thank you very much for that detailed answer !

RobertJasiek wrote:oca, for just understanding how the influence tool works, you do not even need influence
but you can use something similar: proximity.

You can start with a simple proximity function:
+1 for 'adjacent to more black than white stones',
0 for 'not adjacent to any stone' or 'adjacent to equally many black and white stones',
-1 for 'adjacent to more white than black stones'.
If this is too simple, then measure Manhattan distances.

Influence is not proximity, so if you really want influence, you must measure influence.

I have defined influence as a 6-tuple per intersection carefully,
but for you such a careful influence function is beyond the computational complexity of your program, I suppose.

proximity seems to be a good strating point for my exploration as I want to start small and simple.

RobertJasiek wrote: Influence is degrees of connection, life and territory for either player, therefore a 6-tuple.
One can treat territory separately, so you can ignore it if you like.
The next simplification is consideration of influence at an intersection for only the player having the greater influence degree
of a kind there (in your influence function, then positive values favour and denote Black, negative White).
This leaves you with two values per intersection.

Connection and life can meaningfully produce different values, but nevertheless you can further simplify
and combine the degrees for connection and life: take the value AMBIGUOUS if one value favours Black and the
other value favours White or if both values are negative for both players,
take the non-negative value n to be the minimum of the connection and life degrees.
Here you find the definitions of the degrees:

http://senseis.xmp.net/?NConnection
http://senseis.xmp.net/?NAlive

Further simplification: allow only the values 0, 1 or 2+ for n.

Yes, determination of the minimal value requires the program to read. However,
in return you get a very meaningful influence value!

***

Alternative approach: instead of using influence, you can mark the influence stones with significant
outside impact (details to be worked out by you),
+1 per black influence stone, -1 per white influence stone. Then you can determine a region's influence stone difference from all surrounding influence stones.

Influence stone difference is a concept different from and simpler than influence, but maybe it is good enough for your purpose. It is already much more useful than proximity.

EDITS

Thanks again, that's really interseting. lots of stuff to explore...

oca · Post by **oca** » Wed Dec 17, 2014 4:42 am

Click Here To Show Diagram Code: [go]$$B Initial position $$ +-------------------+ $$ | . . . . . . . . . | $$ | . . . . . . . . . | $$ | . . . 4 . . . . . | $$ | . . . . . . . . . | $$ | . . . . 1 . . . . | $$ | . . . . . . . . . | $$ | . . . 3 2 . . . . | $$ | . . . . . . . . . | $$ | . . . . . . . . . | $$ +-------------------+[/go]

Proximity (1 space near including diagonal) : I like that one... we can see black trying to spliting white

Click Here To Show Diagram Code: [go]$$B Proximity $$ +-------------------+ $$ | . . . . . . . . . | $$ | . . o o o . . . . | $$ | . . o O o . . . . | $$ | . . o . . x . . . | $$ | . . . x X x . . . | $$ | . . x x x . . . . | $$ | . . x X O o . . . | $$ | . . x . . o . . . | $$ | . . . . . . . . . | $$ +-------------------+[/go]

Zorbist : Useless ?

Click Here To Show Diagram Code: [go]$$B Zorbist (4 iterations) : $$ +-------------------+ $$ | . o o o o o . . . | $$ | o o o o o o o . . | $$ | o o o O o o o o . | $$ | o o o o x x x x . | $$ | x x x x X x x x x | $$ | x x x x x x x . . | $$ | x x x X O o o o o | $$ | x x x x o o o o . | $$ | . x x x o o o . . | $$ +-------------------+[/go]

Bouzy 5/21 : hmmm... not that bad to me...

Click Here To Show Diagram Code: [go]$$B Bouzy (5 dilations then 21 erosions) $$ +-------------------+ $$ | . . . . . . . . . | $$ | . . . . . . . . . | $$ | . . . O . . . . . | $$ | . . . . . . . . . | $$ | x . . . X . . . . | $$ | x x x . . . . . . | $$ | x x x X O . . . . | $$ | x x x . . . . . . | $$ | x x x . . . . . . | $$ +-------------------+[/go]

Bouzy 4/13 : Funny, nothing here...

Click Here To Show Diagram Code: [go]$$B Bouzy (4 dilations then 13 erosions) $$ +-------------------+ $$ | . . . . . . . . . $$ | . . . . . . . . . $$ | . . . O . . . . . $$ | . . . . . . . . . $$ | . . . . X . . . . $$ | . . . . . . . . . $$ | . . . X O . . . . $$ | . . . . . . . . . $$ | . . . . . . . . . $$ +-------------------+[/go]

Edit

code used :

Code: Select all


var g = [
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,-1,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,1,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,1,-1,0,0,0,0],
	[0,0,0,0,0,0,0,0,0],
	[0,0,0,0,0,0,0,0,0]
];



console.log("Position :");
console.log (toStringBW(g).toUpperCase());

console.log("\nProximity");
console.log (toStringBW(prox(g),g));
console.log("\nZorbist (4 iterations) :");
console.log (toStringBW(zorbist(g),g));
console.log("\nBouzy (5 dilations then 21 erosions)");
console.log (toStringBW(bouzy(g,5,21),g));
console.log("\nBouzy (4 dilations then 13 erosions)");
console.log (toStringBW(bouzy(g,4,13),g));

function prox(p) {
	a = init(p,50);
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = [];
	for (var y = 0;y < size_y; y ++) {
		r[y] = [];
		for (var x = 0;x < size_x; x ++) {
			
			
			var onBoardNearPos = keepPositionsOnBoardOnly(size_x, size_y,near(x,y,1));
			var score = a[y][x];

			for (var i = 0;i < onBoardNearPos.length ; i++) {
				var pos = onBoardNearPos[i];
				if ( a[pos.y][pos.x] > 0) {
					score ++;
				} else if ( a[pos.y][pos.x] < 0) {
					score --;
				}
			}
			r[y][x] = score;
		}
	}
	return r;
}

function zorbist(a) {
	var r = init(g,50);
	var nbIteration = 4;

	for (var i = 0;i< nbIteration;i++) {
		r = z(r);
	}
	return r;
}

/*
 * Compute an "array" of score  for a game position
 */
function z(a) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = [];
	for (var y = 0;y < size_y; y ++) {
		r[y] = [];
		for (var x = 0;x < size_x; x ++) {
			var top =    {pos:"top", x : x,	y : y-1};
			var bottom = {pos:"bottom", x : x,	y : y+1};
			var left =   {pos:"left", x : x-1,	y : y};
			var right =  {pos:"right", x : x+1,	y : y};
			
			var onBoardNearPos = keepPositionsOnBoardOnly(size_x, size_y,[top,bottom,left,right]);
			var score = a[y][x];

			for (var i = 0;i < onBoardNearPos.length ; i++) {
				var pos = onBoardNearPos[i];
				if ( a[pos.y][pos.x] > 0) {
					score ++;
				} else if ( a[pos.y][pos.x] < 0) {
					score --;
				}
			}
			r[y][x] = score;
		}
	}
	return r;
}

/* Taken from : http://www.delorie.com/gnu/docs/gnugo/gnugo_201.html

The algorithm is just : 5 dilations, then 21 erosions.
*/
function bouzy(a,nbDilations, nbErosions) {
	var r = init(a,128);
	for (var d = 0;d< nbDilations; d++) {
		r = dilation(r);
	}
	for (var e = 0;e< nbErosions; e++) {
		r = erosion(r);
	}
	return r;
}

/*
dilation :
--------
for each intersection of the goban,

	if the intersection is >= 0, and not adjacent to a < 0 one, then
		add to the intersection the number of adjacent >0 intersections.

	The same for other color :
	if the intersection is <= 0, and not adjacent to a > 0 one, then
		subtract the number of < 0 intersections.
*/
function dilation(a) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = [];
	for (var y = 0;y < size_y; y ++) {
		r[y] = [];
		for (var x = 0;x < size_x; x ++) {
			var intersection = a[y][x];
			var adj = keepPositionsOnBoardOnly(size_x, size_y, adjacent(x,y));
			var adjacentGreaterThanZero = 0;
			var adjacentLessThanZero = 0;
			for (var i = 0; i<adj.length;i++) {
				var posToCheck = a[adj[i].y][adj[i].x];
				if (posToCheck < 0) {
					adjacentLessThanZero++;
				} else if (posToCheck > 0) {
					adjacentGreaterThanZero++ ;
				}
			}
			var isAdjacentToLessThanZero = (adjacentLessThanZero > 0);
			var isAdjacentToGreaterThanZero = (adjacentGreaterThanZero > 0);
			
			if ((intersection >= 0) &&  (! isAdjacentToLessThanZero)) {
				intersection += adjacentGreaterThanZero;
			} else if ((intersection >= 0) &&  (! isAdjacentToGreaterThanZero)) {
				//intersection += adjacentLessThanZero;
                                intersection -= adjacentLessThanZero;  // FIXED... was bugged
			}
			r[y][x] = intersection;
		}
	}
	return r;
}


/*
erosion :
-------
for each intersection > 0 (or < 0), subtract (or add) the number of adjacent <= 0 (or >= 0) intersection.
Stop at zero.
*/
function erosion(a) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = [];
	for (var y = 0;y < size_y; y ++) {
		r[y] = [];
		for (var x = 0;x < size_x; x ++) {
			var intersection = a[y][x];
			
			var adj = keepPositionsOnBoardOnly(size_x, size_y, adjacent(x,y));
			var adjacentLessOrEqualsToZero = 0;
			var adjacentGreaterorEqualsToZero = 0;
			for (var i = 0; i<adj.length;i++) {
				var posToCheck = a[adj[i].y][adj[i].x];
				if (posToCheck <= 0) {
					adjacentLessOrEqualsToZero++;
				} else if (posToCheck >= 0) {
					adjacentGreaterorEqualsToZero++ ;
				}
			}

			if (intersection > 0) {
				intersection = intersection - adjacentLessOrEqualsToZero;
				if (intersection < 0) {
					intersection = 0;
				}
			} else if (intersection < 0) {
				intersection = intersection + adjacentGreaterorEqualsToZero;
			}
			r[y][x] = intersection;
		}
	}
	return r;
}


/*
 *
 */
function init(a,v) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = [];
	for (var y = 0;y < size_y; y ++) {
		r[y] = [];
		for (var x = 0;x < size_x; x ++) {
			r[y][x] = g[y][x] * v;
		}
	}
	return r;
}

function keepPositionsOnBoardOnly(size_x, size_y, a) {
	var r = [];
	for (var i = 0;i < a.length ; i++) {
		var x = a[i].x;
		var y = a[i].y;
		if ((x >= 0) && (y>=0) && (x < size_x) &&  (y < size_y)) {
			r.push(a[i]);
		}
	}
	return r;
}

function near (x, y, distance) {
	var r = [];
	for (var _y = y-distance; _y<= y+distance ; _y++ ){
		for (var _x = x-distance; _x<= x+distance ; _x++ ){
			r.push({x:_x, y:_y});
		}
	}
	return r;
}

function adjacent(x,y) {
	var top =    {pos:"top", x : x,	y : y-1};
	var bottom = {pos:"bottom", x : x,	y : y+1};
	var left =   {pos:"left", x : x-1,	y : y};
	var right =  {pos:"right", x : x+1,	y : y};
	return [top,bottom,left,right];
}

/*
 * a few rendering functions...
 */
function centerString ( str, width ) {
	var padding = " ";
	padding = padding.substr( 0, 1 );
	if( str.length < width ) {
		var len		= width - str.length;
		var remain	= ( len % 2 === 0 ) ? "" : padding;
		var pads="";
		for (var i = 0;i < parseInt( len / 2 , 10);i++){
			pads = pads + padding;
		}
		return pads + str + pads + remain;
	} else {
		return str;
	}
}
function toStringNum(a) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = "";
	for (var y = 0; y < size_y; y ++) {
		for (var x = 0; x < size_x; x ++) {
			var v = a[y][x].toString();
			r += centerString(v,5);
		}
		r +="\n";
	}
	return "\n"+r;
}
function toStringBW(a,g) {
	var size_y =  a.length;
	var size_x =  a[0].length;
	var r = "";
	for (var y = 0; y < size_y; y ++) {
		for (var x = 0; x < size_x; x ++) {
			var v = a[y][x];
			if (v > 0) {
				if (g && (g[y][x] == 1)) {
					r +="X ";
				} else {
					r +="x ";
				}
			} else if (v < 0){
				if (g && (g[y][x] == -1)) {
					r +="O ";
				} else {
					r +="o ";
				}
			} else {
				r +=". ";
			}
		}
		r +="\n";
	}
	return "\n"+r;
}

oca · Post by **oca** » Wed Dec 17, 2014 6:52 am

oups.. did a small bug... bouzy is more like that :

Code: Select all

Bouzy (5 dilations then 21 erosions)

o o o o o o o . .
o o o o o o o o .
o o o O . . . . .
o o . . . . . . .
. . . . X . . . .
. . . . . . . . .
. . . X O o o o o
. . . . . o o o o
. . . . . o o o .


Bouzy (4 dilations then 13 erosions)

. o o o o o . . .
o o o o o o o . .
o o o O . . . . .
o o . . . . . . .
. . . . X . . . .
. . . . . . . . .
. . . X O o o o o
. . . . . o o o .
. . . . . o o . .

Life In 19x19

Looking for an influence function (in javascript)

Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)

Re: Looking for an influence function (in javascript)