-> 1.4  other "problems" (dead-positions, etc.)

Number of valid moves

As you work with Abalone programming you often have to examine properties of the game, such as how many bits are needed to represent a move or what is the largest number of moves you have to choose between.

As for encoding of a move I use the following:
6 bits for position on board, 6 bits for direction+movetype:
There are 61 positions on the board, this fits in 6 bits.
There are 6 directions * 10 move types = 60, which also fits in 6 bits

move types:
move 1, 2, 3
push 2-1, 3-1, 3-2
broadside left 2, 3
broadside right 2, 3
Total: 10

12 bits is 4096. If you count moves you see that some 51% or so of this is used - it is sparse, but you cannot save another bit.

Now, I have a question: What is the largest number of moves you have to choose between when it is your turn? Of course it must be less than 2000, but how tight can you get?

A few elements from MLA :

The average branching factor is between 40 and 50 depending on the settings (ie MLA has to go deeper for about 40 and 50 moves in average during all its analysis). The best move is found (as an average) in the first 20%-25% of the possible moves.

If I follow you, I think that more than the number of possible moves in a given position, move ordering is clearly the issue.

MLA uses a lot more space than 12 bits for each move. If you call "movenr" the binary representation of a move, I'm using a scheme that can answer (for pushing moves) IsPossible[movenr] directly from a constant array, and PushesStones[movenr], and EjectsSomeStones[movenr] so basically my move number depends on the contents of the six board holes (five in fact) that might be changed by a pushing move.

To do and undo moves, the movenr gives, for each of the five board holes, the new value

It's like a constant array saying NewBoardHoleValue[movenr][1-5][colour].

(am I releasing some top secret info? lol)

Encoding 5 holes can be done with 3**5 = 243 states, which fits in a byte. Thus you read the board without branches (good for the CPU pipeline) and then use a few lookups in small tables (fits in CPU level 1 cache)

You only need 5 holes, because you start out with searching for holes with a friendly marble.

Broadside moves are a different but similar story. 2 holes in the direction, 3 holes on the side. This must be done 6x2 times pr friendly marble. The first two holes can be shared with the inline computation.

However, my question was not on the average branching factor, but on the maximum branching factor. I have seen more that 100 moves in some situations. How high can you go? Can you produce an example position with a lot of moves for black? This is not a programming question, although it is nice to know when you write a program.

I'm definitely not using 3 states but four (outside of the board is also a state). => 10 bits minimum.

I tried several representations of moves and move generation algorithms, including bitboards No way i could find faster so far, because when i change the movenr representation i have, consequences are high everytime i need more info about the move, particularly for move ordering at node level ...

This movenr representation is bound to many things in MLA.

For the time being i'm not really concerned by space five holes are built with :

movenr=0
for each hole
movenr=(movenr<<2)+hole content

then IsPossible[movenr] and other similar functions are often used in MLA. Ejects[movenr], NbPushed[movenr], length[movenr] and so on.

Basically, i'm not a system programmer, i'm not interested in getting into the CPU cache I think that reducing the branching factor before finding the best move, heuristics for elimination of moves, hashing schemes and search algorithm are more important, because they decrease so much the number of nodes explored by the engine or for example, decreasing the impact of horizon effect, collisions and so on. Very different point of view

All this is mostly conceptual, and the basis of my approach

Saving 25% of one bit millions of times doesnt really matter to me.

David.

about the max number of possible moves for a side in a given position

you have 14 stones max. 14 starting stones to move, 2 directions to test for broadside moves, 2 or three stones are moved (2 possibilities)

- 14x2x2 = 56

for push moves, 14 stones, 6 directions => 14x6 = 84

56+84 = 140 max with no position containing 140 possibilities i guess

David.

For a hypothetical situation (with only one player) the most I have been able to come up with is:


    . . . . .
   . . . . . .
  . 1 1 1 . . .
 . . . . . . . .
. 1 1 1 1 1 1 1 .
 . . . . . . . .
  . 1 1 1 1 . .
   . . . . . .
    . . . . .

which has 150 moves if I count correctly

For an equally theoretical two player situation with the same number of moves:

    2 2 2 2 2
   . . . . . 2
  . 1 1 1 . . 2
 . . . . . . . .
. 1 1 1 1 1 1 1 .
 . . . . . . . .
  . 1 1 1 1 . 2
   . . . . . 2
    2 2 2 2 2

how many do you count for the following?

  . . . .
 . 1 1 1 .
  . . . .

- left stone :

 - 6 moves for push or one stone move
 - broadside moves : with one neighbor : 4, with two neighbors : 4 directions

- middle stone :

- push or one stone move : 6
- broadside moves : with left neighbor : already counted, with two neighbors : already counted, with right eghbor only : 4 moves

- right stone :

  - push or one stone moves : 6
  - broadside moves : all have aleady been counted

=> 30 moves?

and my formula says 3x4 + 3 x 6 => 30!

Absolutely correct, but consider the larger formations
 
First a few terms:
 A = single move = inline moves with 1, 2, or 3 friendly marbles
 B = dual move = broadside with 2 marbles
 C = triple move = broadside with 3 marbles

Broadside moves are counted for the leftmost marble (as you do).

 . . . . . . . .
. 1 1 1 1 1 1 1 .
 . . . . . . . .

Marble 1 has 5A + 4B + 4C = 13 moves
Marble 2 has 5A + 4B + 4C = 13 moves
Marble 3 has 5A + 4B + 4C = 13 moves
Marble 4 has 4A + 4B + 4C = 12 moves
Marble 5 has 5A + 4B + 4C = 13 moves
Marble 6 has 5A + 4B + 0C =  9 moves
Marble 7 has 5A + 0B + 0C =  5 moves

Total for 7 marbles = 78 moves

Your formula: 7 x 4 + 7 x 6 = 70 moves


 . . . . .
. 1 1 1 1 .
 . . . . .

Marble 1 has 5A + 4B + 4C = 13 moves
Marble 2 has 6A + 4B + 4C = 14 moves
Marble 3 has 6A + 4B + 0C = 10 moves
Marble 4 has 5A + 0B + 0C =  5 moves

Total for 4 marbles = 42 moves

Your formula: 4 x 4 + 4 x 6 = 40 moves


For all 3 formations: 30 + 78 + 40 = 148

Your formula: 14 x 4 + 14 x 6 = 140

:-) Ok, so 150 was too high. But 148 is still above 140. ;-)

nacre, i think you are definetly right, but let's think about a maximum

If my calculations are correct, the maximum is at least 148 - but I have not been able to construct a position with more moves.

A single string of 14 marbles would have more moves, but it does not fit in a board that is only 9 marbles in diameter.

Marbles in two rows, like this

  . . . .
 . 1 1 1 .
. 1 1 1 .
 . . . .

has less moves because there are fewer broadside moves pr marble and the number of inline moves pr marble are the same.

Thus I think we have reached the maximum: 148 moves.  ;)

in fact MLA makes the following computation

inline move : 14 marbles x 6 directions for push (of course)

broadside : considering a row of n marbles, two ways i can go through it (to the right or to the left) two directions for the move, possibility to use two or three marbles (two choices) i.e. 4x2 eight choices for each marble

the amazing thing is that the implementation in MLA is correct since the beginning, but my formula was wrong if "forgot" a "x2" factor lol

i.e. 6x14+8x14 = 196 is a maximum

now which position reaches the highest number of moves? no idea