tree data structure in c#

Question

1.00/5 (1 vote)

See more:

Hello everyone,
I want to make the AI of a chess game and for that i need to generate a decision tree of all the possible moves.
Now the question is that i have 2 ways to do it, and i need to know which one will be faster, using Msaccess database or using classes.

Thanks in advance

Posted 30-Jan-13 4:36am

z3ngew

Add a Solution

Comments

PIEBALDconsult 30-Jan-13 10:58am

Unsure what you are describing. Do you mean to generate it once and store it for future use? Or generate it on the fly for one-time use?

If the former, then a database might be what you want (hopefully a better one than Access). But even then, your solution may involve classes, so I don't understand why you seem to think of them as mutually exclusive.

If the latter, then I wouldn't use a database, I'd use an in-memory structure (and perform breadth-first searches), this would likely require some custom classes.

z3ngew 30-Jan-13 11:00am

I want to generate tree during runtime and evaluate results and then select best answer and then dismiss tree

PIEBALDconsult 30-Jan-13 11:16am

If you do, don't dismiss the parts of the tree that still matter.

Sergey Alexandrovich Kryukov 30-Jan-13 20:47pm

Did you think of the tree size, just for a second? It makes further discussion meaningless... :-)
—SA

PIEBALDconsult 30-Jan-13 21:13pm

I find your lack of faith disturbing.

Sergey Alexandrovich Kryukov 30-Jan-13 22:20pm

:-)

z3ngew 31-Jan-13 16:13pm

i think i will control the tree size by selecting the depth of the search

Sergey Alexandrovich Kryukov 31-Jan-13 16:21pm

Then your program will loose to any more or less good player... Chess machine algorithms are not that simple; and this is not how they work. Perhaps you need to read about them. This is, by far, not AI, but the algorithms are pretty cunning; don't think that you can get a good result by one little project...
—SA

z3ngew 31-Jan-13 16:49pm

You are correct, thanks for the advice :D

Sergey Alexandrovich Kryukov 31-Jan-13 17:15pm

You are welcome...
—SA

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Dave Kreskowiak · Accepted Answer · 2013-01-30T04:53:00

Solution 1

Well, first, all possible moves would take a eons to generate. Second, using Access to store these moves is going to be VERY slow compared to storing everything in memory in a tree structure.

Do NOT keep reposting the same question over and over again. The answers won't change.

Posted 30-Jan-13 4:53am

Dave Kreskowiak

Comments

Sergey Alexandrovich Kryukov 30-Jan-13 17:21pm

Not exactly. Forget about processing time: no modern computer RAM or even disk can store the full tree.
I used to be a favorite historical anecdote about a number of pieces of grains to be payed to the inventor of the historical version of the game and similar mathematical entertainment... :-)
—SA

Dave Kreskowiak 30-Jan-13 20:41pm

I was just comparing the speed of storing a tree node in memory as compared to doing it in an Access database. No contest! :)

Sergey Alexandrovich Kryukov 30-Jan-13 20:46pm

OK, whatever, but the problem of the whole decision tree for the chess game comes first. OP's "a decision tree of all the possible moves" makes further discussion meaningless. :-)
—SA

PIEBALDconsult 30-Jan-13 21:52pm

But he needn't form the full tree. He could look only a few moves ahead. Not that I would.

My own thoughts on the subject is to think of each of the pieces as a base-13 digit and the board as a 64-digit number (not all values in the range are valid).
Base thirteen:
0 -- Empty
1 -- White King
2 -- White Queen
...
12 -- Black pawn
Or whatever order you want. Then it's a simple matter of 13⁶⁴ possible board positions, you assign each one a "best move", done.

Sergey Alexandrovich Kryukov 30-Jan-13 22:21pm

Absolutely. OP is welcome to go for it! :-)
Thank you.
—SA