balanced ternery: the best for go?

phillip1882 · #1

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?

leichtloeslich · #2

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.)

Joaz Banbeck · #3

phillip1882 wrote:

... go truly becomes a computational problem.
what do you think?

I think that you need a very fast computer.

phillip1882 · #4

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.

Boidhre · #5

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.

leichtloeslich · #6

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.)

RBerenguel · #7

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)

phillip1882 · #8

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.

Sverre · #9

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?

phillip1882 · **#10**

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!!!

phillip1882 · **#11**

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.

Boidhre · **#12**

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.

balanced ternery: the best for go?

Who is online