Iterative deepening question

[Luis Babboni]

First the easier answer: yes, "Babboni" is italian, il mio nono came to Argentina from Pietrasanta, Lucca.... in 1922!!
Dove abita lei in Italia?

As you could see, my italian is even worst than my english

Now need me some time to think about your explanation.

[stegemma]

First the easier answer: yes, "Babboni" is italian, il mio nono came to Argentina from Pietrasanta, Lucca.... in 1922!!
Dove abita lei in Italia?

As you could see, my italian is even worst than my english

Now need me some time to think about your explanation.

My english is not better than your but you can also look at our italian chess programming group: www.g-sei.org If you speak spanish, you should understand italian too... as I understand a little of spanish.

[Luis Babboni]

Thnaks for the invitation, I´ll go there jsut after post it!

Here my new attempt to try to ask if I understood correctly or not:

But the bigger problem for option 1 will appear to go to Ply 3 cause I´ll do not have all nodes at PLy2 (as the dotted node for example)

[Luis Babboni]

Mmmmm....

With target deep N and n<N, the action of select the best node of ply n-1 to start searching at ply n for every n in the tree is called Internal Iterative Deepening ?

The named simply Iterative deepening is the action of use simply DFS till ply N-1 and just there select best node at deep N-1 to start search at Ply N?

In the DFS, the order to visit nodes are dictated by try promotions first, following by captures; etc?

[stegemma]

Thnaks for the invitation, I´ll go there jsut after post it!

Here my new attempt to try to ask if I understood correctly or not:

But the bigger problem for option 1 will appear to go to Ply 3 cause I´ll do not have all nodes at PLy2 (as the dotted node for example)

You don't have to go back to ply 1 and down to ply N. What you should do is:

- root node: play any move and for each one call alphabeta
- alphabeta: make moves, play moves, call alphabeta

The value returned by alphabeta is compared with alfa (the greater becomes the best move) and beta (if greater then you "cut the node").

so, in any alphabeta call:

- you go down a node calling alphabeta itself, for any move
- you exit if:
--- value returned by alphabeta is >= beta
--- or all moves has been played
--- or time has expired (don't mind of this, for now)

In any alphabeta node you go down one ply if it is not the last ply, of course. If it is the last ply, you evaluate position and return the value (or call quiescence).

That's all... or maybe not

PS: normally in any node you evaluate ALL the moves, you don't choose what move to evaluate and what not but leave alphabeta cut the node when needed; you can sort moves but not avoid evaluating some of them (this could be done but in a later stage, if you use some kind of aggressive pruning)

[Luis Babboni]

Thanks for your time Stefano!
Give me some time to rethink about it and I´ll come back with new questions.... I promise you

[Joerg Oster]

Maybe this helps a bit, too ...

• Iterative Deepening
  
  
  A idea that is even better than it sounds
  
  If you are about to start searching a chess position, how deep should you search it? It is difficult to predict in advance how long a search will take, since the time it takes to complete a search of depth D is dependent upon factors that might not be obvious. In a complex middlegame position, you might search not very deeply at all, while in an ending you might search significantly deeper, and in some king+pawn endings you might be able to search a hundred plies.
  
  An idea is to search to depth one. If this search completes in less than the amount of time allocated, search again to depth two. And then to depth three. And so on, until you run out of time.
  
  This all but guarantees pretty good time usage. If you are able to perform a deep search quickly, you'll continue along and search even deeper the next time, and perhaps you'll finish that. If the position is more complicated than you expected, you won't finish many plies of search, but you will have at least some legal move to play, since it's almost impossible to not finish a 1-ply search.
  
  This idea is called iterative deepening, because what happens is you iterate the search, going one ply deeper each time (there is nothing magic about going one ply deeper, for instance you could try two, but one works very well).
  
  Here is the code:
  
  for (depth = 1;; depth++) {
  
  val = AlphaBeta(depth, -INFINITY, INFINITY);
  
  if (TimedOut())
  
  break;
  
  }
  
  It might surprise you that this is actually an extremely efficient way to search. If you enhance alpha-beta so that it returns a principal variation, you can feed this principle variation back into the next iteration of search.
  
  For instance, if a one-ply search indicates that 1. e4 is the best move, you will search 1. e4 first when you perform a two-ply search. If that returns the line 1. e4 e5, you will search that line first when you perform a three-ply search.
  
  The effect of this is that the first line you search tends to be good. Alpha-beta is extremely sensitive to move ordering. If your move ordering is bad, in chess your branching factor will be about 35. If your move ordering is good, the branching factor will be closer to 6. The principal variation from the previous iteration of the search function tends to be very good.
  
  Iterative deepening provides you with a simple means of interrupting the search when you run out of time, and it makes your search more efficient.

[elcabesa]

Hi Luis,

here you can try a very good tutorial on how to write a simple chess engine:
http://aghaznawi.comuf.com/computer%20c ... arch01.htm

that said I can try to help you a little.
1) the basic algorithm used to search the game tree is MINMAX, it could be implemented as NEGAMAX and it travel all the node of a tree.

2) a simple and good enhancement to NEGAMAX is ALPHA-BETA!!
it will search fewer nodes than NEGAMAX, in the worst cases it will search the same number of nodes of NEGAMAX.

3) the number of nodes searched to achieve the result with ALPHA-BETA depend on move ordering, if you'll be able to test for each node always the best move, you'll get the smallest tree.

4) all the move ordering algorithm ( PV move, Capture before quiet move,killer moves, history heuristic ....) help you in ther task of testing good moves before bad ones.

5) it happens that move ordering informations collected at depth N-1 are very useful for a search at depth N.

to search the best move at depth 9 it's faster (due to better move ordering)

Code: Select all

for&#40;int i=1; i<10;i++)
&#123;
  val = alphabeta&#40;i,alpha,beta&#41;;
&#125;

than:

Code: Select all

val = alphabeta(9,alpha,beta);

[bob]

Thanks bob!

Good news!

But still some doubts.

1st:
You said "...the best move at ply=1, best move at ply=2, ..., best move at ply=N-1..."
For ply N what I need is not just the best move at ply N-1?
Cause the best move for ply k<N fall not necesarily into the same line that the best for ply N. I agree that you need best move for ply 2 to start search ply 3, but later you will do not need best move for ply 2 anymore..... or I´m wrong?

2nd:
I understood that the second best move could be useful cause I read a lot of times that is better to search some kind of moves first like promotions, captures etc.... and I understood the ID allow you to, instead of look first for that´s kind of moves, use the second best move for ply N-1; following by the 3rd best move for ply N-1; etc.
You suggest to look first for best move of ply N-1 following by promotions; captures; etc?
Or what I´m understanding wrongly?

I probably worded that poorly.

When you complete iteration N, you have a PV of moves m1 ... mN. Now you start iteration N+1. at each ply of iteration N+1 you want to search the best move from the previous depth N search when you start this search. So you search the previous m1, m2, ..., mN. But at the last ply (since you are going one ply deeper) you might not have a best move to search. Here you have to "wing it" with the usual ordering stuff....

Easiest way is after you finish iteration N, before you start N+1, take the PV from iteration N and make sure EVERY position is installed in the hash table correctly. Then, since you try hash moves first, you will be searching exactly what you want first at each ply...

[Luis Babboni]

Thanks Joerg; Marco and Robert!

May be I´m still below the level of understanding you guess, but your comments are usefull for me to show me that what I understand till now was correctly understood.

To give you an idea where I´m standing at the moment..... I still do not know nothing about hash tables; Capture before quiet move,killer moves and history heuristic
I read a little about that´s, but still do not working with them.