Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.
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
If you are experiencing a similar issue, please ask a related question
Title | # Comments | Views | Activity |
---|---|---|---|
What are the meanings and differences of Binary and Unary operators (OR / ||, && / &, XOR) | 3 | 141 | |
Algorithm for Facial recognition system | 4 | 184 | |
Help with Javascript syntax | 4 | 108 | |
How do sunrise and sunset times change with altitude | 14 | 27 |
Join the community of 500,000 technology professionals and ask your questions.