/home/ug/devel/kombilo-py-dev/kombilo/libkombilo/algos.h File Reference

#include <vector>
#include <stack>
#include <fstream>
#include "sqlite3.h"
#include "pstdint.h"
#include <boost/unordered_map.hpp>
#include "abstractboard.h"
#include "sgfparser.h"
#include "pattern.h"

Go to the source code of this file.

Data Structures
class	Algorithm
class	Algo_signature
	This algorithm computes the symmetrized Dyer signature of each game. More...
class	Algo_finalpos
class	MovelistCand
class	VecMC
class	Algo_movelist
class	HashhitF
class	HashhitCS
class	HashVarInfo
class	Algo_hash_full
	Hashing for full board patterns. More...
class	HashInstance
class	Algo_hash
	Base class for hashing for general type patterns (currently works only for corner patterns). More...
class	Algo_hash_corner
	Hashing for corner patterns. More...

Typedefs
typedef vector< HashhitF * > *	vpsip
typedef Algorithm *	algo_p

Variables
const int	ENDOFNODE = 128
const int	BRANCHPOINT = 64
const int	ENDOFVARIATION = 32
const int	REMOVE = 128
const int	BLACK = 64
const int	WHITE = 32

Detailed Description

part of libkombilo, http://www.u-go.net/kombilo/

Copyright (c) 2006-12 Ulrich Goertz ug@ge.nosp@m.omet.nosp@m.ry.de

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Basic information

Coordinate system

We use the following coordinate system (given here for board size 19x19):

(0,0) ---------------------- (18,0)
  |                             |
  |                             |
  |                             |
  |                             |
  |                             |
  |                             |
  |                             |
  |                             |
(0,18) --------------------- (18,18)

This corresponds nicely to the system used by SGF ((0,0) = aa, (18,18) = ss).

Board symmetries

There are 8 symmetries of the square, and hence of the go board. We enumerate them as follows (to simplify notation, we give the maps for boardsize 19). A point with coordinates (x,y) is mapped to

0. (x,y)

1. (18-x, y)
   
2. (x, 18-y)
   
3. (18-x, 18-y)
   
4. (y, x)
   
5. (18-y, x)
   
6. (y, 18-x)
   
7. (18-y, 18-x)
   

So for instance the symmetry 0 is the identity map, and symmetry 1 is reflection with respect to the vertical axis.

Furthermore, given a position, there is the color swap which exchanges black and white stones.

The corresponding PatternList is a list of all reflections, rotations etc. of the pattern, in other words the set of images of the patterns under symmetries of the board.

Continuations

When doing a pattern search, we want to keep track of possible continuations. Of course, for images of the original pattern under a symmetry, any continuation has to be "re-mapped" to the original pattern. Furthermore, when showing continuations, symmetry needs to be taken into account, for instance in

+--------
|........
|........
|.....a..
|...X....
|........
|..b.....
|........
|........

the positions a and b are equivalent, and only one of them should be shown as a possible continuation. To keep track of all this, we use, for each pattern in the pattern list, a dictionary Symmetries such that if a continuation is played in the pattern at the point (i,j), then Symmetries[color, i, j] == (c,x,y) which means that the result should be shown at (x,y) in the original pattern with color c. ('color' is the color (black/white) of the continuation.)