7
$\begingroup$

I'm making a Connect Four game where my engine uses Minimax with Alpha-Beta pruning to search. Since Alpha-Beta pruning is much more effective when it looks at the best moves first (since then it can prune branches of poor moves), I'm trying to come up with a set of heuristics that can rank moves from best to worst. These heuristics obviously aren't guaranteed to always work, but my goal is that they'll often allow my engine to look at the best moves first. An example of such heuristics would be as follows:

  • Closeness of a move to the centre column of the board - weight 3.
  • How many pieces surround a move - weight 2.
  • How low, horizontally, a move is to the bottom of the board - weight 1.
  • etc

However, I have no idea what the best set of weight values are for each attribute of a move. The weights I listed above are just my estimates, and can obviously be improved. I can think of two ways of improving them:

1) Evolution. I can let my engine think while my heuristics try to guess which move will be chosen as best by the engine, and I'll see the success score of my heuristics (something like x% guessed correctly). Then, I'll make a pseudo-random change/mutation to the heuristics (by randomly adjusting one of the weight values by a certain amount), and see how the heuristics do then. If it guesses better, then that will be my new set of heuristics. Note that when my engine thinks, it considers thousands of different positions in its calculations, so there will be enough data to average out how good my heuristics are at prediction.

2) Generate thousands of different heuristics with different weight values from the start. Then, let them all try to guess which move my engine will favor when it thinks. The set of heuristics that scores best should be kept.

I'm not sure which strategy is better here. Strategy #1 (evolution) seems like it could take a long time to run, since every time I let my engine think it takes about 1 second. This means testing each new pseudo-random mutation will take a second. Meanwhile, Strategy #2 seems faster, but I could be missing out on a great set of heuristics if I myself didn't include them.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
3
$\begingroup$

Hmmm, I see some issues that are actually present in both of the approaches you propose.

It is important to note that the depth level that your Minimax search process manages to reach, and therefore also the speed with which it can traverse the tree, is extremely important for the algorithm's performance. Therefore, when evaluating how good or bad a particular heuristic function for move ordering is, it is not only important to look at how well it ordered moves; it is also important to take into account the runtime overhead of the heuristic function call. If your heuristic functions manages to sort well, but is so computationally expensive that you can't search as deep in the tree, it's often not really worth it. Neither of the solutions you propose are able to take this into account.

Another issue is that it's not trivial to measure what ordering is the "best". A heuristic that has the highest accuracy for the position of the best move only is not necessarily the best heuristic. For example, a heuristic that always places the best move in the second position ($0\%$ accuracy because it's in the wrong position, should be first position) might be better than a heuristic that places the best move in the first position $50\%$ of the time ($50\%$ accuracy), and places the best move last in the other $50\%$ of cases.

I would be more inclined to evaluate the performance of different heuristic functions by setting up tournaments where different versions of your AI (same search algorithm, same processing time constraints per turn, different heuristic function) play against each other, and measuring the win percentage.

This set up can also be done with two variants analogous to what you proposed; you can exhaustively put all the heuristic functions you can come up with against each other in tournaments, or you can let let an evolutionary algorithm sequentially generate populations of hypothesis-heuristic-functions, and run a tournament with each population. Generally, I would lean towards the evolutionary approach, since we expect it to search the same search space of hypotheses (heuristic functions), but we expect it to do so in a more clever / efficient manner than an exhaustive search. Of course, if you happen to have a ridiculous amount of hardware available (e.g., if you're Google), you might be able to perform the complete exhaustive search at once in parallel.

Note that there are also ways to do fairly decent move ordering without heuristic functions like the ones you suggested.

For example, you likely should be using iterative deepening; this is a variant of your search algorithm where you first only perform a search with a depth limit $d = 1$, then repeat the complete search process with a depth limit $d = 2$, then again with a limit $d = 3$, etc., until processing time runs out.

Once you have completed such a search process for a depth limit $d$, and move on to the subsequent search process with a limit of $d + 1$, you can order order the moves in the root node according to your evaluations from the previous search process (with depth limit $d$). Yes, here you would only have move ordering in the root node, and nowhere else, but this is by far the most influential / important place in the tree to do move ordering. Move ordering becomes less and less important as you move further away from the root.

If you're using a transposition table (TT), it is also common to store the "best move" found for every state in your TT. If, later on, you run into a state that already exists in your TT (which will be very often if you're using iterative deepening), and if you cannot directly take the stored value but have to actually do a search (for instance, because your depth limit increased due to iterative deepening), you can search the "best move" stored in the TT first. This is very light move ordering in that you only put one move at the front and don't order the rest, but it can still be effective.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Very interesting, you've given me plenty of useful advice to think about. Iterative deepening sounds like a much better approach since it actually involves calculation, rather than general heuristics about a position itself (without any calculation further). However, couldn't it also allow move ordering in not just the root node? Say d = 2, so you're searching two levels down the tree. Since you'd have rough evaluations at depth 2, it seems like the possible moves at depth 1 nodes could be ordered. $\endgroup$
    – Inertial Ignorance
    Aug 17, 2018 at 11:39
  • 1
    $\begingroup$ @InertialIgnorance That would be difficult because it requires memory for every node; for every node in the tree, you'll have to memorize the previous evaluations / ordering. Generally, efficient Minimax implementations don't have any memory for nodes at all, we do not explicitly create a search tree; we only implicitly traverse one through recursive function calls, but normally don't have any Node objects in memory or anything like that for the complete tree. It's much easier to just only "break this rule" for the root, have some memory for the root node, and no memory elsewhere. $\endgroup$
    – Dennis Soemers ♦
    Aug 17, 2018 at 11:47
  • 1
    $\begingroup$ Ah, ok. For my program I've built a linked list where each parent node points to its child nodes, so I'm already explicitly storing each node/position in memory. For what I already have, is there any downside to updating the order of possible moves at each depth level? Also, one other separate thing. With TT, is there a reason for only using it to know the (probable) best move that should be searched first? Why not use it to have an order or all the moves from probably best to worst? $\endgroup$
    – Inertial Ignorance
    Aug 17, 2018 at 11:53
  • 1
    $\begingroup$ @InertialIgnorance On ordering at every level; can't come up with any downsides in that case, though I can't tell with full certainty since I never really thought about / experienced such a situation. Make sure to use a stable sorting algorithm (one that breaks ties by preserving original order), because sometimes you'll have sorted nodes well based on evaluations at $d - 1$, but no longer get any evaluations for many nodes at depth $d$ (due to alpha-beta pruning); then you'll want to make sure to re-use the previous ordering for all those nodes without new evaluations. $\endgroup$
    – Dennis Soemers ♦
    Aug 17, 2018 at 11:57
  • 1
    $\begingroup$ @InertialIgnorance As for TTs, that's usually to save memory. If you only remember the best move for every entry, that's e.g. $32$ bits per entry in the table (if you use a $32$ bit integer). Storing more moves requires much more memory per entry as well, and generally that memory is better used by just creating space for more entries (more states), rather than fewer entries with more "information" per entry. $\endgroup$
    – Dennis Soemers ♦
    Aug 17, 2018 at 12:00
0
$\begingroup$

With regards to random vs evolutionary algorithm, an evolutionary algorithm will almost always be superior. Imagine the space of all possible heuristics. An evolutionary algorithm moves through it 'intelligently' i.e. it somewhat follows the gradient of the space and should converge to a local optimum. A random algorithm will not be able to achieve this.

With regards to the time taken, surely it would be the same for each one to evaluate X heuristics?

Improve this answer
$\endgroup$
0
$\begingroup$

There is a third strategy and that is to study what heuristics a human player uses.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .