On Oct 15, 10:09 pm, adak <[EMAIL PROTECTED]> wrote:
> In this algorithm, you need to search through a large tree or space,
> consisting of all the possible combinations of piece orientations in
> each box. That space can be searched beautifully using DFS, and alpha-
> beta (NOT mini-max). Your "scoring" function, will just be scoring the
> amount of free space that is wasted, with any configuration that has
> to be checked.
>
> The best thing about it, is that many configurations will NOT even
> have to be looked at, because they will be "cut - off" by the Alpha-
> Beta search, saving a great deal of time.
>
> DFS and alpha beta are not just for 2 player games. Used together,
> they are a very powerful search tool. Not that you would want to go
> this far, but consider also every possible perfectly packed box, being
> made into tables (like the End Game Table Bases that Chess programs
> access on the fly, (made via retrograde analysis)). That would make a
> VERY powerful tool to add to the DFS with A/B.
>
> A search through a large space, where you don't know what logic may
> ultimately find the best answer, thus demanding LOTS of search and
> evaluation of proposed (moves/positions, whatever), is a good
> candidate to consider DFS with A/B and a scoring function (of course).
>
> That's why we use it in chess programs. Not because "it's for 2 player
> games", because it kicks ass!
I'm still confused by what you say. Maybe you mean something different
by "alpha-beta" than I. The alpha-beta I'm talking about is a pruning
method that relies on a maximizing and a minimizing player: e.g. at
each owned ply, you can ignore nodes that are better than worst you've
already seen because you know your opponent will pick the worst for
you.
Maybe you are talking about branch-and-bound search, which is DFS that
prunes when it reaches a branch that can't possibly do better than the
current best solution.
The A-star algorithm is roughly like an optimal branch-and-bound
search.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
