Theoretical elements of Programming

This sujet has to collect different elements of theoretical Abalone-Programming.

According to the "General Introduction" of this Programming-Forum we differentiate several points:

1.1. the rules and a notation-system
1.2. the evaluation-function (board-score, ball-score and maybe pattern-socre)
1.3. the move-searching (optimum-problem: deepth and/or tricky)
1.4  other "problems" (dead-positions, etc.)
1.5  refinements (opening-book, endgame-patterns, etc.)  

--Last edited by Funky-AbaloneTheory-JazzClub on 2005-10-22 00:48:11 --

-> 1.1 notation


A board-coordinate-system-map, which figures the hexagonal board onto a rectangular x-y plane:

10 - - - - - - - - - - -          Where
9 - - - - - @ @ @ @ @ -         '@' is a white marble
8 - - - - @ @ @ @ @ @ -         'O' is a black marble,
7 - - -  .  .  @ @ @ . . -        '.' is an empty location, and
6 - -  .  .  .  .  .  .  .  .  -        '-' is off the board.
5 -  .  .  .  .  .  .  .  .  .  -
4 -  .  .  .  .  .  .  .  .  - -     NW  NE    The movement directions
3 -  .  .  O O O  .  .  - - -       + +      are named after compass
2 - O O O O O O - - - -      W+ O +E     directions like this.
1 - O O O O O - - - - -          + +
0 - - - - - - - - - - -          SW  SE
  0 1 2 3 4 5 6 7 8 9 10

So, for instance, we might communicate a move by saying, "3 marbles northeast from (1,1)" to indicate the marbles at (1,1), (2,2), and (3,3) all moving up and to the right.  Or, "3 marbles east from (3,3) moving northeast" to indicate a broadside move, and so on.  

A different system:

 

--Last edited by SilverSurfer on 2005-10-21 22:02:08 --

-> 1.4 other problems

The problem of dead-end positions:

for example:
 

--Last edited by SilverSurfer on 2005-10-21 22:02:42 --

-> 1.2. the evaluation-function


One suggestion for an evaluation function:


             10     12     15    12     10

         12     40      45    45     40     12  

      15    45      60      65    60     45     15  

   12    45     65      80     80     65     45     12

10     40     60     80     100     80     60     40     10  

--Last edited by SilverSurfer on 2005-10-21 22:03:39 --

-> 1.2. the evaluation-function

My present idea for the "Evaluation Function" is:

The centre-score has to decrease and the ball-score has to increase, the more balls were ejected.


This "temporal-dynamic-endgame-function" should antoganize two programming-problems:

1. a statement, if the programme has  conquered  the centre and the function-optimum is to stay in the centre and not to push balls on the edge for a easy win.

2. if a player has ejected 5 balls and he wants to give the programme a one-ball-victim for an easy win.  



For example:

To start with this function:

Evaluation Function:


             10     12     15    12     10

         12     40      45    45     40     12  

      15    45      60      65    60     45     15  

   12    45     65      80     80     65     45     12

10     40     60     80     100     80     60     40     10


and "350" for a ball-ejection.

And then to increase the ball-value and to decrease the board values after a ejected ball for "each"  party seperately.
The consequence is that 1. both players have different board and ball-scores, if they have not a identical number of ejected balls and 2. the scores of the balls and board can change in a path-tree if one path-tree eject for example a ball after the second move and the deepth of the tree is 4 moves.  


For example the function for Black-White: 4 - 4



         12     40      43    43     40     12  

      15    43      50      52    50     43     15  

   12    43     52      68      68     52     43     12

10     40     50     68     80      68     50     40     10


And the ball-ejection-score is now 390

And the ball-ejection-score for the 5th-ball will be 430 and for the 6th ball 500 (or much more !?!).  

In the case of Black -White: 4 - 0 there are now two different functions: for black the later and for White the former function.
Black will now try to eject the last two balls and will not attack or defend the centre too much.  

--Last edited by SilverSurfer on 2005-10-21 22:04:01 --

-> 1.3. the move-searching

Several functions:




Complexity:

 

(remark: the branching-factor in backgammon is questionable, since it is due to the stochastic element of the game)  

--Last edited by SilverSurfer on 2005-10-21 22:04:41 --

Quote :

SilverSurfer wrote : -> 1.1 notation

I have written some on this topic in
http://90214.aceboard.net/90214-2318-15375-0-Move-notation.htm

Quote :

SilverSurfer wrote : -> 1.2. the evaluation-function My present idea for the "Evaluation Function" is: The centre-score has to decrease and the ball-score has to increase, the more balls were ejected. This "temporal-dynamic-endgame-function" should antoganize two programming-problems: 1. a statement, if the programme has  conquered  the centre and the function-optimum is to stay in the centre and not to push balls on the edge for a easy win. 2. if a player has ejected 5 balls and he wants to give the programme a one-ball-victim for an easy win.

If you want a simple function that works, use the compactness function defined by Tino Werner. It is much better than assigning values to fields on the board. You don't need to increase the push-out value as the game progresses -- the effect is not that large -- but you do need to transfer focus from center towards the edge. Read Werner's work. It has a nice solution to that as well.

As search depth is very important in Abalone, you should try to maximise your search speed. I have written a small text on how to compute the compactness function incrementally. This should save you about 60% of the time used on evaluation.

Quote :

SilverSurfer wrote : -> 1.3. the move-searching

After you have implemented the compactness evaluation function, search depth should be your next priority.

Forward pruning is essential, and easy to do as Werner described. More work can be done in this area though -- you should spend some time searching the litterature, then try to come up with a better way to do it. Nacre uses an improved forward pruning.

Hello nacre,

nice, that you write here !  

I have played many games with Aba-Pro and I am disappointed of the end-game-playing of Aba-Pro. Sometimes it does not find eays wins.

There is not only this "problem-reason", why I want to change the push-out values and the board-values. Well, I have not written a programme until now, but I would like to experience this way.
A second reason for this function are my theoretical thoughts, that the centre is not important in the end-game.
The problem is than rather to recognize the beginning of the endgame.
But I will study Werners function. Thank you.

Silver  

--Last edited by SilverSurfer on 2005-10-22 23:32:34 --

I will post some endgame-examples with an easy win here.
The "score" and the "playing" of Abalone neglect those situations.

Quote :

SilverSurfer wrote : I have played many games with Aba-Pro and I am disappointed of the end-game-playing of Aba-Pro. Sometimes it does not find eays wins. There is not only this "problem-reason", why I want to change the push-out values and the board-values. Well, I have not written a programme until now, but I would like to experience this way. A second reason for this function are my theoretical thoughts, that the centre is not important in the end-game. The problem is than rather to recognize the beginning of the endgame. But I will study Werners function. Thank you. Silver

You must be able to handle the opening & middle game before your work on the end-game. The reason AbaPro is strong, is 1) that it has a large searchdepth (8-9 ply) with tournament time limits, and 2) that it has an evaluation function that measures compactness. Often, AbaPro never has to play endgame :-)

Werner added a small tweak that allowed the program to play on the edge when it was clearly ahead. The exact configuration of this tweak could be debated (to attack earlier, for example).

Nacre uses a non-linear parameterised function to combine features of the board. One of the features that Nacre compute is "number of marbles pushed out". Every marble has its unique value. By selfplay and temporal difference learning these parameters have been tuned, and the result is that Nacre believes that the first marble pushed out is less important than the last marble.

In other ways, Nacre agrees with you ;-)

I think its possible to study the basic patterns in the endgame without the middle-game and the opening, like in chess.
I dont see any problem to do this. There are simple basic patterns, with 3 balls and with 4 balls, with prisoners, and so on. Its not necessary to know anything of the middle-game here, I  think so.

And its possible to study the middle-game without the opening, too. There can emerge the identical structures in pretty all openings - included standard and standard-related-opening -, if they player play well.  

Against eob, gohatto, me and other players, Aba-Pro has to play endgame in many games, even on level 10.  

--Last edited by SilverSurfer on 2005-10-24 13:32:54 --

Quote :

SilverSurfer wrote : I will post some endgame-examples with an easy win here. The "score" and the "playing" of Abalone neglect those situations.

Take a look at some of the newest games played by nacre on NetAbalone. One of them played against Sax (I forgot which nick he used), clearly shows an anti-computer strategy, where he plays around the center. Nacre happily forgets the edge and looses the game pretty early. This example demonstrates a situation where the edge is a central part of the game

My current work on the search engine adresses this problem. I'm trying to come up with a quiecense search definition that lets the program do edge-searches when some of its marbles are in danger.

yes, this - edge-search - sounds to me very reasonable.  

--Last edited by SilverSurfer on 2005-10-24 13:36:17 --

Quote :

SilverSurfer wrote : I think its possible to study the basic patterns in the endgame without the middle-game and the opening, like in chess. I dont see any problem to do this. There are simple basic patterns, with 3 balls and with 4 balls, with prisoners, and so on. Against eob, gohatto, me and other players, Aba-Pro has to play endgame in many games, even on level 10.

No doubt that players are learning (or have learned) how to beat AbaPro, thus computer players have to gain knowledge of how to play all phases of the game instead of relying on search.

I have done some thinking about the end game. Not much is yet in Nacre. With respect to end games I would like to ask you how many marbles is necessary to push a single opponent out? I think you can do it with 5 but not 4.

This can be implemented as a simple algorithm, which is exactly what I am doing to get the quiecense search. However, I have not taken the influence of the remaining marbles on the board into account. Another question is: How do you determine if a 5-against-1 subset of the board is independent / influenced by the remaining marbles.

If you study some end-game-tasks, you will quickly realize that 4 balls are enough to catch a adversarial "isolated" ball on the "forth ring" and to eject it (watch my second example in this message). 3 balls are necessary to capture an isolated adversarial ball, without ejecting.

If there is not one isolated adversarial ball on the edge, but two, then very often 3 balls (!) are enough to eject one of them with a double-attack.  


----------------------------------------------------

I distinguish between two types of endgames:

1. middle-game-extension-endgames
You have to play these endgames with the "positional patterns" and "strategical-positional movements" of the middle-game. The "strategy-principles" are understated and the tactical-requirements are  raised - but both not too much.

(for these terms compare my Elements-Catalogue/GeneralTheory)

A very simple example:


Black to move and win in two moves

2. real-endgames
The  "strategical-positional-movements" and the "strategy-principles" are now pretty invalid. There are particular "positional-endgame"-patterns and the tactical-requirements are raised very much onto this particular positional-endgame-patterns.

For example:

Black to move and win in 5 moves (5 black, 4 white-moves)

----------------------------------------------------------------

The middle-game-extension-endgames occur predominantly in "standard-related" (compare my Introduction in Opening-theory ) starting-positions, if both players are not "stage 3 players" (compare my Introduction in the Standard-Opening). If both are "stage 3" players than it is unusually, but possible.

The real-endgames occur predominantly in non-standard-related-openings, as more probable as the players play progressed, offensive and equivalent (level3).  

--Last edited by SilverSurfer on 2005-10-24 22:13:23 --

Quote :

SilverSurfer wrote : If you study some end-game-tasks, you will quickly realize that 4 balls are enough to catch a adversarial "isolated" ball on the "forth ring" and to eject it

In your example, if the white marble was at f8 instead of g8, then the 4 black marbles cannot force the white away from ring 4 -- thus 4 marbles it not always enough.

Hi nacre,

thanks for your answer.

In my example the four black marbles catch and eject the white marble on g8.
If you neglect the White three-row on c3d4e5 (for h8) or the other marbles (for f8) and study only "theorectically the endgame-pattern on the board", then the four black marbles are able to catch and to eject the white marble even on h8 and f8.

h8:


You can recognize the three-marbles-prison if white plays "i9i8" (3.2)

f8:



I think "1.e6e7" is the winning-move, this is a prison, too.

1. ... f8g8 I.
2. f6f7  g8h8 II.
3. e7f7  h8g8
4. f7g6  g8h8
5. f7g7  h8g8
6. g6g7  and winning-move very soon.

I. 1. ...      f8e8
  2. g7f7    anything
  3. f6f7 ...  and winning very soon

II. 2. ... move with other white marble
   3. e7e8 g8h8
   4. f7g7 and winning-move very soon
-> this is the possible prison for move 2-6

And I think black can win, even with the white marble e7 on the 3rd ring.

First move "1. f6e6"


for example: 1. ...  e7d7
            2. e6d6
           
1.  ... e7f8 and e7e8 are not well, too.

Therefore as far as I can see f8,h8,g8,e7 can be catched and ejected by 4 marbles in a theoretical endgame on the board.

-----

But you are right, my sentence was "over-generalized" and I mentioned this in the Elements-sujet yesterday after our talk.
I should say "in many practical tasks, you will realize that 4 balls are enough ... ... on the forth ring."

In future we will study on this Theory-Forum the endgame-patterns to formulate precisely the principles -
for example like the end-game-rules in chess with kings "opposition" and the "square-rule".

Thanks and see you,
Silver  

--Last edited by Funky-AbaloneTheory-JazzClub on 2005-10-25 19:35:16 --

Hi nacre,

I have some questions to you.

Is it possbile to start with nacre with these starting-configuations ?



4 black marbles and one white marble on the 2th and 3rd ring ?

And if "yes", how many moves nacre can calculate with only 5 marbles? It is possible to you to write a programme with brute-force-endgame-calculation for this theoretical problems with less marbles? Or is this too much work?

It would be a great thing, if a AI could do this calculation for us and to finde these basic, theoretical-endgame-laws - I think so.  

--------------------------------------------------

And I have a second question to you.
There are Chess- and Go-Sites like this:

http://playgo.to/interactive/german/

If you press on "49 Kyu Problems" then there will emerge a Java-task-modul. Can you imagine to write the basic-code of a similar site for Abalone? I think this would be a good thing for Abalone-Player.

Thank you and see you,
Silver  

--Last edited by SilverSurfer on 2005-11-07 00:26:05 --