| |
Main
Date: 30 Sep 2007 01:20:06
From: Summercool
Subject: Depth Fist Search and Breadth First Search and using array
|
I just wonder if for DFS (Depth Fist Search), we don't really need an
array to act as a Stack (LIFO), but we can just use recursion.
Is it true that the main concern is stack overflow? (if too deep
level). If we use the array as a stack, then the overflow problem is
gone. Now, however, if our program is to spider the web, or to go
down the game tree, and we set the levelMax to 10, then the stack
overflow problem is really not there, as the deepest call stack level
is 10.
Is it true that for BFS (Breadth First Search), we always have to use
an array as a Queue (FIFO)? Using an array seems a bit like a "global
variable". Is it possible at all to do BFS without using an array as
a queue and just use recursion?
|
|
| |
Date: 30 Sep 2007 09:40:44
From: Summercool
Subject: Re: Depth Fist Search and Breadth First Search and using array
|
On Sep 29, 8:16 pm, "Guest" <[email protected] > wrote:
> "Summercool" <[email protected]> wrote in message
>
> Figure a max depth of 100 plies....
>
> Assume 20 variables. Assume another 10 words of stack for the compiler
> stuff. So 30 words total. That'd be 120 bytes on a 32 bit system.
>
> 120 bytes * 100 plies = 12k. Insignificant on all but 8 bit micros. Even
> many 8 bit micros would have no problem, especially since they would be
> going 100 plies deep.
>
> If you have an array on the stack, then that's certainly going to increase
> the stack usage.
hm, the stack will be a global stack... and if using stack, then won't
use recursion, i think. just
while stack is not empty
pop element
process element
for i in children node
push into stack
that's it, i think.
BFS is like
while queue is not empty
shift element from front of queue
process element
for i in children node
push into end of queue
Yeah, the stack overflow issue is more like if the program is to
traverse a graph, say even with only 1000 elements. if just happen
the DFS hits a long chain, such as 500 elements, if the program's
default stack size is not big enough, then it can crash... so maybe
using a global stack is a way to guarantee no such crash.
|
| | |
Date: 30 Sep 2007 12:36:10
From: Guest
Subject: Re: Depth Fist Search and Breadth First Search and using array
|
"Summercool" <[email protected] > wrote in message
news:[email protected]...
>
> hm, the stack will be a global stack... and if using stack, then won't
> use recursion, i think. just
The language, whether C or Pascal or Java or C# will have a 'stack' for the
language itself to use. That's where it puts local variables, temporary
variables during computations, whatever it needs it for.
When you call a routine, such as the evaluator or a library function, that
stack is where the computer puts the return values.
So having a global stack is a given. It's going to happen and there is
nothing you can do to prevent it.
If you have multithreaded program, then each thread will have a stack.
But even though it's a "global" stack, at the same time it's not global.
You can't access arbitrary elements on it. You access the local variables
and that's all.
You haven't really said what you are wanting.
You just popped in here talking about stack sizes and stack overflow, etc.
So I don't know what you are wanting. Are you trying to keep the stack
small for a specific reason? Are you doing a multithreaded approach? Are
you trying to keep total memory small? What??
> while stack is not empty
> pop element
> process element
> for i in children node
> push into stack
>
> that's it, i think.
That's not really how depth first works. Although you can do it that way.
The compiler stack is NOT treated like an explicit programmer stack.
It's more like:
step 1: if depth too deep, then evaluate & return
step 2: while MoreMoves() do
step 3: recurse to step 1
step 4: return best score.
Depending on whether step 2 generates all the moves at once or just one at a
time, the memory usage can vary quite a bit. But as I pointed out in the
previous message, even allowing for 200 moves at each ply is no big deal.
The memory usage is too small to worry about in nearly all situations.
>
> BFS is like
>
> while queue is not empty
> shift element from front of queue
> process element
> for i in children node
> push into end of queue
>
> Yeah, the stack overflow issue is more like if the program is to
> traverse a graph, say even with only 1000 elements. if just happen
> the DFS hits a long chain, such as 500 elements, if the program's
> default stack size is not big enough, then it can crash... so maybe
> using a global stack is a way to guarantee no such crash.
There are always ways to crash a program. Few gracefully handle a memory
overflow situation.
Again, if you would say what you are wanting to do, and what special
conditions you have, etc. we can be in a better position to help you.
Judging from what you have said, it sounds like you have never done a chess
program before. Or checkers. Or any game.
And you are probably a beginning programmer. (Perhaps this is a class
assignment?)
In that case, unless you have some specific requirements (class assignment,
limited hardware, etc.) I would suggest you totally forget about all that
and just do a plain, simple chess program. Don't worry about running out of
memory or keeping memory usage down, or anything.
Just write a very basic program and see how things work and get familiar
with the basic techniques.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
| |
Date: 29 Sep 2007 22:16:58
From: Guest
Subject: Re: Depth Fist Search and Breadth First Search and using array
|
"Summercool" <[email protected] > wrote in message
news:[email protected]...
>
> I just wonder if for DFS (Depth Fist Search), we don't really need an
> array to act as a Stack (LIFO), but we can just use recursion.
>
> Is it true that the main concern is stack overflow? (if too deep
No. Just do the math.
Figure a max depth of 100 plies....
Assume 20 variables. Assume another 10 words of stack for the compiler
stuff. So 30 words total. That'd be 120 bytes on a 32 bit system.
120 bytes * 100 plies = 12k. Insignificant on all but 8 bit micros. Even
many 8 bit micros would have no problem, especially since they would be
going 100 plies deep.
If you have an array on the stack, then that's certainly going to increase
the stack usage.
For example, if you put your 'BestMove" line on the stack, then that would
be 100 words of 4 bytes. (Possibly even just 2 bytes, depending on your
move storage method.) So 400*100=40k.
Even allowing for additional stuff, that'd still be under 60k.
Really... You've got a 32 bit system with half a gig or more of memory.
What's 60k? Insignificant. And you can always specifiy to the compiler /
linker enough memory. (Assuming your OS doesn't grow the stack as needed.)
If you are really worried about stack usage, then simply use global storage
to set up a stack. Then you'd only be passing one variable in recursion...
the depth. But the code would be rather ugly and there's no real reason to
do it anyway.
(And for the record, yes some programs have been written that way.
Especially those written in Fortran, which didn't allow recursion in the old
days. Programs like CrayBlitz, for example.)
Now, if you do the move list on the stack, then that can certainly add more
memory. If you generate all the moves, then you'd have to allow for up to
300 moves. So 300*4 bytes=1200. 1200*100 plies=120k.
So then we'd be at 180k total. Still pretty darn insignificant, considering
your hash table will likely consume 128megs or more.
If you have a limited memory system, such as an 8 bit system, then you may
need to adjust things a bit.
Just do the math.
> level). If we use the array as a stack, then the overflow problem is
> gone. Now, however, if our program is to spider the web, or to go
> down the game tree, and we set the levelMax to 10, then the stack
> overflow problem is really not there, as the deepest call stack level
> is 10.
But any program that limits to just 10 ply is going to loose to everybody
and every program. 8 bit micro programs used to go to 8 plies deep....
The q-search may extend for 20 plies or more, depending on how you set
theings.
And for a endgame situation with only a few moves, it's not unrealistic to
expect a program's regular search to reach 30 plies or more in some cases.
Plus q-search.
Even under realistic game positions, going 20 plies deep is not uncommon.
> Is it true that for BFS (Breadth First Search), we always have to use
> an array as a Queue (FIFO)? Using an array seems a bit like a "global
> variable". Is it possible at all to do BFS without using an array as
> a queue and just use recursion?
How you choose to store the data is up to you. And there's nothing wrong
with doing it as a global variable.
The reality is that global variables are a necessity in programming. I
don't mean making everything global. That's bad programming. But it will
be required that some variables be global.
But I doubt recursion is the right program structure for BFS.
I doubt a BFS is the best choice for chess. Or even a good choice.
----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
|
|
