If it were possible to list the animals allowed in the game, the. It is certainly possible “in theory” to craft ideal questions: “does its name come before [halfway point] in alphabetical order?” Of course my son would probably rule that question out of bounds, making it impossible “in practice”.
I was thinking more about characteristic-based questions that are more in keeping with the game. But you’re right - as someone else has noted above, could just name the literal breakpoint in the list.
Guess Who is a special case of 20 questions where each outcome is equally likely and you generally can split the candidate set in two by a certain feature at any point in the game. Good way to see the general principle
There are a couple subtleties here. You mention that partitioning your solution space in half may not be possible in theory, but if you have no restrictions on the nature of the questions, there is a trivial – albeit practically infeasible – way to do so: just take half of your subset and say “is it one of a giraffe, lion, zebra, …” until you’ve enumerated everything in the subset. It’s not completely clear to me what reasonable restrictions you can place on questions to avoid this, but perhaps banning disjunction outright is fine.
Assuming you have some restrictions on your questions, now you have to be careful about how you measure information gain. If you just select greedily (ie based on highest information gain at the current step), you may run into situations where you have seemingly partitioned your space well, but 3 questions down the road you realize that you have some pathological edge case of four remaining options and no way to construct any questions better than knocking them off one by one, which ends up being very inefficient. This is the same issue that 3Blue1Brown ran into when solving wordle using expected information gain, incorrectly concluding that CRANE is the best opening word.
I am fairly sure that if you do not have any restrictions on your questions then the greedy EIG solution is optimal, but I’m not sure.
That's a fair point. I also wondered if there was a 'hangman' type strategy that would allow the partioning to be achieved with word lengths and other numerical characteristics – but again, not exactly a fun way to play the game...
I'd hope your very first consideration would be having fun, then deepening your bond?
In addition to your line of thought above, it would be perfectly admissable to use this game to gradually extend his vocabulary & understanding of a wider range of animals, grouping and sorting by categories such as colour/wild or farmed/carnivore or herbivore/size and so much other everyday learning which might be appropriate for a small child - you don't say how old. Can't believe your 'story' is so abstract...
If it were possible to list the animals allowed in the game, the. It is certainly possible “in theory” to craft ideal questions: “does its name come before [halfway point] in alphabetical order?” Of course my son would probably rule that question out of bounds, making it impossible “in practice”.
I was thinking more about characteristic-based questions that are more in keeping with the game. But you’re right - as someone else has noted above, could just name the literal breakpoint in the list.
Guess Who is a special case of 20 questions where each outcome is equally likely and you generally can split the candidate set in two by a certain feature at any point in the game. Good way to see the general principle
Ha! I have also moved from playing zero games of 20 questions in 30 years to a weekly occurrence.
There are a couple subtleties here. You mention that partitioning your solution space in half may not be possible in theory, but if you have no restrictions on the nature of the questions, there is a trivial – albeit practically infeasible – way to do so: just take half of your subset and say “is it one of a giraffe, lion, zebra, …” until you’ve enumerated everything in the subset. It’s not completely clear to me what reasonable restrictions you can place on questions to avoid this, but perhaps banning disjunction outright is fine.
Assuming you have some restrictions on your questions, now you have to be careful about how you measure information gain. If you just select greedily (ie based on highest information gain at the current step), you may run into situations where you have seemingly partitioned your space well, but 3 questions down the road you realize that you have some pathological edge case of four remaining options and no way to construct any questions better than knocking them off one by one, which ends up being very inefficient. This is the same issue that 3Blue1Brown ran into when solving wordle using expected information gain, incorrectly concluding that CRANE is the best opening word.
I am fairly sure that if you do not have any restrictions on your questions then the greedy EIG solution is optimal, but I’m not sure.
That's a fair point. I also wondered if there was a 'hangman' type strategy that would allow the partioning to be achieved with word lengths and other numerical characteristics – but again, not exactly a fun way to play the game...
I'd hope your very first consideration would be having fun, then deepening your bond?
In addition to your line of thought above, it would be perfectly admissable to use this game to gradually extend his vocabulary & understanding of a wider range of animals, grouping and sorting by categories such as colour/wild or farmed/carnivore or herbivore/size and so much other everyday learning which might be appropriate for a small child - you don't say how old. Can't believe your 'story' is so abstract...
Of course! That’s why the mathematical pondering is being posted on substack and the things you mention are happening in real life…