Posts tagged ‘connected components’
I’ve been working off and on to find the optimal strategy for the final round of a game of liar’s poker. I’ve gotten a bit farther on it, and it now looks solveable. I’ve now solved the 12-card deck version (i.e. if the deck only contains aces, kings, and queens), and I suspect I’ve got an algorithm that will solve the whole problem in a reasonable amount of time.
I recently wrote about a card game called Liar’s Poker and my endeavours to find an optimal strategy for the final round. Some extra progress has been made, but it’s still a long ways off. Despite what I wrote when I edited my previous post, I’m no longer convinced that we can adapt Simplex or a gradient descent algorithm to solve this. It turns out that although the gradient function is piecewise linear, there are an exponential number of different linear regions in it, and I’m not convinced we can do something like Simplex without enumerating them all. but here’s some other stuff Reid and I have done on the problem: