Depth of Search

[Guest]

Archived from groups: comp.ai.games (More info?)

Hi,

I am using an alpha beta cutoff minimax search tree to play
Othello (Reversi).

I am trying to get my software to challange itself by having one
player
running the algorithm up to depth 5 and the other player up to depth
9-10
Suprisingly the 5 depth player wins big time (exactly same
implementation)

Is this normal behavior when working with search trees (after all the
other player is not optimal and cange change intended results) or do I
have a bug lurking out there?

Could it be that I will consider limiting the depth just to take
advantage?

Thanks.

 

[Guest]

Archived from groups: comp.ai.games (More info?)

Moti ezra a écrit :
> Hi,
>
> I am using an alpha beta cutoff minimax search tree to play
> Othello (Reversi).
>
> I am trying to get my software to challange itself by having one
> player
> running the algorithm up to depth 5 and the other player up to depth
> 9-10
> Suprisingly the 5 depth player wins big time (exactly same
> implementation)
>
> Is this normal behavior when working with search trees (after all the
> other player is not optimal and cange change intended results) or do I
> have a bug lurking out there?

On a single game everything is possible, but if you did your experiments
on several games (from various openings or starting positions), a deeper
search should give better results, particularly when playing Othello.
Your results may be caused by a bug or by a poor evaluation function.
Note that for a random evaluation function, deeper searches give better
results in several games including othello, so if the problem is in your
evaluation function, it means that it is worst than a random one.

> Could it be that I will consider limiting the depth just to take
> advantage?

No. Searching deeper is very important at Othello. Current strong
Othello programs use selective searches to favour deeper search. In
Othello this is particularly important because a deeper search means a
sooner endgame, where the score could be exactly evaluated. On modern
hardware (say a 3GHz CPU), in 10 minutes games, strong programs usually
play perfectly when 25-30 empty squares remain on the board. In midgame,
Othello may suffer from "diminishing returns", ie searching deeper is
not so useful. However I think the problem arise at depths around 20,
not 5 or 10.

--
Richard