| |
| |
| |
|
Page: 1 2 3 4
Comments:
<0> not that great of a turn up
<0> more time for us then it seems
<1> <ninevolt@ef> in highschool i was supposed to make a chess game where the night just moves around the whole board without touching the same spot twice... i ignored the directions and made it randomly move and try to figure out new ways to do it
<2> yes, it's called a knight tour
<2> very famous problem
<1> <HappyFung@ef> how is optimality judged of chess-playing algorithms?
<1> <ninevolt@ef> could there be a chess computer called "brute force" that statistically calculates its next move based on random strategy
<1> <ninevolt@ef> :P
<2> HappyFung: unfortunately, it's really impossible to "prove" that an algorithm is optimal, other than experiental proof
<2> one common process is to test the algorithm against a number of positions in which the solution is "known"
<0> we wish to prove that it's optimal when it comes to move selection - and that is possible, just not practically yet
<2> where by "known" i mean that the strongest players say so, and nobody's proved them wrong :)
<1> <HappyFung@ef> chessguy: there are sundry proofs of optimality in existence for various algorithms
<2> such as?
<1> <HappyFung@ef> first, did you mean "experiental," or was it a typo?
<2> experiential meaning based on experience. i.e., nobody can beat it.
<1> <HappyFung@ef> here's an optimal algorithm: http://www3.cc.gatech.edu/cl***es/AY2002/cs6210_fall/papers/MutualExForNetwork.pdf#search=%22optimal%20algorithm%22
<1> <HappyFung@ef> any comparison sort is optimal at O(n log n)
<2> oh, are you talking about time efficiency?
<1> <HappyFung@ef> so what do you mean by optimality?
<2> i mean choosing the best move every time
<1> <HappyFung@ef> an exhaustive search is optimal
<2> well sure
<2> but awfully impractical
<1> <HappyFung@ef> next speaker please
<1> <HappyFung@ef> (j/k, chessguy)
<0> well, now that you're on the same page, go on with the original question :)
<0> <HappyFung@ef> how is optimality judged of chess-playing algorithms?
<1> <ninevolt@ef> "One is awakened when mutual exclusion is invoked" --Words of Wisdom
<2> by giving it a number of positions with known best moves and seeing how many it gets right. or simply by having it play other programs and/or humans
<1> <isLandDer@ef> say what?
<0> how is it judged when it comes to time compelxity?
<2> well, in typical engines, you often compare nodes per second
<2> (typical meaning alpha-beta based)
<0> that's a constant!
<3> A* search is optimal given a heuristic that never overestimates.
<1> <ninevolt@ef> i was just quoting the article
<2> yes cwenner
<0> well that's true, in the brute-force approach, you tend to do experiments and take the average branching factor after various pruning
<0> hence NP
<0> but there should be some other approaches in the shadows. i'm interested, could someone mention a few?
<1> <ninevolt@ef> so do you want to win in the shortest moves or measure the destruction of your opponent as moving towards the goal
<2> the number of moves is really irrelevant. the important thing, ultimately, is checkmat
<2> e
<0> it's been almost two hours, could i get an idea of how many wishes to stick to this topic a bit longer and who would like to move on to the next article
<1> <ninevolt@ef> this kind of thing should be what people learn in school
<0> a bit over two hours*
<1> <ninevolt@ef> :)
<2> i'm always willing to discuss this
<0> anyone?
<0> 95% are here to idle
<1> <ninevolt@ef> http://www.eventsounds.com/wav/chess.wav
<0> well, let's stick to this for a bit longer or we'll have one person to discuss with himself
<0> who wants to inquire?
<1> <HappyFung@ef> is there anything in this article which is applicable to a real-world problem?
<2> ah, good question
<2> i think that GP in general, with its notion of telling the computer WHAT to solve instead of HOW to solve it is very applicable to real life
<1> <HappyFung@ef> why?
<4> some things defy a high-level ontology
<2> because i think we get trapped into a mode of thinking that there's only one way to go about solving a particular problem when we need to be open to other possible solutions
<1> <HappyFung@ef> paros: true; i haven't had any ontology cl***es yet though
<2> there may be a radically different way of playing chess that hasn't occurred to us
<2> not to mention, we don't really know how humans play chess
<0> what do you mean, paros? that the complexity is so immense some details must be given? if so - cannot it be generated in the same sense it has for us?
<2> so this is an interesting exploration into trying to formalize something that we don't quite understand
<1> <HappyFung@ef> chess has been going out of style since the defeat of kasparov and the arrest of fischer
<1> <HappyFung@ef> if i'm not mistaken, koza didn't get tenure at stanford
<2> and your point?
<4> cwenner given that the common answer is "it depends on teh position" it becomes more and more difficult to establish a high-level ontology
<4> (in chess)
<1> <HappyFung@ef> i'm not trying to say anything bad about koza, kasparov, fischer, or chess, but for an article like this to be published, there has to be something worthwhile in it
<2> i think GP is certainly worthwhile
<1> <HappyFung@ef> i suspect that gp is dominated by some other paradigm, but i don't happen to know what it is
<2> what do you mean by paradigm?
<1> <HappyFung@ef> gp is merely a stochastic beam search, after all
<1> <HappyFung@ef> it depends on a gradual descent to the solution
<1> <HappyFung@ef> paradigm? problem-solving paradigm
<2> or ascent :)
<4> I think there may be other problems in AI where a "fitness metric" does not exist. Such as a 9-block puzzle
<1> <HappyFung@ef> they didn't use a fitness metric?
<0> does it really affect the performance that much to have three separate trees? cannot they merely have introduced three terminals - AtAdvantage, AtLosing, et.c. (~> MaterialDiff >,=,<). it seems to me it's something that would does it really affect the performance that much to have three separate trees? cannot they merely have introduced three terminals - AtAdvantage, AtLosing, et.c. (~> MaterialDiff >,=,<). it seems to
<0> wouldn't make it harder to take these factors into account while on the other hand, cannot it gain some "insights" in the situations it may advance to.
<2> i think that seems a little artificial too
<2> as in some positions it doesn't matter whether you're winning or losing, the principles that should drive your strategy are the same
<1> <HappyFung@ef> is this the paper: http://www.cs.bgu.ac.il/~sipper/papabs/eurogpchess-final.pdf
Return to
#ai
or
Go to some related
logs:
extension libgd.so freebsd
debian tightvncserver howto
#ubuntu
#linux
#kde
#gaim
gentoo ninan
perl Ircspider
pyxdg failed dependencies
#fluxbox
|
|