[Plan] Some planning

Here is a list of what I will be doing next. In order.

1. Make an opening class of my own (right now I am using Yves' opening class just to avoid repeated games). This is a rather small project and there is not much to it. I will go through how to implement it and what you should keep in mind while writing it.


2. Iterative Deepening and time management.
   
   What iterative deepening does is start to search the position with 1 ply depth, return the best move and evaluation, then search it to 2 ply, and so on until the allocated time is up.
   
   This way we always have a searched move to return when we need to move. We will need to keep track of the times used and make some intelligent calculation on how to spend the time, perhaps use a little more in complex middle games for example.


3. Some improvement to move ordering.
   
   Iterative deepening might seem costly since we do a bunch of repeated searches. A 5-ply search will include all the moves searched in 4, 3, 2, and 1 ply searches as well.
   
   But as I will show later, it is not that much of an extra cost and since it will help improve our move ordering greatly we will actually gain speed by using it.
   
   As I have stated before the move ordering is very important in alpha-beta search. As it is now Mediocre can barely get to a 5 ply search without using too much time to make it annoying. This is mainly because I have no move ordering at all. In fact the move ordering is probably about as bad as it can be since the moves are now sorted starting in the corners where we rarely see the best move.
   
   With iterative deepening in place we can simply input the previous best line and search it first. Since this line will be the best in a majority of the positions, we should see a huge improvement in search speed once this is done.
   
   There are a number of more ways to improve move ordering. I will save that until later since I believe Mediocre will be fast 'enough' for now with this technique.


4. Start tweaking the evaluation so Mediocre plays more interesting (and better). I am planning to put a lot of effort into this before moving on.
   
   The evaluation portion is where we can do the most to shape our engine, and it is the part where every chess engine gets its personality. The search and any search optimization (transposition tables, null-moves etc.) you might have will be pretty much the same in most engines, but the evaluation is unique.
   
   Here are a few things I am planning to implement in the evaluation:
   
   
   • Piece placement evaluations. We want the engine to put his pieces on the best squares. This includes putting rooks on open/semi-open rows. Bishops on the long diagonals where they are not hindered too much by pawns. Knights on good central squares. And anything else I might come up with.
   
   
   • Development. We need the engine to understand what to do in the opening, our opening database only helps until the opponent deviates. This will be done by giving various bonuses; like awarding moving the central pawns, penalizing pieces left on the first rank, greatly awarding castling and so on.
   
   
   • Pawns. We want to make sure the engine understands doubled and trippled pawns are bad (but not always, so we should make a controlled open line more important than avoiding doubled pawns). Award passed pawns and penalize isolated pawns.
   
   
   • The kings. We want our engine to try attack the enemy's king if possible, so award pieces that are in the vicinity of the opponent's king. Also we need to keep our own king safe with a similar scheme.
     
     Here we should also try calculating what protection the king gets from own pawns. An intact wall of pawns in front of the king is a good thing for example.
   
   
   • Endings. We need the engine to realize when the game is turned into an ending. Since in the ending the kings should be brought out and pawns advanced.
   
   These are a few things. More will be implemented as we go along.


5. Transposition table. This is a hash table that keeps track of previous positions in the search, so when we reach a repeated position we already know how to score it. Especially useful in endings where positions are repeated all the time.


6. A full three-fold repetition detection. Once we have the transposition table in place, we will also have Zobrist keys which we can use to efficiently keep track of passed positions in the search tree.


7. Looking even further ahead; Killer moves, null-moves, search extensions, MTD(f) search, better move ordering and more.

There are a lot of things to implement, so lets get started. :)