Iterative Deepening & Principal Variation reordering
$30-120 USD
Cancelled
Posted over 17 years ago
$30-120 USD
Paid on delivery
**1) Generate a fixed-width fixed-depth game tree
**Aa tree of nodes, stored in memory, with branching factor at least 5 and depth at least 7. Each node has several fields to store a parent, a depth in the tree, a list or vector of child nodes (this is empty for leaf nodes), and an integer [login to view URL] also have a field to store a principal variation. The top node has null parent, and is at depth 0. Its child nodes are at depth 1. The tree is to be searched (in steps 2 & 3) by a negamax algorithm, estimated-score of a node should be a simulated static-evaluation result from the point of view of the player to move at that [login to view URL] estimated-score of an interior node should be close to the maximum of the negations of its children's estimated-scores. The children should not be [login to view URL] one parameter to dictate how much difference there may be between scores of siblings, another one to indicate how much absolute difference there may be between an interior node’s estimated score and the negamax of its children’s estimated-scores.
**2) Measure the number of node evaluations performed by alpha-beta
**Implement a simple negamax alpha-beta algorithm, without enhancements except for (1) code to count the leaf-node evaluations performed and (2) to record the principal variation in the subtree dominated by a node. Use this negamax alpha-beta algorithm to search the tree you have built. Evaluation of leaf nodes is trivial - retrieve the node's preassigned estimated-score. Determine how many evaluations are needed for the randomly ordered tree.
**3) Use iterative-deepening and principal variation reordering.
**Use the alpha-beta to search one ply, then two, then three and so on. (Use the somewhat erroneous scores of interior nodes as their evaluations). After a shallow search, re-order the tree in accordance with the overall principal variation. Determine how many evaluations are needed in total.
## Deliverables
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done****Comments Essential ****
2) Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):
a) For web sites or other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.
b) For all others including desktop software or software the buyer intends to distribute: A software installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.
3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).
## Platform
Needs to run on java j2se.