Preventing Solvability in Games of Complete Information

Discussion in 'Game Design' started by Saturday Saint, Feb 29, 2012.

  1. Saturday Saint

    Saturday Saint Well-Known Member

    How do you prevent solvability in games of complete information? I think there are two things that are necessary, but I'd like your thoughts on it as well. By complete information, I mean that you are presented with all the information in the game in a way where you can process it. That is, there's no fog of war, no randomly ordered deck, no hidden hands, moves are slow enough to be reacted to (or turn-based), etc.

    Anyways, here are the two things I think are important:

    1. Too much information to fully explore.

    This means that it would be unrealistic for players to fully explore every relevant move or gamestate in the game. Just put so much into the game that players are always learning, even years or decades after the game is made.

    2. Information is varied enough that different players can build different valuation.

    I'm not sure how you would go about doing this—it might just happen naturally as a result of #1—but it seems important. You need different players to have different senses of valuation and not all come to the same conclusions. If two players both think that move A is the best move in a given situation, then suddenly the best move is actually B, which counters A. But then it's C, which counters B! Etc. This would be fine in a game that isn't complete information, as it give you a very simple RPS yomi, but in a game of complete information you get stuck in these whoever-goes-first-dies (Player A plays rock; being a game of complete information, player B knows this so he just plays paper and wins) or always-a-cats-game scenarios (see: Tic-tac-toe).

    Anyways, thoughts?
  2. Leartes

    Leartes Well-Known Member

    I'm not a huge fan of designing abstract games so take my opinion with a grain of salt.

    I think most games turn out not solvable if you ensure some other properties.

    First of all the gamespace has to be to large to explore it completely. This can be done quite easily.

    Second a large part of the gamespace has to be relevant. I'd argue there are more games in go that totally make no sense than games that make sense. Games as in moveorders from start to end. Still the amount of good games is large enough to not be explored either.
    You could for example imagine a game with a huge gamespace but only a single viable path that leads to a draw. As soon as any player deviates from this path it is easy for his opponent to punish him and win the game.

    Now to ensure the second property you can introduce intermediate goals (like capturing stones, securing good positions on some part of the board etc.) which can be traded. If in go the strongest move always was to reply locally the game would be far worse. Luckily I can trade a disadvantage somewhere for an advantage somewhere else.
  3. Delha

    Delha Active Member

    Are you asking for a truly unsolvable game, or just one where it's not practically solvable by a human player?
  4. Sirlin

    Sirlin Steward of the Realm Staff Member

    I think a complete information turn-based game is necessarily solvable? He probably means ways to make it harder / take longer to solve, so that for practical purposes when played by humans, there's still a game left.
    NoahTheDuke and Gon like this.
  5. Delha

    Delha Active Member

    Yeah thanks, that's pretty much what I was trying to confirm.
    NoahTheDuke likes this.
  6. Gon

    Gon Active Member

    Can you also argue that making unclear payoffs will lead to variance in valuation? Like in chess it is not always clear what the payoff of castling is, and so people might value that differently.
  7. Logo

    Logo Well-Known Member

    Does RPS count as a game of complete information? You know everything there is to know about the game, with the caveat that you don't know what your opponent is going to do (which applies to Chess, Go, etc. as well). The only difference between the latter games and RPS is you take turns simultaneously in RPS.

    So a short answer would be: Have the game be real-time/Simultaneous. Frozen Synapse (Light Mode) is a great example of this.

    EDIT: I guess you do say that moves should be slow enough to be reacted to, but in something like RPS or FS you have plenty of time to 'react', it's just that turns happen at the same time. Either way I don't think that criteria (or a criteria to be turn based) is a required criteria of being a game of complete information. It's more like you're asking the question you asked + if your actions produce a deterministic result. But then I suppose that's just semantics in some ways.
  8. Rufus

    Rufus Member

    In RPS players don't know the opponents choice when they make their own. Therefore it's not a game of complete information.
    Leartes likes this.
  9. dzebra

    dzebra Active Member

    Here's one. If at every decision point in the game there are multiple options that are exactly equally balanced, then there is more than one thing that a player can do to attain the optimal outcome. I don't know if that would be considered "Solved, but with 1,000 optimal solutions" or "Unsolvable."

    But any time a game is being played between humans, there is the hidden information of Player Intention. Many games don't take advantage of this, so all relevant information is evident in the game state (on the game board). For example, in Diplomacy, the state of the game is always 100% known to all players, with the exception of Player Intention. That's an extreme example, but I think it also applies in lesser way to games like Chess (or Go, or GIPF, or whatever). Is he moving this piece in order to attack with stacked Rooks down a file, or is he just trying to get his bishops free? (I'm not good enough at Chess to know how much Player Intention affects games, this was just an example)

    I think the trouble with solvability comes in turn-based games where each turn the action of the player can be counteracted by the other player (like turn based RPS). If the turns are simultaneous, or if doing significant things in the game takes multiple turns to set up, then Player Intention becomes a huge shaping factor of how the game plays out.

    So I think there are ways to make a Perfect Information game unsolvable. Either with perfect balance in many possible game states, or with increased reliance on the effect of Player Intention.
  10. Sirlin

    Sirlin Steward of the Realm Staff Member

    Player intention is completely irrelevant in chess if we are talking about solvability. People's different valuation of castling is also completely irrelevant. The answer is that is solvable, but the solution for optimal play is not yet known. Someday when it is known though, it will make zero different why the opponent makes a move, you just do the optimal response. There seems to be confusion here again if we are talking about technically solvable (chess is) or ways to make it harder to solve for humans.

    Another point of confusion seems to be complete vs perfect information. Chess has both complete and perfect information. Yomi card game has complete information but not perfect information. Complete means you know everything about how the game works, all the rules and data and what causes what exactly. This is true even if the game involves simultaneous plays like Yomi. Perfect information means you know everything about the gamestate when you make decisions, so it can't be something with simultaneous plays.

    As far as I know, all turn-based games of perfect information are solvable. And so are all complete information games, though note that a solution can include a mixed strategy, such as doing one thing X% of the time and another Y% of the time.
    Leartes and garcia1000 like this.
  11. Claytus

    Claytus Well-Known Member

    Yeah, Sirlin's right, there's no actual answer to this question. Perfect information games (which sounds like what the OP actually meant), just are solvable.

    As for the two solutions proposed:
    1) Make it too complex.
    A: Don't rely on this. Your playerbase is larger and smarter than you are. It doesn't matter how "realistic" it is for someone to process all the data, they'll do it anyway.

    2) Rely on valuation as a skill.
    A: Again, can't be relied on. It doesn't really matter how much input you give a player to come up with their own valuations. Someone will just solve it with math, and post the solution.

    Case Study: Go read up on Garcia1000's old Kongai posts. Best example I know of (and definitely easiest to research), of a player breaking a system that was supposed to involve yomi, but ended up providing enough information to players that someone found a set of mathematically optimal moves in a lot of endgame situations, and then the winner came down to RNG miss rates.
  12. Logo

    Logo Well-Known Member

    I don't see how Frozen Synapse light mode fits into Sirlin's categories. Yomi is complete information, but has decks of random order and what not so it seems very different from the amount of information you get in Frozen Synapse. Yet FS is simultaneous plays so it's not perfect information either.

    In FS you know the game state when you make your move as well as all possible moves your opponent make. You can't rule out that the game is solvable either. It's entirely possible that a game board situation will be such that you can make a series of moves tailored based only on what your opponent HAS done and be sure to win (no different than chess in that case).
  13. Claytus

    Claytus Well-Known Member

    Are you asking whether Frozen Synapse is complete information or perfect information??? (I'm really not sure, your post is weird).

    If so, the answer is it's complete information. It's a pretty wide category, so you don't need some other term to say "less random than yomi, but more random than chess"... it wouldn't add much to have such a term anyway. Having turns be double-blind, however, does mean the players don't have full information about the gamestate (because whatever hidden moves your opponent has queued up are part of the gamestate).
    Logo likes this.
  14. Gon

    Gon Active Member

    Doesn't unclear payoffs contribute to "solution is not yet known"? Cause that's what I was trying to get at. I also phrased it as a question because I am not sure, just suggesting an idea.
  15. Claytus

    Claytus Well-Known Member

    That's not how computers work. Once we can solve Chess... *we can also solve all games as complex as Chess*. The centuries that it took for us to get to this point are irrelevant. What's true is that *right now* solving games is very easy, and trying to create a game that's "hard to solve" is a pretty much a pointless endeavor.

    I guess Arimaa shows that it can be done. But who do you know who plays Arimaa?


    Actually... that's completely fair to say. I feel like you either don't understand games or math to be able to type that sentence in. Games are an abstract system of rules, and math provides us with a structured way to deal with abstract systems of rules.
  16. Sirlin

    Sirlin Steward of the Realm Staff Member

    Well, it's fine to make a game harder to solve. And you should. I just thought it was necessary to point out the distinction between these kind of games being inherently solvable, and the efforts to delay the solution.

    I would also recommend looking at garcia's Kongai endgames but for the opposite reason as Claytus said. With kongai, the goal was to make it very hard to solve. And really...it worked. Garcia would post an end game scenario that was ridiculously "end game." Like so many things out of the equation because it's RIGHT at the end of the game. And it would take like 20+ pages of posts and debate to even answer that one tiny, tiny point in the vast data space of the game. So the takeaway is that it worked. There's years of gameplay in Kongai, but there might have been a week or couple days of gameplay had no effort been spent here in making it inherently somewhat hard to solve.
  17. Claytus

    Claytus Well-Known Member

    Isn't "delaying the solution" relative to the size of your audience, though? Like, imagine if the guys who solved the Portal2 ARG, or that protein-folding game that was in the news recently somehow got pointed at Kongai? Not that it would ever happen, but I think a large enough, dedicated enough group could shrink years back down to weeks if they felt like it.

    I agree with you that it can make a game better. But it seems like if the goal is to make a game "great", then a different approach is preferable.
    Kristoph likes this.
  18. garcia1000

    garcia1000 World Champion Staff Member

    Well, one thing is that complexity increases exponentially with the number of moving parts (if game is designed to allow this). So your task isn't as hard as it seems. Just adding one factor could increase the complexity by like, 10 times.
    Lofobal likes this.
  19. AppleKing

    AppleKing Member

    I think a distinction ought to be made between whether a game has been / can be solved by a computer, vs whether a human player cares that the computer has solved it.

    To use chess as an example, you could (in theory) make a computer program that always wins at chess. All you have to do is run a min/max ai long enough to cover every possible game, from the first move to the last. Unless there happens to be some specific path a player can take that will always leave an opening for them to still win, no matter what their opponent does, that computer would be guaranteed to win every game. Granted, unless it's a super computer it will probably take about a day to make a move, but that is not the point.

    I believe this is the sort of scenario we refer to as the game being solved. The thing is, just because some super computer has solved a game, doesn't mean that there's even one single human being who has the mental capacity and patience necessary to memorize that solution. So, unless there happens to be one specific path to guaranteed victory no matter your opponents moves, or the solution can be condensed into a relatively small set of simple(ish) rules, odds are it won't come up very often, if ever, when the people playing the game are all human.

    Tic-Tac-Toe is one example of a perfect information game where this is not the case. Not only has it been solved, but the solution is so simple that anyone who cares can probably memorize it within a day, or quite likely an hour or less. Chess, in my opinion, is too complicated for that to be the case. I would also logically extend this to cover anything at least as complicated as chess. With potential exceptions for corner-cases caused by specific mechanical interactions.

    I could be wrong of course. I'm not an expert on any of these topics. I hope I'm not though, as that would present a pretty bleak outlook on the future of perfect information games. Not that I've ever been a huge fan of those, but I would consider losing the validity of an entire broad game type to be a loss for gaming as a whole.
    Leartes and rozencrantz like this.
  20. Logo

    Logo Well-Known Member

    It's about what you're trying to improve. When you play SF, among the execution, you are improving your ability to read the RNG flaws and tendencies in your opponent. Each opponent is unique and a different situation and you can't be a good RNG generator yourself no matter how hard you try. In Chess your opponent is irrelevant because you can always win by making purely optimal moves (if your opponent makes 0 mistakes then it's whatever the result of the game is and you can't change that).

    For me (and others?) just that mere fact, even if it's unobtainable, changes the joy in learning that type of thing. I feel like I'm not learning or improving some skill, but rather just memorizing game states (and admittedly some kinda cool stuff behind that about how to optimizing remembering game states).
  21. rozencrantz

    rozencrantz Active Member

    I think that people often under-estimate the complexity of abstract games, especially ones on or past the edge of computer domination, like Chess. These games are large enough that even people who have dedicated their lives to studying just one game can have style. Situations in chess can be described by a great many factors, and even in the upper echelons people will be more familiar or comfortable with situations that can be grouped together by some category, and less familiar with situations that fall under some other category. This is even true in extremely well-understood, highly mathematical games like Sprouts.

    This is why some grandmasters are noted for particularly sharp play, while others favor closed games. That is a fairly un-subtle manifestation of the phenomenon, but much of the strategy in abstract games revolves not around finding an optimal move so much as pushing the game into a state that your opponent is less familiar with, and does not understand as well as you do. Just like you cannot be a good RNG, you also cannot be a good alpha-beta searcher, no matter how hard you try. The existence of an optimal move is a theoretical curiosity, nothing more.

    I should be clear that this is a property of great games, and there are many abstracts that just come down to being better at searching, or knowing more positions than your opponent. I believe that it is not actually particularly difficult to make a great game, if you know what you are doing and have good testers who also know what they are doing. The economics of abstract games is more of a hurdle than the actual design problems in creating a deep game.
    zem, snarles and Saturday Saint like this.
  22. CCGer

    CCGer Active Member

    I remember you saying something about RPS games being solve by mathematics. However, you also pointed out that players are usually bad at doing things at specific percentages. So can we say that there are perhaps two types of game solutions, the good one (doing things at a specific percentage) and the bad one (like in tic-tac-toe)? I think we should be able to see the diffrence in the effects of a game being solved.
  23. Sirlin

    Sirlin Steward of the Realm Staff Member

    They are not really good and bad solutions. They are pure or mixed solutions. That players might be bad at implementing a mixed solution is some side issue. Just like how a human might be bad at memorizing the entire optimal algorithm to play chess. Either way, simply knowing that it's solved and that your "strategy" is really just you being bad at looking up some pre-determined thing is demoralizing.

    That said, it's generally better to have your game be solvable with a mixed strategy than with a pure one I think, if you have to choose. At least it looks more like a game with a mixed solution, can take longer to figure out too (kongai).
  24. CCGer

    CCGer Active Member

    I find the distinction of "perfect information" and "complete information" quite amusing. However, I still have some confusion with these two phrases.

    You said that all complete information games are solvable, so since Yomi card game is a game with complete information, does it mean that it is solvable? How about games like Stratego?

    And where does hidden information comes in?

    Your post actually sounds like most board games (turn-based) are solvable.
  25. Acosta

    Acosta Member

    He said that all games of perfect information are solvable, not complete information.
  26. Leartes

    Leartes Well-Known Member

    As far as I understand without randomness and with perfect information there is (possibly hard to find) optimal pure strategy. With randomness or imperfect information you get an optimal mixed strategy. I can't really remember if there are classes of games with no mixed nash-equilibrium - perhaps infinite games but this gets very theoretical. Therefore I think mathematically all relevant games at least have that.
    Keep in mind that nash-equilibria are not always perfect as you don't play your opponent, but assuming a perfect opponent you will play an equilibrium.
    Now my point is, I doubt randomness can prevent solvability at all. It can force mixed strategies and it can make it harder to find an optimal strategy but it can't prevent it entirely.

    Now if you want to only consider practical solvability then you don't really need randomness either as there are plenty of games that proof that a large enough gamespace suffices. Therefore I'd only include random elements if you like the gameplay properties it causes. (Possible properties are a reduced emphasis on searching the game tree, necessity to juggle probabilities)

    This sounds very interesting - and hard to achieve. In a game with diverse gamestates and decisions you need tons of moves to get a detailed picture of your opponents valuation, especially if your opponent is trying to hide it behind a mixed strategy. You could take a look at heads-up poker, it is a very simple game and ridiculously hard to play optimal.
    Obviously it has hidden information making it harder to figure out your opponent. On the other hand your game has to be much more complex to allow a large variety of valuations while being a perfect information game.
  27. dzebra

    dzebra Active Member

    Let's say, for instance, that Chess is a solved game. In this solution, we find that White always wins when the perfect game is played. White goes first, making the first move in the optimal solution. Black then goes, but since he knows he will lose if he plays the "optimal" game, he plays a suboptimal move. Now the game is not the "solved" version of the game.

    The reason Tic-Tac-Toe is so easily solved is that there are few enough options that I can account for every option with every move I make, and moves very quickly become forced.

    Because of how many turns it takes to start forcing moves on your opponent in Chess, the only way to play a perfect game is the be able to find the best move every turn. If you can't force your opponent's move next turn, then you have to be able to account for every possible action he is capable of doing.

    And to calculate the best possible move, I reckon you'd have to take into account how many moves that opens up for you in the future, how many moves this allows your opponent, how much material gain you'd get, etc. Many of these things don't have specific values, especially considering that your calculations must include some amount of probability of what your opponent will do next.

    Every solved game of Tic-Tac-Toe is the same game, but rotated 90 or 180 degrees. This cannot be the case with a game like Chess, because moves do not become forced as quickly. For Chess to be solved, there must be a move each turn that is strictly better than all other moves. That is not the case due to what I mentioned in the previous paragraphs.
  28. Leartes

    Leartes Well-Known Member

    A game is solved when for every deviation that black makes there is a known moveorder that gives white the same or a better result.

    If for example it is known that white wins in a perfect game, then the solution might consist of the path through the gametree that gives white the latest possible win (most moves required). Then every deviation by black leads to an earlier loss by black.

    Therefore if it is solved, than it is solved in all subgames as well. Someone already mentioned it is highly unlikely that this will be possible anytime in the forseeable future and even if it is possible no human can memorize this solution.
  29. Aesa

    Aesa Well-Known Member

    Yea as Leartes said the only difference between Tic-Tac-Toe and Chess is the complexity (I mean that's a big difference but yea). Regarding "For Chess to be solved, there must be a move each turn that is strictly better than all other moves.", note that you can easily tell this is false simply by looking at Tic-Tac-Toe which is solved and the latter is not the case.
  30. dzebra

    dzebra Active Member

    Yeah, I talked it out over lunch, and I think that perfect information games are inherently solvable. It's weird for me because I tend to think along the lines of games that in this thread are being referred to as "complete information" games.
  31. Claytus

    Claytus Well-Known Member

    Hahahahahahaha. Yeah, we're done here. Do some frickin' research:
    http://en.wikipedia.org/wiki/Solving_chess
    And that article is just working with some pretty conservative viewpoints. Good estimates place it much sooner.
  32. Leartes

    Leartes Well-Known Member

    How "good" are good estimates? And 50 years ago they were sure that by now we'd long be running on fusion power.

    Also I highly doubt computational power will increase exponentially for two hundred and forty years.

    Just try to estimate the computational power you'd have by then. It'd be possible to count from 1 to the number of atoms in the universe by then ...
    So I don't think there will be a brute force solution unless P=NP. There might be a more sophisticated proof but not via computational power.
  33. rozencrantz

    rozencrantz Active Member

    I think most important is having many sub-goals that are mutually weakly opposed -- increasing your strength in one should come at the cost of being weaker in the others, but not to the exclusion of the others. One easy way of getting this is by making actions have a strong local effect and a weaker non-local effect. Influence in Go is an example of this, a move has more effect on the game right where it is made, and that influence tapers off as you move farther from the stone. Othello is an example of what not to do, moves effect too much of the board too strongly.

    "Recycling" is another way of getting this kind of tapering effect, but temporally instead of spatially. If spaces are occupied and then vacated repeatedly, then short-term gains are fleeting, so focusing on the long-term effects is more important. Those long-term effects are harder to valuate, so there tends to be more variation in how people address them.

    With recycling though, you need some guarantee the game will end. The easiest way to do that is to have some fundamental variable in the game that either only increases (to some limit) or only decreases. In Othello this is the number of pieces on the board, but many games (notably most of Mark Steere's games) have a nested set of these. In Hex Oust, the number of groups of stones increases every turn, and can only decrease if the size of the largest group increases. Some games have even more complicated ratchet factors.

    There are other mathematical properties that are nice: high branching factor (>30) and long average game length (again >30) both increase the absolute size of the game tree, which is likely to increase the size of the relevant game-tree as well. Game temperature is very important and currently not well understood; you generally want to strike a balance between "hot" positions (where you would rather make a random move than pass) and "cold" positions (where you would rather pass than make the best move available to you). Some games like Go, Hex, and Connect6 manage very well even though they are completely hot, but they need some artificial mechanism for balance (komi, a swap option, or a restricted first move)

    The game has to give the players more information than they can process, and it has to give players the means for taking short-cuts in processing the information, and those short-cuts must be imperfect. Branching factor, length, and temperature are all good indicators that the game will likely have this property, but only thorough testing can say for sure.

    The abstract game design community is small, and there are still a lot of open questions that we are working on, but there is right now an effort to make abstract game design more scientific and controlled.
    Saturday Saint and Leartes like this.
  34. Leartes

    Leartes Well-Known Member

    Thanks rozencrantz for the insightful post.

    The notion of hot and cold gamestates is new to me. I always thought positions you define as cold are bad, boring and lead to stalemates. Never thought of using them to remove the first move advantage.

    Also I think what you call high branching can be too much. I know many games have a branching beyond 30 move-options, but usually a large amount of those options is clearly not good. I think it wouldn't be a problem to have a game with a larger fraction of interesting moves. Like a game with 10-20 move-options where 50-90% are non-trivial. Not sure if you should aim for this property during design but you should definitely count the number of interesting branching moves. I mean high branching destroys naiv computer play but that is bad approach to solving the game anyway.
  35. rozencrantz

    rozencrantz Active Member

    That is true, but it's extremely hard to control. There are necessarily no more viable paths than there are total paths, so increasing the number of branches tends (in a rough statistical sense) to increase the number of interesting paths. These games are so unpredictable that you have to take a shotgun approach much of the time.
  36. Claytus

    Claytus Well-Known Member

    Yeah, that was basically my point. The most powerful Chess software available today (the stuff since deep blue... deep fritz is one, I don't know if there's something even more recent?) doesn't rely on brute-force methods. The amount of processing power described in that link isn't necessary, if you have enough advantages in the effectiveness of the software to trim the move tree way down in the first place, which is effectively what's happening.

    If you are generally interested in the topic, I highly, highly recommend this book:
    http://en.wikipedia.org/wiki/The_Singularity_Is_Near

    He spends quite a while in the beginning sections explaining both the current state of chess-playing computers, and why solving the game is inevitable (and the rest of the book is super interesting, too). I could probably not scratch the surface in a forum post.

    For the record, history shows that would be one of the worst bets you could possibly make... (A topic also covered in detail in the book above)
  37. deluks917

    deluks917 Yomi League 1 Champion

    Chess is almost certainly a draw imo. One problem with chess is that even if one player plays a little better then the opponent the game can still be a draw. So if Chess is solved as a draw the game really might just be over as far as top level play goes. I think chess is clearly on its deathbed, look at the percentage of gm draws.
    snarles likes this.
  38. rabid_schnauzer

    rabid_schnauzer Well-Known Member

    There may be an exception for games which are infinitely scaleable, such as Go. Go on a 19 by 19 board is solvable (but not with today's computers), but provable much more computationally difficult to solve than Go on a 13 by 13 board. And while for any given N by N Go board, the game will be solvable, those may (or may not) be different solutions for each board size so there may not exist a generalized solution for Go played on an arbitrarily large board.
  39. rozencrantz

    rozencrantz Active Member

    This is a thing, it's called Zermelo's theorem: Any finite game is theoretically solvable. For any given N, the game tree may be astronomical (as it is with n=19) but it is still finite (this is not strictly true, because there are infinite variants of Go, but they are not relevant. PM me if you want to know way too much about finiteness as it pertains to Go and the solvability of Go)

    On a practical level though none of this matters, because even with today's technology we have game solutions outside the bounds of human comprehension. Chess is orders of magnitude more complex than those, and Go is orders of magnitude more complex than Chess.
  40. Leartes

    Leartes Well-Known Member

    To back up my knowledge I currently only have wikipedia at hand http://en.wikipedia.org/wiki/Computational_power#Ultimate_limits_of_the_law and the following paragraphs. Also there is currently research going on in direction of atom-scale transistors with some recent results in january this year (not included in the wiki article yet).

    Additionally to the limitations of current technology which will end moores law in a few years if no other technology is developed in time, there is also the exponential increase in research cost and the dropping efficiency in massively distributed computing. For many problems there is a multiplicative gap between the necessary amount of operations on a single core system to a multi-threaded system. This is due to the increased amount of required operations for communicating partial problems and solutions inside the system. Finally for many problems there is a bound on the number of cores that give a increased performance, therefore even a hypothetical processor with an infinite amount of cores (and therefore infinite parallel operations) still has pretty hard bounds on the runtime of many problems.

    Now I do believe there might be a faster technology out there but I doubt it will come soon and I believe the increase in development cost will persist. Leading to a singularity with infinite cost in labour and $$.

    In conclusion I do think Kurzweil is wrong. His work is certainly interesting but very optimistic in my eyes.
    Anyway I'm fine with you agreeing with him, just keep in mind that he is just one among many experts with vastly different opinions on the matter. (And no I'm no expert :D)

    The only technology I can imagine that breaks all assumptions is one that allows for real valued bits. If something like that is ever developed it would crush most of the current theories of computer science.

    Chess is just another optimization problem with exponential runtime. For many NP-complete optimization problems it is possible to show lower bounds on the runtime therefore I foresee a lower bound on the constant factor in the runtime of solving chess. Obviously the notion of runtime is strange since the input size is fixed still I think there are limits to how good your pruning can become because there are limits in many much easier problems as well.

    Thanks again, another interesting read. I agree on practical levels it is not relevant today and unless the solution is easy enough for a human to understand there is no problem in playing a solved game anyway.

    Also I doubt a game becomes better just because you scale it to a size where computers can't solve it. I watched some 39x39 go games on kgs. They take many hours and most of the time local results don't matter much. Certainly nothing I'd want to play on a regular basis.
  41. suiraclaw

    suiraclaw Member

    http://en.wikipedia.org/wiki/Arimaa

    As much as I'd love to find a better source than wikipedia, the Arimaa article is actually excellent and contains a huge section on the computationality of the game and the difficulties an AI would have to solve this game.

    Anyway, the game is made by an AI programmer who wanted to "design a new game which could be played with a standard chess set, would be difficult for computers to play well, but would have rules simple enough for his then four-year-old son Aamir to understand." As such, it uses quite a few techniques to discourage brute force and delay solvability, the most important one probably being a very high branching factor (http://arimaa.janzert.com/bf_study/). Obviously, it does not claim to be unsolveable, but it does succeed in making it impossible to solve within current hardware constraints.

    As such, even games on a small board can be insanely difficult to brute force.

    PS: according to the arimma wikipedia article: "Top chess programs use brute-force searching coupled with static position evaluation dominated by material considerations. Chess programs examine many, many possible moves, but they are not good (compared to humans) at determining who is winning at the end of a series of moves unless one side has more pieces than the other." Sadly, no reference is given.
  42. rozencrantz

    rozencrantz Active Member

    That chess quote is fairly out-of-date; positional evaluation has gotten a lot better, especially in programs like Rybka. They don't use brute-force searching, they use alpha-beta searching: they use the positional eval algorithm to eliminate less promising branches of the game-tree, search smarter not harder. Top chess programs all evaluate about the same number of nodes/second, the best programs examine the best nodes (or the fewest bad nodes). It is true that some things are easier to evaluate than others, and material is one of the easiest, but they are much more sophisticated than that.
  43. Leartes

    Leartes Well-Known Member

    The thing with solving a game is, valuation heuristics and alpha-beta pruning is not enough. You can never be sure you really got the optimal play, you only know you got the optimal play for the heuristic used. And every heuristic is limited.
    To apply alpha-beta pruning in a program that not only plays really well but solves the game, you need to prove for your valuation heuristic that it strictly increases the chance to win for every possible gamestate. Which is a pretty hard thing to do ... Even proving that your program is actually close to optimal play is hard since you can't really analyse how close your valuation is to the optimal valuation. The only thing you can do is do experiments and play versus other ai or strong human players and find out how strong you are in relation to them. Solving is something entirely different.
  44. Claytus

    Claytus Well-Known Member

    Once again, let me just point out that people have predicted that every year for 30 years now and been wrong. So, again... very, very bad bet to make.

    That said, you're overlooking a couple important points:

    a) You really shouldn't be making statements about whether you believe Kurzweil is wrong or not without knowing what he said. He argues in favor of this concept (which is not the same as Moore's Law, and too often gets confused with it):
    http://en.wikipedia.org/wiki/Accelerating_change

    b) I wasn't actually referring to Moore's Law either, because there's much bigger stuff going on. What I mean, is that currently the massive advancements in computing are being made in hard drive space, and bus speeds. The standard example being Solid State Drives, and how awesome they are, and how widely available/affordable they're becoming. Processor speeds have stopped going up because it didn't matter... it ceased to be a bottleneck.

    c) Quantum Computing (and the competing crazy ideas that I don't even remember the names of). I mean, it doesn't exist yet. But all the research out there seems to indicate it's possible, and could happen sooner than one might expect. If they do manage to create it, it will totally change the game.
  45. Leartes

    Leartes Well-Known Member

    Then let me frame it different. I think these theories are nothing more. They are on the same level as me saying there will be a thunderstorm in 364 days from now in London. Now I could start make some charts that look nice and support that possibility and you could believe me or not. I am 100% sure there will be no singularity in 2045. It is just ridiculous.
    Have you ever worked in a scientific environment? Technological progress needs time to be understood and more time to be tested. Computer science will not suddenly evolve much more rapidly as it does now. Perhaps it will broaden up more so that there are more fields of study but in no single branch will be much more improvement as there is now apart from the rare random breakthrough.

    Kurzweil argues around that barrier of human understanding with:
    It is a nice (or not so nice) dream but not more believable than the cold fusion wonder. Even normal fusion power was said to become the norm already decades ago. We know how that went so far ...
    I'm not saying machine intelligence will not evolve. It is not difficult to evolve since at the moment it is none existent. All we can do with computers at the moment is define a course of action we are to lazy to calculate by hand and input it into a machine that does all the boring steps for us. Even neural networks are not beyond that level yet. Not sure how you come from 0 machine intelligence to some breakthrough in 2045 since exponential grows from 0 remains 0.

    Also stuff like

    Sounds nice but is highly not scientific. I can't give something like that much credibility sorry.

    He could stay on the safe side and claim "someday a singularity might occur" due to some reasons but this timeframes ...

    Anyway if you want to continue discussion on this matter maybe open a new thread in the General Discussion section, it is highly offtopic in this thread :D
  46. rozencrantz

    rozencrantz Active Member

    This is a point I'm not entirely clear on: would quantum computing do a complete end-run around P/NP, or would it just vastly reduce the root of the exponent?
  47. Leartes

    Leartes Well-Known Member

    As far as I understand quantum computing there is an exponential improvement in the number of qbits used.

    It is quite some time since I did complexity theory in regard to quantum computing. Wiki states some weird properties indicating that there might be more than polynomial speedup for some hard problems but not for all. This contradicts with the general notion of the class NP-C. I'll have to read up on this :)
  48. Claytus

    Claytus Well-Known Member

    http://en.wikipedia.org/wiki/Quantum_computer

    Specifically:
    The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time".

    BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known.

    There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.
  49. Claytus

    Claytus Well-Known Member

    *oops, double post, sorry... I meant to combine these*

    Actually, this isn't what Kurzweil is saying. Again, read his book... this is not a simple topic that can be discussed on a forum. The short version is that his main argument is that basically every branch of science is way more advanced than the public realizes *right now*. And even most scientists aren't aware of that fact, because people studying in different disciplines aren't talking to each other.

    So... what do you call the navigation system in your car? What do you call a chess-playing computer? What do you call Wolfram Alpha???

    This is the big problem discussing this issue. Machine Intelligence is all around us, we are literally steeped in it. And yet, there's this public perception that real "intelligence" is some magical word for a concept that doesn't truly exist yet.

    It's done, we did it, a while ago, get with the program. All these predictions being made are just saying that this stuff we have right now is going to continue to get better.
  50. Leartes

    Leartes Well-Known Member

    I can totally agree with that. It is just no singularity. There are so many theories out there that reject any form of singularity that I can't give much credit to a person that states a singularity will occur in 33 years from now. It is like claiming doomsday will occur in 28 years or something.

    On intelligence in my book neither chess computer nor wolfram alpha are intelligent. They are manifestations of logical reasoning but they lack everything else required. Someday there might be some artificial mind with true intelligence and then it'll take a lot more time until it becomes as intelligent as humans are.
    Anyway this is a different discussion. Just remember that logic can only get you so far in science. Many aspects of human life are not entirely logical and so are many aspects of science. Therefore I believe the machines you call intelligent are not capable of understanding human behaviour and before they are able to do that they can't be more than helpers for their human masters.

    Now we could make a bet about this singularity thing but I doubt we'd resolve it in 30+ years :D
    Maybe I'd even lose that bet. It is just a theory, there is some probability that it comes true ...

    What is much more interesting for now is the question what happens to moores law in the next decade. Also I'm interested in the limitations of parallel progamms. And I'm eager to see who does the exponential growing work and who pays the exponential growing cost to fuel the advancement. Because there are big obstacles that have to be overcome long before we can experience any singularity.

Share This Page