It is currently Fri May 02, 2025 2:32 pm

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 12 posts ] 
Author Message
Offline
 Post subject: balanced ternery: the best for go?
Post #1 Posted: Sat Aug 17, 2013 10:47 am 
Lives in gote

Posts: 322
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
first a brief intro into balanced ternary.
to convert a standard int into balanced ternary first divide by 3 and record the remainder, as if you were going for standard ternary:
1579 | 3
526 r 1
173 r 1
57 r 2
19 r 0
6 r 1
2 r 0
0 r 2
so 1579 is 2010211 in standard ternary. then to convert to balanced ternary;
change each 1 in to a +
20+02++
then change each 2 into a -, and adding "1" or "+" or the next place
+-++-++ this is balanced ternary representation of a number.
now, for go, we have three state, black white and empty.
for balanced ternary we also have 3 states, "+" "0" and "-"
clearly this gives some interesting possibilities. we can essentially represent adding a stone as addition or subtraction and a capture the same way.
then go truly becomes a computational problem.
what do you think?


This post by phillip1882 was liked by: Ortho
Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #2 Posted: Sat Aug 17, 2013 7:21 pm 
Lives in gote
User avatar

Posts: 314
Location: Germany
Liked others: 10
Was liked: 128
Rank: KGS 4k
Quote:
clearly this gives some interesting possibilities. we can essentially represent adding a stone as addition or subtraction and a capture the same way.

I don't see anything "clearly" about this. Do you care to elaborate how base 3 representation of integers cuts down on the computational costs of the algorithms needed for computer go? (Recognize connected strings, count liberties, capture.)

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #3 Posted: Sat Aug 17, 2013 9:04 pm 
Judan
User avatar

Posts: 5546
Location: Banbeck Vale
Liked others: 1104
Was liked: 1457
Rank: 1D AGA
GD Posts: 1512
Kaya handle: Test
phillip1882 wrote:
... go truly becomes a computational problem.
what do you think?


I think that you need a very fast computer.

_________________
Help make L19 more organized. Make an index: https://lifein19x19.com/viewtopic.php?f=14&t=5207

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #4 Posted: Sat Aug 17, 2013 9:37 pm 
Lives in gote

Posts: 322
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
here's what i'd do.
represent each row as a balanced ternary number,
as well as each column.
top left would be most significant trit.
let's define some operators.
<< = multiply by 3;
now for some functions.
Code:
place_stone(x,y,turn):
   row[x] += turn<<(19-y)
   col[y] += turn<<(19-x)
check_stone_value(x,y):
   v = str(row[x])
   return v[y]
check_liberties(x,y,turn,elements):
   v = check_stone_value(x,y)
   count = 0
   elements += [[x,y]]
   if v == turn:
      if x > 0 and [x-1,y] not in elements:
         count += check_liberties(x-1,y,turn,elements)
      if x < 18 and [x+1,y] not in element:
         count+= check_liberties(x+1,y,turn,elements)
      if y > 0 and [x,y-1] not in elements:
         count+= check_liberties(x,y-1,,turn,elements)
      if y < 18 and [x,y+1] not in elements:
         count += check_liberties(x,y+1,turn,elements)
   elif v == 0:
      return 1
   else:
      return 0
   return count
remove_captures(elements,turn):
   count = len(elements)
   for i in elements:
      row[elements[i][0]] += turn<<(19-elements[i][1])
      col[elements[i][1]] += turn<<(19-elements[i][0])

just throwing some ideas out there for you.

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #5 Posted: Sat Aug 17, 2013 10:12 pm 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
Well, usually when trying to improve on algorithms you first need to figure out where the bottle neck is. What exactly are you trying to fix here? And I do mean exactly.

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #6 Posted: Sun Aug 18, 2013 12:09 am 
Lives in gote
User avatar

Posts: 314
Location: Germany
Liked others: 10
Was liked: 128
Rank: KGS 4k
That's cool, seems you know some sort of scripting language (I'd guess ruby on rails, or maybe it's python?).

You have however not answered my question in the slightest. Posting obfuscated code is not the way to go. Instead use clear arguments in plain words.

I'll repeat my question: please give me an example of an algorithm used in computer go (for example anything that implements the basic rules of the game) where the use of ternary over binary results in a saving of CPU cycles.

You may assume for this that you're given a computer with ternary architecture.

All I have so far observed is that you figured trits are better than bits because a trit encapsulates an intersection on a go board (with its 3 possible states black, white and empty).
I have not yet seen a compelling argument how this results in faster algorithms. (Mind you, that does not mean that this is not the case. I just don't see it following from what you've posted so far.)

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #7 Posted: Sun Aug 18, 2013 2:27 am 
Gosei
User avatar

Posts: 1585
Location: Barcelona, Spain (GMT+1)
Liked others: 577
Was liked: 298
Rank: KGS 5k
KGS: RBerenguel
Tygem: rberenguel
Wbaduk: JohnKeats
Kaya handle: RBerenguel
Online playing schedule: KGS on Saturday I use to be online, but I can be if needed from 20-23 GMT+1
leichtloeslich wrote:
some sort of scripting language (I'd guess ruby on rails, or maybe it's python?)


Just to play the "computer grammar nazi" here. The language is ruby, not ruby on rails (rails is a web framework built on top of ruby.)

Also this is more of a feeling, but nowadays scripting language is used to refer to basically shell script (sh and similar, awk would also fit the role) and (I don't know why) perl. Ruby, python and other interpreted languages are no longer qualified as scripting, except in the rare cases when they are used to write throaway scripts.

The example from phillip1882 looks like neither proper ruby nor proper python, since functions are not being defined using def (which is the way to define functions in both languages, def functionname (something):) But looks pretty close to both (in fact the pseudocode I learnt a long while ago in "CS 101" was pretty close to both, too)

_________________
Geek of all trades, master of none: the motto for my blog mostlymaths.net

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #8 Posted: Sun Aug 18, 2013 9:16 am 
Lives in gote

Posts: 322
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
Quote:
I'll repeat my question: please give me an example of an algorithm used in computer go (for example anything that implements the basic rules of the game) where the use of ternary over binary results in a saving of CPU cycles.

You may assume for this that you're given a computer with ternary architecture.

All I have so far observed is that you figured trits are better than bits because a trit encapsulates an intersection on a go board (with its 3 possible states black, white and empty).
I have not yet seen a compelling argument how this results in faster algorithms. (Mind you, that does not mean that this is not the case. I just don't see it following from what you've posted so far.)

okay, sorry i thought you wanted an example of computer code that would be more efficient.

firstly I'd like to point out that ternary computers are provably faster than their binary counter parts.
secondly, you can easily identify a single intersection with a single trit rather than 2 bits. so this means you can represent a whole board state with 361 trits rather than 722 bits. both capture and placing stones could be made much faster, because again you are only changing a single trit per intersection, rather than 2 bits.
liberties would be easy to count, simply note the number of 0's around the symbols "+" or "-".
and again, since this is a ternary computer, that 0 is a single trit long, rather than 00 you would need for binary.
the down side is that ternary computers are more financially costly than the speed up makes worth their while.
Quote:
The example from phillip1882 looks like neither proper ruby nor proper python, since functions are not being defined using def (which is the way to define functions in both languages, def functionname (something):) But looks pretty close to both (in fact the pseudocode I learnt a long while ago in "CS 101" was pretty close to both, too)

its pseudo python. just put def in front of the functions, and make sure they are called properly and they will run, all-be-it most of the functions wont work properly since this is designed for a ternary CPU.

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #9 Posted: Sun Aug 18, 2013 9:28 am 
Lives with ko
User avatar

Posts: 193
Location: Trondheim, Norway
Liked others: 76
Was liked: 29
Rank: 2d EGF and KGS
GD Posts: 1005
Universal go server handle: sverre
phillip1882 wrote:
firstly I'd like to point out that ternary computers are provably faster than their binary counter parts.


For all algorithms? By how much? Can you give me a link to this proof?

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #10 Posted: Sun Aug 18, 2013 9:31 am 
Lives in gote

Posts: 322
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
you know, now that i think of it, you're right ternary wouldn't be THAT much faster than binary.
if you kept 2 copies of the board: a 0,1 for black and 0,1 for white; you cold make a pretty fast algorithm.
:grins: off to code!!!

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #11 Posted: Sun Aug 18, 2013 9:58 am 
Lives in gote

Posts: 322
Liked others: 4
Was liked: 39
Rank: 6k
GD Posts: 25
OGS: phillip1882
primarily since comparisons, as well as number themselves, can be represented more compactly with ternary, ternary is more efficient.
anyway here's a nice pdf on ternary computers.
http://xyzzy.freeshell.org/trinary/CPE% ... 20RC6a.pdf

note its 196 pages long so it takes a while to download. the integer efficiency is covered on page 14.

Top
 Profile  
 
Offline
 Post subject: Re: balanced ternery: the best for go?
Post #12 Posted: Sun Aug 18, 2013 11:10 am 
Oza

Posts: 2356
Location: Ireland
Liked others: 662
Was liked: 442
Universal go server handle: Boidhre
phillip1882 wrote:

firstly I'd like to point out that ternary computers are provably faster than their binary counter parts.


I thought that was for specific tasks, not generally.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group