Thread: Minimax tree help

  1. #1
    The One And Only
    Join Date
    Aug 2005
    Posts
    3

    Minimax tree help

    I am interested in making a tic-tac-toe game only I want to possible make it using a 4x4 or larger board. I want to try and make it 1 player. I understand the concept of minimax trees but I was wondering how you go about making a tree that large because in a tree for a 4x4 board there's over 2.0x10^13 possible outcomes.

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    A few things to consider..

    I don't really know what you mean by 1 player tic tac toe. I assume you just mean that is the style of the input, and that it's actually X and O playing against each other.

    If you just want to do the 4x4 case, you can "psuedo bruteforce" it with memoization, there are only really 3^16 states before even reducing for symettry. It's a lot like this problem http://www.algorithmist.com/index.php/UVa_10838

    On the other hand, not that I really understand mini-max trees, but the idea is that

    A) you explore the tree, not store it.
    B) you prune off parts of the search tree by estimating that certain parts of the search space are not good places to look, as they won't lead to a good solution.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Tree, couple questions
    By scoobasean in forum C Programming
    Replies: 3
    Last Post: 03-12-2005, 09:09 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM