|
On July 21 2007 14:49 LeoTheLion wrote:to publish a paper in science that's worth it guaranteed professorship for the rest of his life
Science is probably the most respected journal in the scientific world/industry. another top one is Nature.
this paper might well be a stepping stone for this professor to obtain tenure at his institution, or to move to another institution that has better academic assets available for furthering research
it is by no means a "shame" or "waste" to publish in Science - if only i had that kind of opportunity in my research heh
|
Bill307
Canada9103 Posts
On July 22 2007 14:30 mahnini wrote:Show nested quote +On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it.
Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn.
Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where:
a) it is impossible to draw: the game always ends in a win or a loss; and
b) player 1 can choose to pass on his first move (and no other moves can be passed on).
Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins.
Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did).
|
On July 22 2007 14:42 Bill307 wrote:Show nested quote +On July 22 2007 14:30 mahnini wrote:On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it. Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn. Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where: a) it is impossible to draw: the game always ends in a win or a loss; and b) player 1 can choose to pass on his first move (and no other moves can be passed on). Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins. Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did).
I see what you are saying, but wouldn't you have to prove both a and b? How would you prove a and b without playing out every possible move?
|
A and B are the rules of the game
|
On July 22 2007 14:52 mahnini wrote:Show nested quote +On July 22 2007 14:42 Bill307 wrote:On July 22 2007 14:30 mahnini wrote:On July 22 2007 01:13 haduken wrote:On July 21 2007 18:37 mahnini wrote:On July 21 2007 18:07 HeadBangaa wrote:
Wow they really brute-forced this.
I thought it was going to be some clever algorithm, too bad. What? brute-force means the most costly but sometimes more obvious way of doing thing. By using a brute-force algorithm, you may potentially use up more time and storage in your calculation. (computer wise) So in a nut-shell, a dumb but working method. I understand the difference, I just don't understand how you would solve checkers without brute-forcing, as if some algorithm could be thought up without first brute-forcing it. Well, the alternative for "solving" checkers would be to come up with a mathematical proof that proves the outcome of the game is always a draw, given that both players always make the best possible move on each turn. Here is a simple example of a proof that solves a game: suppose you have a non-random 2-player game where: a) it is impossible to draw: the game always ends in a win or a loss; and b) player 1 can choose to pass on his first move (and no other moves can be passed on). Then it is easy to prove that player 1 always wins, given that both players always make the best move. Because it is impossible to draw and the game has no randomness, we know that either the first person to move will win, or the second person to move will win. Because player 1 can choose whether he plays first or second, he can just choose whichever case always leads to a win. Therefore player 1 always wins. Of course, sometimes it must be veritably impossible to come up with a proof like this, and so the only realistic way to solve the game is to brute-force every position, or prove that only a subset of those positions need to be analysed and then brute-force said subset (which is what the Chinook team did). I see what you are saying, but wouldn't you have to prove both a and b? How would you prove a and b without playing out every possible move?
Read this book, it will change the way you think about life, and stretch your mind!
http://www.amazon.com/Algorithms-Sanjoy-Dasgupta/dp/0073523402
|
testpat
United States565 Posts
Terminology is going to be bad here, hopefully the examples will be better.
Easiest: If in part of a tree, you evaluate one move to a win/loss, you don't need to search any other moves in that portion of the tree. This is a major source for pruning min max trees.
You can also do some pruning based on the knowing the states of the games. For example.
You can prune parts of trees without solving them if you can show that the subtree is suboptimal to another option. In chess, you can prune all trees that promote pawns into bishops & rooks because all future moves will be a subset of queen. However, you must analyze trees that promote into knights.
You can also prune paths that lead to solved states if the current path is a superset of a solved state. For example, if you know that a certain checkers position leads to a win for white with no kings, and you are evaluating a state that is the same except one of the white pieces is a king.
(However, this requires knowing/evaluating that the king cannot be forced into a move that regular piece couldn't make).
|
So this pretty much kills checkers, feels meaningless to play a game when you know theres an optimal strategy 
Luckily it's pretty much impossible to do for more advanced games, since the number of available strategies are enourmous compared to the ones in checkers.
iirc some math professor estimated the number of strategies in chess to 10^120
developing algorithmes for optimizing the play get's a lot more interesting in such games
|
MyLostTemple
United States2921 Posts
lets get a computer that can own at difficult game ;o
|
|
|
|
|
|
EPT
