Timeline for Is the game Hanabi NEXPTIME-complete?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 22, 2017 at 13:21 | vote | accept | Dylan Thurston | ||
| Feb 15, 2017 at 11:30 | answer | added | Jonas Kölker | timeline score: 4 | |
| Nov 13, 2015 at 3:39 | comment | added | domotorp | Of course, but you do the calculation for each player, for each possible set of hands, and take the expected value. Also, to understand this and that there are no conventions, it's best to think over first the last move, then the last but one move etc. | |
| Nov 12, 2015 at 23:07 | comment | added | user5810 | @domotorp : $\:$ "the best option" will also depend on what the other player does. $\;\;\;\;$ | |
| Nov 12, 2015 at 23:04 | comment | added | domotorp | @Ricky: You pick your best option. | |
| Nov 12, 2015 at 22:28 | comment | added | user5810 | @domotorp : $\:$ "going through all combinations in a brute force search and computing probabilities $\hspace{.51 in}$ in PSPACE" and then doing what with those probabilities? $\;\;\;\;$ | |
| Nov 3, 2015 at 22:32 | comment | added | domotorp | Do not try to search over all possible conventions. That's impossible. Instead only try to realize the truth:There are no conventions. If powerful Turing-machines play, then they can just use THE ("lexicographically first") best convention. | |
| Nov 3, 2015 at 19:18 | comment | added | Dylan Thurston | dmotorp, you're omitting the search over all possible systems of conventions. | |
| Nov 3, 2015 at 1:01 | comment | added | domotorp | Position = own cards in hand + complete history of what happened in the game so far. Then you can make the brute force search over the possibilities of what's in the hands of the others, imo. | |
| Nov 2, 2015 at 12:43 | comment | added | Dylan Thurston | Thanks for the cstheory suggestion, I didn't think of that. The reason it's not obviously in PSPACE is that in addition to the state of the cards, you also need to model the state of knowledge of what the other players know, and there's no obvious bound on that. Note the "undecidable" entry in the table I posted. | |
| Nov 1, 2015 at 21:27 | comment | added | domotorp | I think this question would be more suitable for cstheory.stackexchange.com. I also think that from any position any player can calculate the optimal move by going through all combinations in a brute force search and computing probabilities in PSPACE. | |
| Oct 28, 2015 at 2:34 | comment | added | Dylan Thurston | Lots of upvotes here, but no answers or discussion! Does anyone know any related work? | |
| Oct 23, 2015 at 20:26 | history | asked | Dylan Thurston | CC BY-SA 3.0 |