parellel programming basic ideas

[adams161]

i'm thinking of implementing 2 core parallel computing in my connect 4 program so i can see if i'm capable of doing this before i start in my chess program which would be in the future. the four program is in c++ and chess program in c.

i was talking to someone and he said you could basicly implement parallel computing on a fixed leaf like ply 3. lets say i had 7 moves on ply 3 to make. i'm thinking i spin off a thread to search the first move and then i go on and search the second move. when both complete, i run through my checks on if > alpha then if >= beta twice, in order of the moves that completed. then i move on and search moves 3 and 4. for move 7 of course i would not split it since its an odd number move and just search on one processor. Now bear in mind i'm not interested right now in max efficiency, only in seeing if i can get it to work.

here is my first question:

how do i spin of the thread for move 1 on ply 3 and then move to move 2? do i do something like:

score1=-100000;
score1=thread(search(move1);
score2=search(move2);
while(score1 is still = -100000)
{
// thread not done
:
}
// i get here i'm done with both moves

unmake both moves and check score1 then score2 against alpha beta.

repeat on moves 3 and 4.


now that was the algorithm question. i'm interested in a c++ or c approach in windows right now.

second question, memor and variables.

I assume i should keep just about all my variables local to avoid memory issues, i can override the globalness of a variable by passing it as a parameter to search. hash will be global. if hash is global is that enough for both threads to use it? i have used threads a little in java and i realize i need to lock memory access before reading or writing to hash using some type of mutex or something.

so my two questions are on algorithm developement and memory using windows and c and c++. links are great too if people know of good ones particularly wtih short code examples.

i'm not using any kind of terminology in my example above that implies i understand how c/c++ programming language works in terms of calling threads etc. As i see it i have two chores. one is learn the basic programming language rules for using threads and the other is learn the language independent way that the algorithm actually works.

If directed to crafty source code, i'm hoping for some talking answers as well, link please, i'm not up on where it is.

Mike

[Dann Corbit]

Have you examined Viper and Scorpio?
Those are definitely the easiest programs to learn threading search from.

[jswaff]

i'm thinking of implementing 2 core parallel computing in my connect 4 program so i can see if i'm capable of doing this before i start in my chess program which would be in the future. the four program is in c++ and chess program in c.

Multithreading is tremendous fun. You'll probably learn a lot. Good luck!

i was talking to someone and he said you could basicly implement parallel computing on a fixed leaf like ply 3. lets say i had 7 moves on ply 3 to make. i'm thinking i spin off a thread to search the first move and then i go on and search the second move. when both complete, i run through my checks on if > alpha then if >= beta twice, in order of the moves that completed. then i move on and search moves 3 and 4. for move 7 of course i would not split it since its an odd number move and just search on one processor. Now bear in mind i'm not interested right now in max efficiency, only in seeing if i can get it to work.

Well, you've already pointed it out yourself, but that really is going to be horribly inefficient. But if you're going to arbitrarily split at some ply, why ply three (as opposed to the root)? But anyway, I understand you're just cutting your teeth here. Once you're done look into a better algorithm like Young Brothers Wait.

here is my first question:

how do i spin of the thread for move 1 on ply 3 and then move to move 2? do i do something like:

score1=-100000;
score1=thread(search(move1);
score2=search(move2);
while(score1 is still = -100000)
{
// thread not done
:
}
// i get here i'm done with both moves

unmake both moves and check score1 then score2 against alpha beta.

repeat on moves 3 and 4.


now that was the algorithm question. i'm interested in a c++ or c approach in windows right now.

If you wanted to use the pthread library you could check into the pthread_create and pthread_join functions. (Doing a bunch of pthread_creates within a search is very expensive BTW. Later you'll want to do something like maintaining a pool of threads.) You should be able to find Windows specific equivalent to those functions if you don't want to use the POSIX stuff.

second question, memor and variables.

I assume i should keep just about all my variables local to avoid memory issues, i can override the globalness of a variable by passing it as a parameter to search. hash will be global. if hash is global is that enough for both threads to use it? i have used threads a little in java and i realize i need to lock memory access before reading or writing to hash using some type of mutex or something.

You've got the right idea here. One idea (used by Viper IIRC) is to keep an array of "search stack elements", one stack per thread. Each of those search stack elements would be indexed by ply. See Viper for specifics there.

As far as the hash table, you can lock it using mutexes, look into the lockless hashing algorithm (google for Hyatt Mann Lockless Hashing), or ... some have claimed you can ignore the problem as long as you can detect and handle a bad move coming out of the hash table.

so my two questions are on algorithm developement and memory using windows and c and c++. links are great too if people know of good ones particularly wtih short code examples.

i'm not using any kind of terminology in my example above that implies i understand how c/c++ programming language works in terms of calling threads etc. As i see it i have two chores. one is learn the basic programming language rules for using threads and the other is learn the language independent way that the algorithm actually works.

Here is a link that might be useful:
https://computing.llnl.gov/tutorials/pthreads/
Again, that's for POSIX stuff, which you may or may not be interested in.

Good luck!

If directed to crafty source code, i'm hoping for some talking answers as well, link please, i'm not up on where it is.

Mike

[bob]

i'm thinking of implementing 2 core parallel computing in my connect 4 program so i can see if i'm capable of doing this before i start in my chess program which would be in the future. the four program is in c++ and chess program in c.

i was talking to someone and he said you could basicly implement parallel computing on a fixed leaf like ply 3. lets say i had 7 moves on ply 3 to make. i'm thinking i spin off a thread to search the first move and then i go on and search the second move. when both complete, i run through my checks on if > alpha then if >= beta twice, in order of the moves that completed. then i move on and search moves 3 and 4. for move 7 of course i would not split it since its an odd number move and just search on one processor. Now bear in mind i'm not interested right now in max efficiency, only in seeing if i can get it to work.

This is not going to work very well. You need to search the first move before you start a parallel search to search the rest of the moves. The first move gives you an alpha bound that will reduce the size of the trees for the remainder of the moves. If you don't have that alpha bound, you will search much larger trees and the speedup will be poor.

here is my first question:

how do i spin of the thread for move 1 on ply 3 and then move to move 2? do i do something like:

score1=-100000;
score1=thread(search(move1);
score2=search(move2);
while(score1 is still = -100000)
{
// thread not done
:
}
// i get here i'm done with both moves

unmake both moves and check score1 then score2 against alpha beta.

repeat on moves 3 and 4.


now that was the algorithm question. i'm interested in a c++ or c approach in windows right now.

second question, memor and variables.

I assume i should keep just about all my variables local to avoid memory issues, i can override the globalness of a variable by passing it as a parameter to search. hash will be global. if hash is global is that enough for both threads to use it? i have used threads a little in java and i realize i need to lock memory access before reading or writing to hash using some type of mutex or something.

Global hash is fine, but you have to be careful as both threads will be writing to the hash, and you can get a single entry that may have data from two different positions due to the race conditions caused by multiple writes. If this won't hurt your program, you can ignore it. Locking on the hash probes is horribly expensive and will slow you down.

so my two questions are on algorithm developement and memory using windows and c and c++. links are great too if people know of good ones particularly wtih short code examples.

i'm not using any kind of terminology in my example above that implies i understand how c/c++ programming language works in terms of calling threads etc. As i see it i have two chores. one is learn the basic programming language rules for using threads and the other is learn the language independent way that the algorithm actually works.

If directed to crafty source code, i'm hoping for some talking answers as well, link please, i'm not up on where it is.

Mike