Yangbo's Blog!

Artificial Intelligence Board Game.
Browsing BoardGame(民间棋类游戏)

Bitboards

April8

AS3 BitBoard(based-on BitVector) preview:
This is our ChineseChess as3 bitboard:
[R][K][B][O][M][O][B][K][R]
[0][0][0][0][0][0][0][0][0]
[0][C][0][0][0][0][0][C][0]
[P][0][P][0][P][0][P][0][P]
[0][0][0][0][0][0][0][0][0]
[0][0][0][0][0][0][0][0][0]
[p][0][p][0][p][0][p][0][p]
[0][C][0][0][0][0][0][C][0]
[0][0][0][0][0][0][0][0][0]
[r][k][b][o][m][o][b][k][r]
Operations:

and

public function and(value:BitBoard):BitBoard
		{
			var bb:BitBoard =
new BitBoard(this.column,this.row);
			for(var h:int=0;h<_row;h++)
			{
				for(var w:int=0;w<_column;w++)
				{
					bb.setBitt(h,w,
Boolean((value.getBitt(h,w)&this.getBitt(h,w))));
				}
			}
			return bb;
		}


xor

public function xor(value:BitBoard):BitBoard
		{
			var bb:BitBoard =
new BitBoard(this.column,this.row);
			for(var h:int=0;h<_row;h++)
			{
				for(var w:int=0;w<_column;w++)
				{
					bb.setBitt(h,w,
Boolean((value.getBitt(h,w)^this.getBitt(h,w))));
				}
			}
			return bb;
		}


or

public function or(value:BitBoard):BitBoard
		{
			var bb:BitBoard =
new BitBoard(this.column,this.row);
			for(var h:int=0;h<_row;h++)
			{
				for(var w:int=0;w<_column;w++)
				{
					bb.setBitt(h,w,
Boolean((value.getBitt(h,w)|this.getBitt(h,w))));
				}
			}
			return bb;
		}


not

public function not():BitBoard
		{
			var bb:BitBoard =
new BitBoard(this.column,this.row);
			for(var h:int=0;h<_row;h++)
			{
				for(var w:int=0;w<_column;w++)
				{
					bb.setBitt(h,w,
!Boolean(this.getBitt(h,w)));
				}
			}
			return bb;
		}


rotate

public function rotate90():BitBoard
		{
			var bb:BitBoard =
new BitBoard(_row,_column);
			for(var w:int=0;w<_row;w++)
			{
				for(var h:int=0;h<_column;h++)
				{
					bb.setBitt(h,w,
Boolean(this.getBitt(w,h)));
				}
			}
			return bb;
		}


reverse

public function reverse():BitBoard
		{
			var bb:BitBoard =
new BitBoard(this.column,this.row);
			for(var w:int=0;w<_column;w++)
			{
				for(var h:int=0;h<_row;h++)
				{
					bb.setBitt(h,w,
Boolean(this.getBitt(_row-h-1,w)));
				}
			}
			return bb;
		}
This page is wiki editable click here to edit this page.

The2Tigers(二虎棋)

August24


Example:



Code snippet


Supplmentary interpretation

Thinking...
Fuzzy logic, whenever is safty,wherever is dangerous?

This page is wiki editable click here to edit this page.

The3Directs(三通棋)

August24


Example:


First off,three key words:
1.adjacent;
2.opposite;
3.hypotenuse;
Next,how to draw triangle using Degrafa?

Code snippet:

<Polygon   fill="{upFill}">
    <data>0,70 40,0 80,70</data>
</Polygon>

rotate 180 degree?

<Polygon   fill="{upFill}">
   <transform>
        <RotateTransform angle="180" centerX="40" centerY="35"/>
   </transform>
    <data>0,70 40,0 80,70</data>
</Polygon>


Supplmentary interpretation

Next,how to determine the 3 directs? Using the graph data struct to finding simple path existed from adjacent to opposite and
from adjacent to hypotenuse and from opposite to hypotenuse.the simple path finding searcher function as follows:

1.Dijkstra:

package jp.dip.hael.gameai.graph.searcher
{
	import jp.dip.hael.gameai.graph.GraphEx;
	import jp.dip.hael.gameai.graph.Edge;
	import jp.dip.hael.gameai.graph.WeightedEdge;
	import jp.dip.hael.gameai.util.PriorityQueueDsc;

	public class Dijkstra extends Searcher
	{
		public function Dijkstra(graph:GraphEx)
		{
			super(graph);
		}

		public override function search(src:int, dst:int):Boolean
		{
			var pq:PriorityQueueDsc = new PriorityQueueDsc();
			pq.insert(new Edge(src, src), 0);

			var route:Array /* of int */ = new Array(graphRef_.size);
			var weight:Array /* of int */ = new Array(graphRef_.size);

			while(pq.length > 0){
				var next:Edge = pq.popObj() as Edge;
				route[next.dst] = next.src;

				if(next.dst == dst){
					src_ = src;
					dst_ = dst;
					route_ = route;
					found_ = true;
					return true;
				}

				var dsts:Array = graphRef_.edge(next.dst);
				for each(var e:WeightedEdge in dsts){
					if(route[e.dst] === undefined){
						var w:int = (weight[next]>>0) + e.weight;
						weight[e.dst] = w;
						pq.insert(e, w);
					}
				}
			}

			return false;
		}

	}
}

2.Bread-first traversal:

override public function search(src:int, dst:int):Boolean
{
	var queue:Array /* of Edge */ = [];
	queue.push(new Edge(src, src));

	var visited:Array /* of Boolean */ = new Array(graphRef_.size);
	visited[src] = true;

	var route:Array /* of int */ = new Array(graphRef_.size);

	while(queue.length > 0){
		var next:Edge = queue.shift();
		route[next.dst] = next.src;

		if(next.dst == dst){
			src_ = src;
			dst_ = dst;
			route_ = route;
			found_ = true;
			return true;
		}

		var dsts:Array = graphRef_.edge(next.dst);
		for each(var e:Edge in dsts){
			if(!visited[e.dst]){
				queue.push(e);
				visited[e.dst] = true;
			}
		}
	}

	return false;
}

3.Depth-first traversal:

override public function search(src:int, dst:int) : Boolean
{
	var queue:Array /* of Edge */ = [];
	queue.push(new Edge(src, src));

	var visited:Array /* of Boolean */ = new Array(graphRef_.size);
	visited[src] = true;

	var route:Array /* of int */ = new Array(graphRef_.size);

	while(queue.length > 0){
		var next:Edge = queue.pop();
		route[next.dst] = next.src;

		if(next.dst == dst){
			src_ = src;
			dst_ = dst;
			route_ = route;
			found_ = true;
			return true;
		}

		var dsts:Array = graphRef_.edge(next.dst);
		for each(var e:Edge in dsts){
			if(!visited[e.dst]){
				queue.push(e);
				visited[e.dst] = true;
			}
		}
	}

	return false;
}

...

This page is wiki editable click here to edit this page.

The5Elements(手工五行棋)

August24


Example:


First off, make chess board:

Code snippet:

<degrafa:Surface>
	<degrafa:strokes>
		<paint:SolidStroke    id="whiteStroke"
				      color="#FFF"
				      weight="1"
				      alpha=".5"/>
	</degrafa:strokes>

	<degrafa:GeometryGroup>
		<geometry:RegularRectangle id="hRegularRect" width="150" height="450" x="{150+PADDING}" y="{PADDING}" stroke="{whiteStroke}"/>
		<geometry:RegularRectangle id="vRegularRect" width="450" height="150" y="{150+PADDING}" x="{PADDING}" stroke="{whiteStroke}"/>
	</degrafa:GeometryGroup>
</degrafa:Surface>


Supplmentary interpretation

How to find all simple paths which length limited by 5,such as a-b-c-d-e?

override public function searchAll(src:int, dst:int, visited:ArrayCollection) : void
{
	var nodes:Array = new Array();
	if(!(graphRef_.edge(src) is Array))
	{
		return;
	}
	for(var i:int=0;i<graphRef_.edge(src).length;i++)
	{
		nodes.push( (graphRef_.edge(src)[i] as WeightedEdge).dst );
	}
	//trace("nodes:",nodes);
	for(var node:* in nodes)
	{
		//trace("~node:",node,"nodes[node]",nodes[node]);
		if(visited.contains(nodes[node]))
		{
			continue;
		}
		if(int(nodes[node])==dst)
		{
			visited.addItem(nodes[node]);
			//restore this path.
			saveToAllSimplePaths(visited);
			visited.removeItemAt(visited.length-1);
			break;
		}
	}
	 // in breadth-first, recursion needs to come after visiting adjacent nodes
	for(var node2:* in nodes)
	{
		//trace("~~node:",node,"nodes[node]",nodes[node]);
		if(visited.contains(nodes[node2])||int(nodes[node2])==dst)
		{
			continue;
		}
		visited.addItem(nodes[node2]);
		searchAll(nodes[node2],dst,visited);
		visited.removeItemAt(visited.length-1);
	}
}
This page is wiki editable click here to edit this page.
« Older Entries

BLOG CALENDAR

September 2010
M T W T F S S
« Apr    
 12345
6789101112
13141516171819
20212223242526
27282930