Life In 19x19 :: go equation

What do you mean by "reduced"? Are you referring to a representation of board state?

If that's what you mean, then this could be accomplished in several ways.

The simplest representation that comes to mind would be to represent the board state as a single number of 361 digits, with each digit being a value from the set {0, 1, 2} (with 0 being no stone, 1 being a black stone, and 2 being a white stone). The left-most digit could correspond to the top left coordinate of the board, and the right-most digit could correspond to the bottom right coordinate of the board.

Or are you looking for something more complex?

You would need at least 4 values because of ko.

Or maybe even more since you need to mark if someone can play on the specific coordinates.

probably more complex.
more like a Turing state machine, with a 2d tape.
i doubt storing the go board as a single ternary value would be of much help, but i could be wrong.

yes an ai. but a highly deterministic one rather than a random one.
more specifically, something where i can plug in the board state, and get the coordinate for the best next move, and doesn't rely on random trial and error (except perhaps in determining the state machine itself.)

do you think go could be "reduced" to a 361 variable equation, each variable having 3 possible values?
something that I've been pondering. I'm not sure myself, it seems like the answer should be yes, but i have no idea what the equation should look like.
thoughts?

Krama wrote:

You would need at least 4 values because of ko.

Or maybe even more since you need to mark if someone can play on the specific coordinates.

Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone.

Kirby wrote:

Krama wrote:

You would need at least 4 values because of ko.

Or maybe even more since you need to mark if someone can play on the specific coordinates.

Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone.

You need to know what plays are possible to determine the best play or plays.

Krama wrote:

You would need at least 4 values because of ko.

Or maybe even more since you need to mark if someone can play on the specific coordinates.

Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone.

Kirby wrote:

Krama wrote:

You would need at least 4 values because of ko.

Or maybe even more since you need to mark if someone can play on the specific coordinates.

Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone.

Wrong, the state of the intersection is important otherwise you could play an endless ko and it wouldn't even be called a ko.

If you have a position on board you must mark it somehow in order to tell the viewer if it is possible to play on that intersection. Take a ponuki shape in the middle of the board for example. If black has a ponuki shape somewhere on the board then white can not play in the empty intersection inside (unless it's a ko fight and even then you have to mark if that area can be played on next turn or not).

Even in chess - a much more "calculable" game-the hash table approach works only for the endgame - and then, only for a limited number of pieces on the board (I believe perhaps seven total)

If go were solved, you could look up the position of the whole board, along with ko or superko information, and read off the correct play or plays.

Author:	phillip1882 [ Wed Jul 08, 2015 11:23 am ]
Post subject:	go equation
do you think go could be "reduced" to a 361 variable equation, each variable having 3 possible values? something that I've been pondering. I'm not sure myself, it seems like the answer should be yes, but i have no idea what the equation should look like. thoughts?

Author:	Kirby [ Wed Jul 08, 2015 11:32 am ]
Post subject:	Re: go equation
What do you mean by "reduced"? Are you referring to a representation of board state? If that's what you mean, then this could be accomplished in several ways. The simplest representation that comes to mind would be to represent the board state as a single number of 361 digits, with each digit being a value from the set {0, 1, 2} (with 0 being no stone, 1 being a black stone, and 2 being a white stone). The left-most digit could correspond to the top left coordinate of the board, and the right-most digit could correspond to the bottom right coordinate of the board. Or are you looking for something more complex?

Author:	Krama [ Wed Jul 08, 2015 11:35 am ]
Post subject:	Re: go equation
Kirby wrote: What do you mean by "reduced"? Are you referring to a representation of board state? If that's what you mean, then this could be accomplished in several ways. The simplest representation that comes to mind would be to represent the board state as a single number of 361 digits, with each digit being a value from the set {0, 1, 2} (with 0 being no stone, 1 being a black stone, and 2 being a white stone). The left-most digit could correspond to the top left coordinate of the board, and the right-most digit could correspond to the bottom right coordinate of the board. Or are you looking for something more complex? You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates.

Author:	phillip1882 [ Wed Jul 08, 2015 11:38 am ]
Post subject:	Re: go equation
probably more complex. more like a Turing state machine, with a 2d tape. i doubt storing the go board as a single ternary value would be of much help, but i could be wrong.

Author:	Kirby [ Wed Jul 08, 2015 11:42 am ]
Post subject:	Re: go equation
Krama wrote: You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates. Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone.

Life In 19x19 http://www.lifein19x19.com/

go equation http://www.lifein19x19.com/viewtopic.php?f=18&t=12019	Page 1 of 1

Author:	Kirby [ Wed Jul 08, 2015 11:43 am ]
Post subject:	Re: go equation
phillip1882 wrote: probably more complex. more like a Turing state machine, with a 2d tape. i doubt storing the go board as a single ternary value would be of much help, but i could be wrong. What are you trying to accomplish? Do you want to represent board state? Do you want a way to represent a game succinctly? Are you trying to develop an AI? What's the goal?

Author:	phillip1882 [ Wed Jul 08, 2015 1:01 pm ]
Post subject:	Re: go equation
yes an ai. but a highly deterministic one rather than a random one. more specifically, something where i can plug in the board state, and get the coordinate for the best next move, and doesn't rely on random trial and error (except perhaps in determining the state machine itself.)

Author:	Kirby [ Wed Jul 08, 2015 1:11 pm ]
Post subject:	Re: go equation
phillip1882 wrote: yes an ai. but a highly deterministic one rather than a random one. more specifically, something where i can plug in the board state, and get the coordinate for the best next move, and doesn't rely on random trial and error (except perhaps in determining the state machine itself.) I see. You are very ambitious If you find a formula that deterministically gives you the next best move, given a board position, I'd be very impressed. As a side note, for a school project, I did something related, but not exactly the same: * I created a few simple metrics that I could calculate based on a board position (simple formula for calculating influence in the middle game, captured stones, average distance between stones, etc.). * I used these metrics as variables that could easily be calculated at a given middle game board position. * I grabbed a bunch of pro and high-dan level games that were finished with an actual score (eg. B+15.5, W+1.5, etc.). * I used the game records as training data to obtain a function, which returned the estimated endgame score, given a middle game board position. The project was fun, but never amounted to any sort of real score estimator that was reliable. If you're looking to deterministically solve go by a closed formula with a few variables... That'd be even more difficult, I think.

Author:	Bill Spight [ Wed Jul 08, 2015 7:36 pm ]
Post subject:	Re: go equation
phillip1882 wrote: do you think go could be "reduced" to a 361 variable equation, each variable having 3 possible values? something that I've been pondering. I'm not sure myself, it seems like the answer should be yes, but i have no idea what the equation should look like. thoughts? If go were solved, you could look up the position of the whole board, along with ko or superko information, and read off the correct play or plays. Edit: OC, there may not be a correct play, in the sense of one guaranteed to win.

Author:	Bill Spight [ Wed Jul 08, 2015 7:38 pm ]
Post subject:	Re: go equation
Kirby wrote: Krama wrote: You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates. Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone. You need to know what plays are possible to determine the best play or plays.

Author:	Kirby [ Wed Jul 08, 2015 8:14 pm ]
Post subject:	Re: go equation
Bill Spight wrote: Kirby wrote: Krama wrote: You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates. Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone. You need to know what plays are possible to determine the best play or plays. Right. At this point in the discussion, I thought he was aiming for a way to represent the board position - not a way to determine good moves. After clarification, I see that my response wasn't what he was looking for.

Author:	Krama [ Thu Jul 09, 2015 3:58 am ]
Post subject:	Re: go equation
Kirby wrote: Krama wrote: You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates. Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone. Wrong, the state of the intersection is important otherwise you could play an endless ko and it wouldn't even be called a ko. If you have a position on board you must mark it somehow in order to tell the viewer if it is possible to play on that intersection. Take a ponuki shape in the middle of the board for example. If black has a ponuki shape somewhere on the board then white can not play in the empty intersection inside (unless it's a ko fight and even then you have to mark if that area can be played on next turn or not).

Author:	Kirby [ Thu Jul 09, 2015 6:18 am ]
Post subject:	Re: go equation
Krama wrote: Kirby wrote: Krama wrote: You would need at least 4 values because of ko. Or maybe even more since you need to mark if someone can play on the specific coordinates. Ko doesn't matter for a static board position. You look at the board in a given point in time, and each intersection is either empty, has a black stone, or has a white stone. Wrong, the state of the intersection is important otherwise you could play an endless ko and it wouldn't even be called a ko. If you have a position on board you must mark it somehow in order to tell the viewer if it is possible to play on that intersection. Take a ponuki shape in the middle of the board for example. If black has a ponuki shape somewhere on the board then white can not play in the empty intersection inside (unless it's a ko fight and even then you have to mark if that area can be played on next turn or not). I disagree. You can't say the representation is "wrong" unless we have defined what we are trying to represent. And my suggestion was before this was clarified. Anyway, your case is only true if you are enforcing rules in your representation of the board position, and if board positions contain information about previous board positions. If you are just looking for a board representation indicating placement of pieces, knowledge of ko or other rules is not necessary. To give an example, the representation I suggested generates a unique number for any unique placement of stones on the go board. Since the ko rule can be enforced by disallowing repeat board positions, one simple way to handle ko in a computer application would be to store each unique board position number in a hash table after the move was made. Then, when a new board position is made from a new move, check the hash table to see if the number generated by the new board position is unique to the game. If not, reject the move. There are many ways you can "represent" go. Anyway, this isn't what the OP is looking for anyway, so it is off topic.

Author:	DrQuantum [ Sun Aug 02, 2015 6:13 am ]
Post subject:	Re: go equation
There are a number of significant issues with the original question. Among them is the most significant one - the idea that there is a single best move to be made given a board position. If there is not a single best, then this project will fail. One can re formulate the question, perhaps, but a deterministic hash table to absolutely determine the best possible move will not be realizable. Even in chess - a much more "calculable" game-the hash table approach works only for the endgame - and then, only for a limited number of pieces on the board (I believe perhaps seven total)

Author:	djhbrown [ Thu Oct 08, 2015 4:21 pm ]
Post subject:	Re: go equation
outcome(board) = if nomovepossible then balanceofterritory (black, white) else foreach(move) (outcome (move(board)))

Page 1 of 1	All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/

Author:	SoDesuNe [ Sun Aug 02, 2015 6:26 am ]
Post subject:	Re: go equation
DrQuantum wrote: Even in chess - a much more "calculable" game-the hash table approach works only for the endgame - and then, only for a limited number of pieces on the board (I believe perhaps seven total) Endgame with seven pieces is solved since 2012. Though the tablebase, when finally compiled to use with your average chess program, is likely to be around 100 terabyte. So, I guess it's a problem of storage and not a problem of computing? : D

Author:	RobertJasiek [ Thu Oct 08, 2015 10:44 pm ]
Post subject:	Re: go equation
Bill Spight wrote: If go were solved, you could look up the position of the whole board, along with ko or superko information, and read off the correct play or plays. Provided the universe offers enough quantum states to store more than 1.2 * 10^172 positions with their correct moves (under a given ruleset) and we can access all those quantum states linearly;)