Optimizing the AI Tree

[ETang444]

Ah. So I messed up. There are a couple major ways to optimize the tree that I should have thought about . . .

1. We don't need to build the entire tree then find values; we can build the tree as we're finding values. Using alpha-beta pruning, this means that there a lot of branches we don't have to even build at all. When we call value(), each node will have an order of searching (loosely from best to worst moves), and we run through those. When we find a legal move, we start building, and then we update the alpha and beta values. a. So within each if check for a legal move, we'll need to make a move, create that board, then run value() on that node. Not so bad.
2. We can optimize the order in which we search for legal moves. If we search for best moves first, that's optimal. I say we go through the board once looking for jumps, then go through the board again looking for normal moves.

[ETang444]

Alternatively, we could have two projects working in tandem: the naive MiniMax AI, and then another that implements a nice form of Alpha-beta pruning. I'll continue working on the naive minimax, and later see if I can combine it into a nice AI.

[ETang444]

Other AI needs (to finish construction):

1. We need to implement jumping chains every time we check for a possible move. Each chain of jumps should count as one move. We may need a tree structure to add all the possible jumps -- Eric
2. CORRECTION: Each node will store a String, which is the sequence of moves that got it to that place. -- Jack
3. Finally, we need to complete the AITree class's function of findBestMove(): ask the RootNode for its best move.
4. Add the heuristic calculator of any given board's position (factoring in kings, pieces, edge pieces, etc.) -- Aivant

[aivantg]

Aivant: Heuristic Board Calculator Eric: Jumping Chains Jack: Storing Moves leading to Children and Find Best Move