...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest
...Haven't the foggiest ...Haven't the foggiest
...Haven't the foggiest
Go Back  Xtreme Visual Basic Talk > > > ...Haven't the foggiest


Reply
 
Thread Tools Display Modes
  #1  
Old 10-23-2009, 06:13 PM
Hachen Hachen is offline
Newcomer
 
Join Date: Aug 2009
Posts: 7
Default ...Haven't the foggiest


I'm not positive if this should be here or in graphics so I'm sorry if I'm posting it in the wrong section.

I'm trying to make a program for the game Go. Now before getting upset that I want to make the game go I just want to say that I have looked for months for this specific thing and I still have yet to find it. I want to make something to simulate go so that two people can play on the same computer. The problem I ran into was capturing stones. Stones are captured when surrounded and then they are taken from the board. The problem is that I don't know how to make the program know when a black stone is surrounded.

I have thought of a grid detecting but the possibilites on a 19x19 area are too high for anybody to sit down and program. I have also thought of using picture boxes and the edges to detect other pictures, but there are ways for stones to group together and the opponent must surround all stones to capture them.

Any ideas are appreciated and yet again, sorry if this should either be in graphics or is somehow against the rules.
Reply With Quote
  #2  
Old 10-23-2009, 10:16 PM
Hachen Hachen is offline
Newcomer
 
Join Date: Aug 2009
Posts: 7
Default

Sorry, Nevermind. I actually found a go simulator that lets you do what I wanted. If anyone is interested it is called gogod. Sorry for taking up the forum space with this.
Reply With Quote
  #3  
Old 10-24-2009, 03:06 PM
Qua's Avatar
Qua...Haven't the foggiest Qua is offline
Impetuous & volatile

* Expert *
 
Join Date: Apr 2005
Posts: 2,177
Default

I'm not familiar with the rules of Go, but why do you feel that you would have to check 19x19 tiles everytime a single piece was placed on the board? Wouldn't you just have to check the 9 titles surrounding the placed tile to see if the placed stone helped capture any stones? That will never end up being 19^2 computations. At most you will check in 9 directions and in a worst case scenario you will have to identify 9 stones in each direction equaling 81 checks which is very manageable.
__________________
Reading is the foundation for all knowledge - Unknown.
Reply With Quote
  #4  
Old 10-24-2009, 08:10 PM
AtmaWeapon's Avatar
AtmaWeapon...Haven't the foggiest AtmaWeapon is offline
Fabulous Florist

Forum Leader
* Guru *
 
Join Date: Feb 2004
Location: Austin, TX
Posts: 9,500
Default

If I remember correctly, in Go you capture pieces by surrounding them with yours. So, for an easy case, you might have a 2x2 square of pieces that I surround with a 12-piece hollow square, then your 4 pieces become mine and I now have a 4x4 square.

Still, there's no need to check the entire board for each piece. I've never tried implementing such a thing, but here's a crack at a more efficient algorithm. When a player drops a piece, I'd look for "groups" of pieces by looking for same-colored squares adjacent to a particular square (these groups would be stored in some data structure). Then, I'd look to see if any of the adjacent pieces are part of a group; if so, I'd merge groups. Next, I'd check nearby "enemy" groups to determine if my move surrounded them by checking each perimeter piece.

I'm not super familiar with the rules of Go, but I believe this would dramatically reduce the search space. When you complete the 2x2 square, 8 checks would be made and I'd have the overhead of noticing the 3-piece structure that was there previously is now a 4-piece structure. When I complete my surrounding square, 8 checks would be made, the 12-piece structure would be constructed, and 96 checks would be required in the most naive algorithm to notice I surrounded the 4-piece structure. Intuitively it looks like I could narrow that 4 checks by seeing if all "internal" pieces are enemy pieces, but I am not sure how easy it is to express algorithmically. Seems like a neat challenge!

So even with a dumb algorithm, this is (8 + 16 + 96) + 2n = 120 + 2n units of overhead, where n is the overhead for structure comparison. This is dramatically less than the 19*19*8 = 2,888 checks.

Still, I haven't given it much thought, so I could be wrong.
__________________
.NET Resources
My FAQ threads | Tutor's Corner | Code Library
I would bet money 2/3 of .NET questions are already answered in one of these three places.
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest ...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest ...Haven't the foggiest
...Haven't the foggiest
...Haven't the foggiest
 
...Haven't the foggiest
...Haven't the foggiest
 
-->