About notation, eob goha and i had worked on a 3-axis representation (goha giving the three axis and eob the formula to determine if two positions are conex). The three axis start symetrically from the center, which is {0, 0, 0}.

If it may seem too unfamiliar for humans, i think it can be interresting for representing the board in an internal layer (an interface layer translating them in a more familiar, if not standard, coordinate system for being understandable).

This 3-axis system had the advantage of carrying intrinsiquely the distance of each position from the center, allowing to test with a very easy computation (i cannot recall how right now and should have to think a little bit to figure it out) if two positions are conex, and avoiding many bounderies testing in regard memory representation of the board (i guess testing which coordinate is valid and which one is not can be a big time consumer in a 2d representation).

Here are some translation from your coordinate system into this 3-axis :

A5 -> 4, 0, 0
I9 -> 0, 4, 0
E1 -> 0, 0, 4

Those three coordinates gives you the three axis.

Now a few others, and it becomes real food for brain :

A1 -> 4, 0, 4
A2 -> 4, 0, 3
D6 -> 2, 1, 0

You have probably noticed that you always have at least one 0 in those coordinates.

This coordinate system was designed in order to allow some specific computations (mainly concerning distance from the middle and which positions are conex) to run faster. However, as you should know, i am lazy and play other games now so it hasn't be proved to be actually faster in real operationnal systems.  

--Last edited by chriscool on 2005-10-26 04:59:03 --

Quote :

SilverSurfer wrote : It is possbile to start with nacre with these starting-configuations ? 4 black marbles and one white marble on the 4th 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? -------------------------------------------------- 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?

1) The 4-1 endgame is very easy for me to do, but may take some time. I think the work may be able to support my current line of work, so it will get my top priority. To answer your question: The search will be of unlimited depth. Well, limited by time, so I guess something like 20-60 ply. Maybe.

The 4-1 problem is very interesting and we should discuss it further on the Endgame-Theory forum. You must allow for null-moves for the defender, if this should be usable in general.

2) The java applet is not that hard, but it requires much more work, as I have no java source. I do know Java, but doing this work would take time from Nacre (which is C++), so I'm probably not goint to do it.

However, this should be a simple task for somebody with Java experience. A good "getting-started" task. Probably the first step is to search the net for existing implementations.

Quote :

chriscool wrote : About notation, eob goha and i had worked on a 3-axis representation

Have you read http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon2.html ? Nacre uses this for fast Manhattan distance computation. It is faster than the one presented by Werner. I thought I had discovered something original, but I later discovered that my "original" thought was done by somebody else back in 1994.

Hello nacre,

first I have to say:  




I am happy for this forum




There are now 138 messages in exactly 7 days on this forum and I am glad to see you and other abalone-interested people here.
And I am very glad, that you want to support this endgame-theory-project. Thank you.

Silver  

--Last edited by SilverSurfer on 2005-10-26 15:43:31 --

Quote :

Have you read http://www-cs-students.stanford.edu/~amitp/Articles/Hexagon2.html ?

No, i hadn't. Thx for the link...

Quote :

I thought I had discovered something original

Yeah, it seems i just tried to re-invent the wheel too

just FYI:


a visual representation of the 3axis notation
(note the analogy with the 3D cube view)

         O
       O   O  
     O   O   O
   O   O   O   O
 X   O   O   O   Z
   X   O   O   Z
     X   O   Z
       X   Z
         C
X X X X C   C Z Z Z Z  
O O O O Y   Y O O O O
O O O O Y   Y O O O O
O O O O Y   Y O O O O
O O O O Y   Y O O O O



And just fyi here is another representation of this 3axis representation which should be considered as a 2 axis representation (x=z + y).
(note the arrow/bottleneck property using this view... maybe another starting point for a pattern based AI where the strategy would tend in considering the "north" area as the common "battlefield" and the "west" and "east" area as "base-camps"? The "y" axis would rotate on its 6 possible positions according to the current topology... i.e. for the starting position of a 2 player game, the y axis has 2 possible positions on the middle horizontal line, hence it may translate in 2 strategies either converging or diverging...)

       O
     O O O
   O O O O O
 O O O O O O O
x x x x c z z z z
O O O O y O O O O
O O O O y O O O O
O O O O y O O O O
O O O O y O O O O


PS: has anybody found yet a practical use of polar-coordinate system (except for drawing)?
center:   (0,0)
1st-ring: (1,0);(1,60);(1,120);(1,180);(1,240);(1,300)
2nd-ring: (2,0);(2,30);(2,60);....
3rd-ring: (3,0);(3,20);(3,40);(3,60);....
4th-ring: (4,0);(4,15);(4,30);(4,45);(4,60);.....  

or said differently

for (r=0; r<=4; r++)
 for (a=0; a<2pi; a+=(r?2pi/3r:2pi))
    pos=[r,a]
    x=r cos(a)
    y=r sin(a)

 

--Last edited by kopedito on 2005-10-27 23:47:14 --

Well, a problem with polar coordinates is that they cannot be directly mapped to memory, requiring one more indirection so that you can access the memory location of each position in the game (through an associative array).

Speed being vital in AIs, you need the fastest possible data access, and this is why this indirection is a serious drawback to whatever could be the advantages of polar coordinates, i think.

AI is a generic term englobing lots of different things including bactracking. Speed might thus be a concern in brute force 'AI' which I'm not interrested in. If I had to investigate for an AI, I wouldn't go for an algo which exceeds 4 to 5 ply as I'm not sure  it can be named 'AI'.

Anyway, I'm not concerned about AI for the moment and I propose to Silver my contribution in implementing the java applet needed for its abaschool. I just need to figure out a way to indicate to the user if his solution is right or not...

kr.  

--Last edited by kopedito on 2005-10-28 00:04:52 --

Well, polar or 3axis coordinates are not user friendly, so i wouldn't use them for interacting with the user...

-> 1.2. the evaluation-function

criticism on Aba-Pros' endgame-ability

I have analysed some winning-in-x-moves-tasks with Aba-Pro.
In  many tasks, even in winning-in-2-Moves-Tasks, Aba-Pro did not found the easy solution, even if I put it on Level 9 - I don’t use Level 10, because of time.

This is a usual example:



The first, left image is the task-problem: its an easy win in 3 moves:
1. d5c5 ! ... 2. d4c4   ... 3.winning

Winning-in-3-Moves-Task have a depth of 5 single-moves - 3 black-, two white-moves.

the second image is the position after 8 ! moves if Aba-Pro plays on Level7 against itself. The score is +1,8 (Black), which is a small-medium advantage.

The third image shows the position after 6 ! moves, if Aba-Pro plays on Level8 against itself. The score is + 4,7 (Black) medium-big advantage.

Aba-Pro is far away of moving the simple winning-in-3-moves.



And this is a ugly example, I think so:



This is a simple winning-in-two-moves-task: 1. b3b4
Aba-Pro plays on Level 9: 1.e2e3 and then: a4b5 ! the win is gone and the Score is: -0,7 Black - a little disadvantage for black, instead of an easy victory in two moves.

If my Ab-Pro-Version 4.8 is not out of order, than Aba-Pro plays the game, from the beginning to the end, with the identical strategical principles. And the move 1. e2e3 is "better" (Min-Max-> centre-board-values) than the ejection of the marble with 1.b3b4 (win). Thus it neglects completely the fact, that this is the sixth marble to eject.

This is not a single-case.

I think there is a lack of a endgame-function.  

--Last edited by SilverSurfer on 2005-10-29 21:22:14 --

The reason AbaPro is strong is that it uses forward pruning. This gives it search depth of 8-9 ply in tournaments. However, this is also the cause of AbaPro endgame weakness. It plays endgames like middlegame: Pruning moves that deviates too much from the "optimal" score with respect to compactness.

This has the effect that you see: Attacks toward the edge are ignored since they move marbles away from the center.

The overall bennefit from forward pruning is larger than the drawbacks. AbaPro without forward pruning may be able to play these mate-in-2 but it will certanly loose all games to AbaPro with forward pruning, because it could never survive the middlegame.

The trick is to determine when to disable forward pruning.

AbaPro has one feature that addresses this problem: When AbaPro is much ahead, it will ignore more and more marbles in the center, thus it becomes more willing to do edge-attacks. However, if the position is balanced with respect to center-control, this feature will not be enabled.

nacre also wrote:

Real endgame

One thing that tricks AbaPro and Nacre consequently is when marbles are trapped against the edge.

When enough marbles are trapped, the center no longer matters. Now the race for push-out begins. If only one player has trapped marbles, it is not really a race, but just a puzzle where the attacker must be carefull to get as many of the trapped marbles out.

One example from a game Nacre lost:

[Black "Eobllor"]
[White "Nacre"]
[Date "2005.06.18"]
[Result "1-0"]

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

1.5  refinements:

If I play Aba-Pro, than I miss a lot of features, particular when I want to analyse games. Aba-Pro indicates me the move-number, the thinking-time for the moving-colour, the score - for each move of the point of view of the moving-colour - and the fixed depth.
This is enough for playing, but few for analyses.

This is the image of a usual, current chess-program:



To the left (0.75) there is the score. Right beside (Tiefe) there is the move-depth(8) and the number of the variations  (27).

First move:
“1.  (0,75) 31. Kg1 b4 32. e6….”

The first (1.) move in the move-thinking-list  is the best move for the moving-colour. Its possible to regard all 27 move-paths and the according score, but I think maybe 10 moves would be sufficient. Every move indicates the score of the point of view of White, this avoids the changing of "+" and "-" for every move. You can recognize the move-paths from move 31. to move 35.

This are very helpful features for analyses - I think so.  

There will be I time, I hope so, that the program is not only the game-opponent, rather a nice support for analyses, too.  

--Last edited by SilverSurfer on 2005-11-07 00:23:45 --

I just implemented minimax and TD-learning Abalone agents.  The coordinate system really isn't a large issue.  There are only 61 coordinates on the board, so a hashtable that contains the distances between any two points on the board would only contain 61 choose 2 pairs of coordinates, under any representation.  I suppose switching to a 3-coordinate system might give you some speed-up in checking move logic, but that doesn't suck up *that* much time.  I think pattern-matching might be faster by hashing as well - but I'm not an Abalone expert so I don't know exactly what patterns are 'good' and what patterns are 'bad'.  I imagine some image filtering algorithms might actually be useful here...

The more difficult aspect is speeding up minimax with heuristics beyond alpha-beta pruning and tuning parameters of each model.  Aba-Pro solved this problem by picking a relatively simple heuristic to optimize on and searching the game tree to a great depth heuristically.  What would be interesting (and more challenging) would be to achieve the same result without searching to such a great depth.

Can the strength of the TD+minimax agent you are talking about any good at playing abalone?

I see a big difference between Backgammon and Abalone. There are combinations to calculate ... like in chess. This is exactly the problem abapro encounters against MLA (my program), it stops analysis (ie doesnt develop a given tree node) when the position is considered stable enough (based on variance of evaluations after each considered move as compared to the evaluation of the current position it seems). But if most of the possible moves in a given position do no change much the position, one good move is enough. But the abapro heuristic is a very good idea. BTW Abapro isnt going "to great depth". abapro takes "a while" at depth=8 for example.

I have a good heuristic for you : why should the engine try broadside moves (for example) of three marbles out of its main group of marbles ? Considering some hill-climbing principles has lead to great enhancement in speed of my program (see http://mogwai.lunarpages.com/lovely).

I'd love to get a copy/more info about your TD agent !

Nacre uses Temporal Difference (TD) for tuning its feature weights. It works, but TD is not a silver bullit. For Backgammon it works, because it is fairly easy to come up with a representation that can be categorized by ANN-style functions, for Abalone you are left with the problem of finding this representation. I have not found a representation that does any better than a simple but fast evaluation function. The reason for this is the extra ply you get from the speed.

There is something we are missing in general, it's the lack of electronic knowledge like starting positions, games databases to tune all this. I'm wondering if netabalone could provide a download of the games saved in their databases.

david (currently working on selective extensions and reductions)

Programming and Theory

There are at least three entrances to the Abalone-game:
The starting with no knowledge and learning by doing, the Theory-entrance and the Programming-entrance. They are not mutually exclusive, but in the present days they are most of the time still different, I think so.


Theory:

The theory tries to describe, to understand and finally to explain the game. There are 3 analysis-levels: tactical, positional, strategical. And there are three periods with 2 two transitional phases.
Opening: There is an implicit Opening-Knowledge in the present days of the Abalone-Evolution (This forum follows the aim to present these moves and the theory for this Knowledge). In the Daisys, there are some ways to "open" a game. You can attack only with one Daisy or you can attack with both Daisys, but you reach not so fast the centre. You can attack from the side and ahead. This all leads to "pattern" in the centre and the ring around the centre after about 4-8 moves.
Middle-game: Then there is the question, how to transfer this emergent "interaction-sequence": the first transitional phase from the opening to the middle-game. It’s a question, how to transfer the opening in a particular manner into a middle-game-problem.  (This forum will also analyse the middle-game-problems with the aim to get a typology). There are many patterns and there are different plans - position-movements and strategies - for these positional middle-game-patterns.  If you are leading and your opponent played the opening not well, than the plan is easy: kill him. But if the two players played both a good opening, then there is a balance in the centre and you now have to find a way to lead the opening into a advantageous middle-game-structure. There are different types of middle-game-structures: for example simply the both standard-blocks, but also much more complex patterns. Its here the question how you can conquer the centre and/or how you can eject marbles without losing too much power in the centre. The centre is always very important for the middle-game.
Endgame: Finally there is the second transitional phase. I want to explain this period with an example: it is possible that you lose a key-point in the middle-game, your position in the centre is  collapsing, but maybe you can eject enough marbles on the edge for the win and maybe this was the strategy: to leave the middle-game, to give the important dominant key-point away, with the aim to win the better endgame. The transitional phase is the phase, where you have to find these moves from the middle-game into the end-game - very often the end-game is not easy to recognise.
Therefore: if there is a endgame-position, most of the time - if it is not only a continuation of the middle-game-dominance - then you can neglect the centre, for example with building a prison. But you have to "recognise" if there is the possibility for prisons and the way to lead to this structure. Maybe you have a worse position in the middle-game, but you can find a winning-endgame - this is possible sometimes. Thus: there is a necessity of a different strategy than in the middle-game to win this situation, because middle-game-strategies would lose those positions.

Programming:

I am only able to describe the Programming-entrance of the point of the view of the Theory.

Endgame-lack:
My impression is, that the most programs have a lack of the endgame. I think its necessary for the programmers to recognize this.
The minimum endgame feature – in my eyes - would be: “if you have ejected 5 marbles, then search the fastest ejection for the sixth marble, with victims if necessary.”  There are parameters for the middle-game and this minimum-endgame-feature is changing the playing-style in the end of the game obviously. This is an endgame-feature, but the most simple – I guess.

Middle-game-patterns vs. deep-pruning:
Most of the time the programs play from the beginning to the end with the identical parameters. And I think this is a big problem. Programs are compared with humans weak in the opening and weak in the endgame. They are also weak in standard-block-middle-games. (I don’t think so that these standard-block-games are “natural” a draw. Maybe if your opponent is leading 5-4 and you have the centre and he is playing only defensively, than probably. But most of the time the standard-situation is not "natural" draw, I think so. It "can be", but has not to be.)
But they are very strong in complex middle-games, which emerge for  example with Daisy-Starting-positions.
They lose sometimes, because the opening was from the beginning bad  or they don’t realize, that the opponent has created an endgame-prison on the edge. But they rarely lose the middle-game.
The programs are far away to recognise several middle-game-patterns. But they play them very well, because they have a deep tactical pruning.

Endgame-patterns and Middle-game-patterns - future-music:
There is also a lack of a typology of the endgame. I can imagine: if there would be a typology of middle-game-problems and a typology of endgame-problems, than you could program to transfer the middle-game-problem x into the endgame-type y.
The similar way for the opening and the middle-game transitional phase.
But  this all is future-music - I think so.

( Compare the interesting messages of chriscool and nacre about this subject: http://148009.aceboard.net/148009-512-1213-0-neural-network-versus-evaluation-fonction.htm#vb )


“Realistic” proposals for programs:
My proposal for the programs of the present days is:
Opening: create a opening-book for the first 2-3 moves. There are most of the time 3-5 good moves, so this is a tree of about 4*4*4*4(*4*4) moves.
I think there are two components to find very strong moves: deep ply and human strategy. There is no objective truth, rather its like in chess or other game boards: it’s a matter of the point of view. But there are obviously better and worse moves. Thus its the question, which are the 3-5 best moves.
If a programmer could implement a feature that displays the 5-10 best moves with the according game-value and the paths (as I have suggested for “refinements”), than this would be very helpful to figure out and to fix the best moves. You could go to depth 10-12 and you could select the best moves. I think there will be always a chunk of 2-5 moves.
And find the best parameters for the opening-period – the period till the there are many marbles in the centre and the first ring.

Middle-Game: Change the parameters for the middle-game and the first transitional-phase together.

End-game: Draw a distinction between the most important and evident types (prison, witch-ring, standard, ...) of endgames and integrate a endgame-feature for the last marble.
The programmers are able to analyse groups:
- position analysis
   - marbles score
   - compactness
   - groups
       - efficiency
       - mobility
       - alive / dead
       - number of
   - push pressure / sumitos
   - mobility
   - threats
   - center
   - balance
   - tempo
   - stability

This should be sufficient to figure out the endgame-patterns.


I think: these propositions would support a realistic step in the evolution of the Abalone-programs. And we will see how the evolution of the Abalone-humans will react to this development.
If the analyses of the middlegame will develop, than the programmers will integrate it, too - I think so.

In the present days I can see at least one program, which is on this way: MLA.

------------------------------------------------------------
Endgame-lack:



This is a simple winning-in-two-moves-task: 1. b3b4
Aba-Pro plays on Level 9: 1.e2e3 and then: a4b5 ! the win is gone and the Score is: -0,7 Black - a little disadvantage for black, instead of an easy victory in two moves.
There is a lack of a endgame-function, I thnk so.



To attack sub-groups or main-groups:



Its obviously a endgame-prison. MLA ejects both marbles, Aba-Pro only one and one marble escapes.




There are 3 marbles to eject and there is a very important positional and strategical key-point. Aba-Pro conquers the Key-point on Level9, MLA on Level8.
A human player can recognise very fast: if you eject the marbles, then white will get a block and the game will lead into a standard-game. But if you conquer the key-point, then the game can be finished soon.


Best Regards,
SilverSurfer

(A lot of "Thank you" to Mogwai for discussing pretty all parts of this message)  

--Last edited by Silversurfer on 2005-12-19 01:45:47 --

According to the former message: the MLA-2.0-system now integrates different sets of parameters depending on the type of position encountered during the game:

- Opening
- Middle game
- Standard (looks like "standard" board set-up)
- Endgame
- Defense

The engine picks the parameters automatically, depending on the analysis of the position.

There is also a new layout of MLA's board.

http://mogwai.lunarpages.com/lovely/index.htm  

--Last edited by AbaloneTheory-Forum on 2006-01-07 05:24:17 --