Thanx for all this :)

I still dont understand why my new version of the engine beats the previous one
lol. Each time I slightly change my amendments to the engine, it doesnt win
anymore. Therefore, conceptually, no conclusion so far.

If the board dispays WBWW, searching for WBW , is similar to searching for a
.BWW sumito but earlier in the search tree. It's probably a sumito threat.

By considering this type of sumito threat, i'm probably influencing the horizon
effect too :)

Therefore i'm currently lost ;) We'll wait for the next episode :)

Searching for WBW or WBBW patterns is very similar to performing legal move
generation. I fully implemented legal moves generation with bitboards 6 months
ago (with the same programming language), and it didnt prove to be faster than
the current move generation in MLA (so i gave it up, i might try to use it in
the near future but only if i can use assembly code and prove to be faster).

In MLA, in line move generation is performed as follows :

If the board shows in a given direction something like

BBBWWE (where E means Empty)

let's assume that :

0 means white
1 means black
2 means empty
3 means outside of the board

in BBBWWE, let's ignore the first character, BBWWE can be written

1 1 0 0 2

MLA computes a number (called the move number in my source code) as follows :

(((1 + 4 x 1) x 4 + 0) x 4 + 0) x 4 + 2 = 322

I have an array telling me than 322 is a legal move for black.

To compute the resulting board, i.e. EBBBWW.

322 (for black) is also associated the list of board changes
vector "0 0 1 0 -2":

1 1 0 0 2

added to

0 0 1 0 -2

gives

1 1 1 0 0

I'm pushing a black marble therefore the first position is empty. we get :

2 1 1 1 0 0 i.e. EBBBWW

Note that using bitboards means using XORs and logicial shift to do this (i.e.
recycling as you called it in the previous message). But using bitboards is
slower because i need to build the long integers for each row in each direction
first.

Bitboards would be efficient if i had a way to record a move (i.e. perform it on
the board) using a limited number of XORs and shifts. I havent investigated it
seriously. I should look into chess programming for move recording when using
bitboards ...

But it's true that i havent pushed it to the limit of using only one binary
number for both move generation and move recording and evaluation function. This
is the probably the path i need to follow to enhance "nodes per sec"
drastically.

For each "move number" MLA also knows how many marbles are ejected, pushed,
moved.

But i'm also searching for a faster move generation and a faster center of mass
computation (updating the center of mass of each side after is move is already
performad, but the evaluation function calculates a reference point from the two
centers of mass and then re-calculates the distance of each stone to this
reference point, and it's time consuming lol).

I think i need to look into pattern matching research related to the the "game
of go", I'm sure someone found fast algorithms for pattern matching lol.

I'll also go on working on the amended engine to understand why MLA 3.0 beats
2.5 lol.

plenty of ideas though ;)

David.

Selon Peer Sommerlund <peer.sommerlund@...>:

> With respect to patterns, I have no better idea than a sliding window:
>
> Think of an ordinary 2D grid (easy to translate to hexagonal board)
>
> . . . a
> . . . a
> . . . a
>
> This pattern is a 3x3 pattern. When you slide to the right, you must
> match most of the positions again, only shifted. The only new fields are
> the "a" column.
> If you compute the examined pieces to an integer, you can shift the
> integer and recycle the old fields. For example:
> value = 0;
> for (int i=0; i<9; i++) {
> value <<= 2; // or *3 if you want to save a few bits
> value += field[i];
> }
>
> incremental:
> value = old_value << 6;
> for (int i=6; i<9; i++) {
> value <<= 2; // or *3 if you want to save a few bits
> value += field[i];
> }
>
> Do a table lookup to find out if the pattern is interesting or not. (or
> simply what value you have assigned to it)
>
> A 7-field circle (radius 1) can hold 3**7 = 2187 < 2**12 values, with 2
> bits pr field: 4**7 = 2**14
> A radius 2 circle can hold 3**19 = 1G162 < 2**31 values. 2 bits: 4**19 =
> 2**48
>
> Radius 1 you can do a direct lookup to see if it was a match, and even
> lookup the shifted value.
> Radius 2 you have to work the other way, using partial matches - or
> split the pattern into 2 or 3 parts where you can perform lookup on each
> of them. If the number of patterns you want to look for is small, this
> can work.
>
> Another way (that also makes it easier to build large patterns) is to
> first do a horizontal translation, then a vertical. You translate every
> series of x fields into a single number representing the pattern of size x
>
> Lets consider the first row (it has 5 fields)
> ABCDE
>
> If you are looking for patterns of size 3, you would compute 3 values:
> ABC, BCD, CDE
> You can easily compute patterns of size 2 at the same time. Do this
> again on rows
> ABC BCD
> ABCD BCDE etc
> BCD CDE
>
> If you want to use bitboars you can work the other way: For each
> pattern, test it against all possible locations on the board: A complete
> board takes less than 128 bits (2*61 = 122 bits).
>
> The test is simple
> if ((board & shifted_mask) ^ shifted_pattern == 0)
> // we have a match
>
> .. fast, but the time is O(n) with number of patterns