search

panchishin / alphabeta

Javascript implementation of minimax in Node using asynchronous calls to customizable game logic, scoring, and move generation.
The Unlicense
19 stars 5 forks source link

Generating next possible states is doing to much work #2

Closed ericvrp closed 7 years ago

ericvrp commented 8 years ago

As a rule of thumb alphabeta roughly has a branching factor of the sqrt(number of possible moves). So because this implementation generates all possible states it does a lot of unneccessary work. It would be better to generate moves and then when needed perform/play the move and generate the new state.

It can them be decided if undoing/takingback the move on a single state is faster/slower then generating new states.

Introducing moves has the other great advantage that it is easier to sort them in an order that speeds of the alphabeta algorithm. Keeping a best move per depth (killer move heuristic) and trying that move first for instance can greatly reduce the searchtime.

panchishin commented 8 years ago

If you have a pull request I'd review the code for sure!

panchishin commented 7 years ago

closing this enhancement.