Solved

How do I complete this code to work effectively?

Posted on 2008-10-07
4
313 Views
Last Modified: 2012-06-27
                       All in C# language
I seeking help in extending the  implementation of the mimimax algorithm  in  this program so that
(1).  in addition to the variable that holds the minimax value of the node, the node has a

         variable that holds the board position. The value of this variable can simply be an array of

         length nine which takes the values x and o (or 1 and -1, if you prefer integers).

(2).    the tree is generated automatically by computing the successor states for the board

       position represented by a particular node. Start with the empty board for the root node

       and recursively compute the successors until you reach terminal nodes.

(3). the data value of a terminal node is determined by the board position that it represents:

         1, if Max wins

        0, if it is a draw

       -1, if Min wins

(4). after running the program, all nodes should have the appropriate minimax values.
using System;

using System.Collections.Generic;
 

using System.Text;
 

public class Minimax
 

{
 

static void Main(string[] args)
 

{
 

// generate a simple game tree, starting with the root
 

Tree tree = new Tree(0);
 

 
 

// children of the root
 

tree.children = new Forest(new int[] { 0, 0 });
 

// children of the left child of the root
 

tree.children.first.children = new Forest(new int[] { 0, 7, 9 });
 

// children of the right child of the root
 

tree.children.rest.first.children = new Forest(new int[] { 4, 8, 6 });
 

// children of the leftmost child of the left child of the root
 

tree.children.first.children.first.children = new Forest(new int[] { 5, 3, 1 });
 

// write the expected and calculated minimax values to the console
 

Console.WriteLine("Expected minimax value is 5");
 

Console.WriteLine("Calculated minimax value of the tree " + tree.Minimax(true));
 

Console.WriteLine("Press any key to exit ...");
 

Console.ReadKey();
 

} // end method Main
 

private class Tree
 

{
 

public int data; // data stored in node
 

public Forest children; // link to the children of the node
 

// create a tree without children and initialize data
 

public Tree(int nodeData)
 

{
 

data = nodeData;
 

children = null; // node has no children
 

} // end constructor
 

// determine the minimax value of the node
 

public int Minimax(Boolean maximise)
 

{
 

// this method calculates the minimax value for the tree, which is:
 

// - the value in data, if the tree is a leaf
 

if (children == null) return data;
 

// - the maximum of the minimax values of the subtrees, if maximise is true
 

if (maximise) return children.Max();
 

// - the minimum of the minimax values of the subtrees, if maximise is false
 

else return children.Min();
 

} // end method Minimax
 

} // end class Tree
 

private class Forest
 

{
 

public Tree first; // first tree
 

public Forest rest; // remaining trees
 

// create a single-node tree for each piece of data and link them together
 

public Forest(int[] nodeData)
 

{
 

first = new Tree(nodeData[0]);
 

if (nodeData.Length > 1)
 

{
 

rest = new Forest(nodeData, 1);
 

}
 

else rest = null;
 

} // end constructor
 

public Forest(int[] nodeData, int start)
 

{
 

first = new Tree(nodeData[start]);
 

if (nodeData.Length - start > 1)
 

{
 

rest = new Forest(nodeData, start + 1);
 

}
 

else rest = null;
 

} // end constructor
 

// determine the maximum of the minimax values of the trees in the forest
 

public int Max()
 

{
 

// this method returns the maximum of the minimax values of the trees in the forest
 

int max = first.Minimax(false);
 

if (rest != null) max = Math.Max(first.Minimax(false), rest.Max());
 

return max;
 

} // end method Max
 

// determine the minimum of the minimax values of the trees in the forest
 

public int Min()
 

{
 

// this method returns the minimum of the minimax values of the trees in the forest
 

int min = first.Minimax(true);
 

if (rest != null) min = Math.Min(first.Minimax(true), rest.Min());
 

return min;
 

} // end method Min
 

} // end class Forest
 

} // end class Minimax

Open in new window

0
Comment
Question by:Mpencili
  • 2
  • 2
4 Comments
 
LVL 4

Accepted Solution

by:
Busac earned 500 total points
Comment Utility
So which part you don't know how to do? (And what game are we talking about anyway? :-))
0
 

Author Comment

by:Mpencili
Comment Utility
This is a tic-tac-toe game.
The required outcome is fully explained in text form accompanying the code.
Cheers.
0
 

Author Closing Comment

by:Mpencili
Comment Utility
Fake website
0
 
LVL 4

Expert Comment

by:Busac
Comment Utility
Umm, my previous comment wasn't intended to be a solution to this problem.
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now