Eval functions

Current approach

I'm continuing to tackle the eval function. Here's my proposal for the remaining parts.

Section 2:

• Check if the king has a path to the edge in any direction.
• If he does, check whether he can move to the corner from that location.
• If he can, check if there are any pieces that can block him.
• Check if the blocking piece will end up next to the corner. (bad because that's an easy capture for the king)

Section 3: King is at an edge.

• Not a huge fan of this one, because it restricts mobility, unless there's a path to the corner, but section 2 takes care of that.

Section 4: Surroundings of the king.

• Check for pieces right around the king.
• Check for escape paths, if there are 2 or more pieces.

Section 7: Repeating moves

• Definitely needs to be done. Can be very annoying.

Additional evaluation for the king (not in JS)

• Count the number of moves for the king. (assign a value to that)
• See if a king can get to a corner in 3 moves. I think this will be faster than path searching. (plus with depth of the search tree, this is a good look ahead)
  • The approach here is look at the squares right next to each corner.
  • See if the king can get to the appropriate rank or file to hit one of those squares.
  • See if there is anything in the way in that rank/file and the square.

Additional evaluation for black.

Corner protection:

• Use position weights to assign higher value to squares that will create barricades around the corners.
  • only value 3 or 4 piece type barricades.
  • we should also vary the weights of the corners depending on the current pieces around the corners so that black does not rush to one side only to leave the others exposed. Perhaps this will happen naturally.
  • a full barricade should give black major points.
• Value positions right next to the corners lower. (perhaps even negative)
• If all corners are blocked off
  • increase the squares directly outside of the barricade, such that barricades begin advancing and creating cordons.
• Avoid pieces right next to the center, unless the king is at center, or another piece blocking capture.

Additional evaluation for white:

• Attempt to prevent full barricades from forming.
• Avoid pieces right next to the center, unless the king is at center, or another piece blocking capture.

Other thoughts:

• We can adjust depth based on the initial count of legal moves for both sides.
• As the number of legal moves drops, with the number of pieces on the board, we can potentially increase the depth of search.
• However, this might not be practical as the tree grows exponentially and if the game is played correctly by black, it's not going to worry too much about capturing but more about protecting escape routes. Similar for white. I think they're goal is more mobility and corner access.
• I'll also play around with increasing the size of transposition table.

The more I think about it, the more it seems like for white, the advantage is to try to win the game as quickly as possible before black can setup the barricades. For black it's more of a long drawn out process of preventing escape and only then slowly collapsing on the king.

So perhaps there should be two separate strategies / eval functions. Pre barricade and post barricade.

Our approach

1. Let's start with the following Eval function:

2. First, Material Balance (MB) working. All warriors are worth 100.

3. Second, incorporate a very simple BC (Board Control) calculation. See attached image simple-BC. NOTE: Getting the King piece in each square type is worth triple. This is an over-simplification of board control, but it's a start.

4. Third, incorporate Mobility. I'm not sure what is the most efficient way of doing this, but it's a really big part of the game. At first, Mobility can just be the total number of legal moves each side has. A King's legal moves are worth 2x or 3x that of a Warrior. If possible, Mobility should be total number of legal moves without being captured. Even better is to give different weighting factor to legal moves according to the simple-BC multipliers.

5. I have no idea what the weighting (coefficient) for each of the three factors above should be. It is crucial and we will have to experiment to figure this out.

6. Because Minimax grows with O(B^n), moving to a 9x9 board might make the burgeoning AI just fast enough to play until we optimize it. Reducing the size of the board will significantly reduce B (# of legal moves), which will exponentially reduce work of each ply.

7. Add Opening moves.

8. Add the "Perimeter" concept to Eval function somehow. I think this is key strategy to Tafl. The Attacker wants to trap the white pieces within a loop (with the help of edges of the board), while the Defender's job is to prevent this by constantly punching a hole through it.

9. Mobility is not a bad approximation at the beginning since the whole point of the Attacker's perimeter is to reduce the total Mobility of the At

10. Later on, we can add formations.

11. The corners directly adjacent to the corners and the center are really bad positions. Because it takes only one piece to capture. So they should probably have negative value because they are dangerous.

12. As for mobility, yeah we can count the number of legal moves, it's pretty easy. We should also look for moves that leave a piece vulnerable to capture, but that's a little expensive.

13. King material value is 1200 initially.

14. I'm also thinking that certain squares may have different values for different teams.

15. Also, I think board control may be more important for black, but mobility is more important for white. Especially King's mobility.

16. So perhaps we can assign different weights depending on the team we are evaluating.

17. Also, a distance to escape sounds like a useful metric. This might need a pathing algorithm though. It should take into account obstacles. Something like Dijstras's would do the trick here. I have a java implementation of it already in zaria library, but I haven't had a chance to play around with it yet. It might be an expensive calculation. So perhaps we can first start with it for just the king.

Other notes

Eval function as linear transformation. In other words it's a sum of factors and coefficients:

a * f1( ) + b * f2( ) + ... + z * f3( )

Per http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-vi-evaluation-functions-r1208, the four factors are:

f1( ) is Material Balance, i.e. number of pieces of each type. For Tafl, all the pieces are "rooks" and worth the same. While Material Balance for chess can be the Eval function for a decent AI, in Tafl this is not the case. Keeping pieces is important, but it's much more about board control and limiting the mobility of the King.

f2( ) is Board Control, i.e. moving the pieces into the most advantageous parts of the board. It is extremely important in Tafl. While Material Balance is most important in Chess, Board Control is likely the most important in Tafl. In Tafl, the best way to think about is to divide the board into quandrants by the "3rd ranks" (for a 11 x 11 board). In other words, there are four "corner quandrants", four "edge quandrants", and the "center quadrant". So, there are 9 quandrants in total. The game is all about moving the Defender pieces from "center quadrant" to the edge or corner. Once the King gets to the edge or corner quadrant, the game gets close to being over.

f3( ) is Mobility, i.e. how many good legal moves all the pieces can make at any given time. When I think about it, Mobility is much more important in Tafl than in Chess. Limiting the mobility of the Defender pieces is the key to Tafl. The entire point of the Attacker is to form a perimeter around all the Defender pieces and "squeeze" them, which is limiting mobility. Once this is done, Defender can either draw or lose, which also boils down to mobility. Mobility of the King is worth much more than that of Rooks.

f4( ) is Development, i.e. how much closer a player is inching towards favorable formations or board control. For the Defender, getting the King unblocked by its own pieces is an example. For the Attacker, it is how much closer the player is forming a perimeter around all the white pieces.

f5( ) is Formations, i.e. getting pieces into known good formations. In Chess, it's mainly about Pawn Formation. In Tafl, since all pieces are the same, formation is quite useful. For example, the "Tower formation" (four pieces forming a square) is a known protective formation where the opponent cannot take any of the pieces. For the Attacker, there are numerous "Cordon" formations, which are essentially lines of pieces side-by-side that sweep across the board. Also, there are the obvious "Barricade" formations, especially for fully protecting the corner squares.

f6( ) is King Safety and Tropism, i.e. how safe the King is from being captured and how much pressure there is on the King. In Chess, this is important, but in Tafl, overly focusing on King Safety is actually harmful. The Defender actually wants the King out as fast as possible and leading the charge. The King is by far the most powerful piece and is very hard to capture, especially if the Defender plays good formations. We should think about King Safety like the Endgame in Chess, where the King becomes a powerful piece.

Q: Where do we detect things like Pins and Forces? In other words, if there is a great move for forcing an opponent to lose MB (Material Balance) or lose a formation, shouldn't that be favored over the mere possibility of a good outcome? Is this detected by Eval function, or are these just part of the Minimax search? In other words, does the search function already favor Pins and Forces?

Q: As in Chess, opening (the first ~8 moves) is really important for Tafl, especially the Attacker. Should we implement it? It's outside the scope of the Eval function, but getting the right opening will make the Eval function much more effective and keep the AI from being stuck in some devastating local maximum early on.

For Tafl, if I sorted the six factors with highest weight to lowest weight, I think the linear combination would look like this:

a * (Board Control) + b * (Mobility) + c * (Material Balance) + d * (Formation) + e * (King Safety/Tropism) + f * (Development)

Note: I put Development last partially because I don't understand Tafl enough to know what is good development and strategically how good and important it is.

Other implementations

C implementation:

• https://github.com/soderlund/hnefatafl/blob/master/src/aim/aimalgo.c

• line 119: aiminimax_evaluate()

• Value = [Material Value] + [Tactical Value]

• Material Value: Sum of all the pieces. Each piece (e.g. value = 1) is multiplied by their [Proximity to an Escape Square]. Then, it's multiplied again to either a [King Multiplier] or a [Normal Multiplier]. This is similar to our idea of Board Control and Material Value combined into one.

• Tactical Value: This is quite confusing, but I think it's checking if any piece "can escape". Only do this for the Defender pieces. If no piece can escape, then it just count all legal moves, which is just Mobility, and tack on that value instead. If a piece can escape, I assume it's worth a lot more. What I don't understand is what does he mean by a non-King piece escaping? And why is he "looking ahead" in his Eval function when it should be what the Minimax Search Algorithm does in the next ply.

• On second thought, in the Tactical Value, even if he is just checking if the King can escape (reach a Keep), it works well if the Minimax algorithm searches through enough levels. If the algorithm searches through enough levels, it will know how to avoid being trapped in a perimeter because it's being rewarded highly for being in a situation where the King could escape if only we skipped the opponent's turn (it's like the Null Move as discussed in the article).

• The problem here is that we can't look deep into the levels to make Tactical Value meaningful until we get close to an endgame when the King has fewer pieces in its way. Until then, Tactical Value is really just Mobility (total # of legal moves--we can add weighting).

• ...and his algorithm only checks Mobility of the Defender team, which kinda makes sense. I think his "Tactical Value" is really just Mobility with a strong bonus if King has the mobility of escaping.

• See Lutanho.net Implementation

Discussion

i think after this guy's stuff we add stuff for mobility and then board control within board control, we can do third rank and proximity to corners 2nd rank and bee-line can lead to imminent win

versus third rank can is flexible BUT more likely king can be blocked pretty much in 4-piece capture getting to (1,0) (0,1) and the other six symmetrical equivalents is necessarily a win so being on 2nd rank and one move away from (1,0) is very threatening (we might be able to delete the 2nd rank scenario altogether later with depth >= 4) because depth 4+ may just search it out

The third rank is threatening because of the one piece captures So 1,0 0,1 are actually bad squares for black to be on, unless theres another black piece next to them

if someone is on 3rd rank

I think if I only implement rank 2 logic And the move history, which I'm already collecting to check for draw scenarios I should be done with the js implementation I guess next would be position weights, move counts and number of paths to the corner for the king. It should probably be, fewest moves to the corner. Kay, I'll take a look at all that tomorrow.

oh also the stuff about king capture you're not doing that, right? Part 4 that stuff should be able to be searched out and his logic is for 2-piece capture it's pretty much nearing endgame for Black to capture the King since JS implementation does no searching, he had to do all that bullshit

another thing i thought about in the shower just now... don't we want to stop search based on time not depth?

coz later on when the # of pieces get smaller or total mobility get consistently small since search is O(B^n), B gets significantly smaller and there's a lot more pruning since early moves may lead to win so we can search a lot more depth within the same time right? ...i need to go to bed soon... As for implementing simple mobility and proximity to corner or something more complicated with pathfinding etc. it's up to you well... i do know the simple cases of each is a log easier

1. proximity to corners is just the Manhattan distance to each square which can be easily pre-calculated using the coordinates isn't it just d1 = x + y
2. d2 = (11-x-1) + y
3. d3 = x + (11-y-1)
4. d4 = (11-x-1) + (11-y-1)
5. d = Min (d1,d2,d3,d4)
6. d: min distance to a keep
7. mobility has just total number of legal moves hmmm, this one is trickier. but let's say you know the mobility of the opening board then, moving a piece just means you have to recalculate the mobility of the pieces which are influenced by the moved piece.

at most, for each turn, that's 8 pieces whose mobility are potentially influenced anyway...you're smarter than i am so i'm sure you get this already i don't know how you're gonna do path finding efficiently

i think mobility for white as in number of moves is easy, i already calculate that after every turn if we only do pathfinding for king, it might not be too bad just count the number of paths to the corners maybe we should just split it up and think of it completely independently white strategy and black strategy they will get combined in a single evaluation gonna jump in the shower it's a travel day for me so i'm not sure how much i can get done today

i think we will finish alpha in a week get a playable AI and then get it on android phone and we can show it to some people for feedback then, decide if it's "practice" to wrap it all up soon (some final polish) OR try to make money from it