Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Solving problems by mapping to other problems that we know how to solve

news.ycombinator.com

Post reply on HN
Print view View original

71–80 of 81 posts

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#71

Post by monkeyjoe »

hmate9 wrote: post #67

My favourite example of this is how no limit Texas holdem was solved. This game is of course an imperfect information game (you don’t know your opponents hole cards). We have lots of great algos for perfect information games but not imperfect. So what the researches did is they mapped hold em to a perfect information game by tweaking it: now nobody knows their hole cards and all players must publicly announce their s…

Got a reference for this?

My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information.

The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iteration.

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#72

Post by time_to_smile »

Someone wrote: post #35

That’s called Mathematics. For example, most NP-complete problems we know of were proven to be NP-complete by showing them to be no easier than some other problems we know to be NP-complete. https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr... : “The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it” As a se…

To add to this, another mathematical term to be familiar with is "isomorphism". It quite literally means showing that two structures are the same, and perserve the same binary relations (coming from modern Algebra).

If you can show that domain A is isomorphic to domain B, then all of the things you know how to do for domain A can be trivially applied to domain B. Thinking about solving problems in terms of isomorphisms has been tremendously helpful for my day-to-day problem solving.

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#73

Post by aral12 »

personjerry wrote: post #70

This is an even more interesting question on a broader definition - OP and a lot of the answers refer to math, which is understandable given most of our backgrounds, but I've always wondered what about complex, inter-domain problem solving? How do we map programming to understanding genetic codes? How do we map psychological research or zoological data to operations research?

One thing that has been worked, at least with genetic codes, is mapping them to linguistics (or rather to text), although it could be argued that the scaffolding of this mapping is still mathematical. I guess in this case the analogy was already there, waiting to be leveraged. Mode info: https://deepmind.com/blog/article/enformer

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#74

Post by personjerry »

aral12 wrote: post #73
personjerry wrote: post #70

This is an even more interesting question on a broader definition - OP and a lot of the answers refer to math, which is understandable given most of our backgrounds, but I've always wondered what about complex, inter-domain problem solving? How do we map programming to understanding genetic codes? How do we map psychological research or zoological data to operations research?

One thing that has been worked, at least with genetic codes, is mapping them to linguistics (or rather to text), although it could be argued that the scaffolding of this mapping is still mathematical. I guess in this case the analogy was already there, waiting to be leveraged. Mode info: https://deepmind.com/blog/article/enformer

But we need the people with feet in both doors to make the connections necessary to figure out what mappings can be used, and that seems nontrivial

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#75

Post by hmate9 »

monkeyjoe wrote: post #71
hmate9 wrote: post #67

My favourite example of this is how no limit Texas holdem was solved. This game is of course an imperfect information game (you don’t know your opponents hole cards). We have lots of great algos for perfect information games but not imperfect. So what the researches did is they mapped hold em to a perfect information game by tweaking it: now nobody knows their hole cards and all players must publicly announce their s…

Got a reference for this? My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information. The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iterat…

Everything you said about Nash equilibrium is true, I didn't mean to imply that it can only be found in perfect information games via iteration.

What I wanted to say is that methods for finding it via iteration and self-play exist and are well defined but only for perfect information games.

The research itself is here: https://ai.facebook.com/blog/rebel-a-general-game-playing-ai...

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#76

Post by telxosser »

personjerry wrote: post #70

This is an even more interesting question on a broader definition - OP and a lot of the answers refer to math, which is understandable given most of our backgrounds, but I've always wondered what about complex, inter-domain problem solving? How do we map programming to understanding genetic codes? How do we map psychological research or zoological data to operations research?

I have been super into the book Introduction to the Theory of Complex Systems by Thurner, Hanel, Klimek.

I thought the whole field of Complex Systems was kind of bullshit before this book. IMO we just don't know that much in this area in 2022.

It is just too new and different. I thought it was about fractals or some nonsense before reading this book.

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#77

Post by telxosser »

monkeyjoe wrote: post #71
hmate9 wrote: post #67

My favourite example of this is how no limit Texas holdem was solved. This game is of course an imperfect information game (you don’t know your opponents hole cards). We have lots of great algos for perfect information games but not imperfect. So what the researches did is they mapped hold em to a perfect information game by tweaking it: now nobody knows their hole cards and all players must publicly announce their s…

Got a reference for this? My understanding is Nash equilibrium exists in any game with finite states, regardless of perfect or imperfect information. The bit about announcing your strategy holds by definition - the equilibrium is defined such that no player can improve, thus it doesn't matter if the other player's strategy is known. Also, I don't think there's a requirement that Nash strategies be reachable by iterat…

I believe you could say the minimax strategy to the 2 player game of heads up no limit is solved but beyond that is stretching it.

I am way out of it though. I suspect anything more than 2 players is unsolvable when you factor in the stochastic nature of the drunk guy at the table with more than 2 players. Then based on his play he subtracts or adds EV to us randomly.

I won't even let myself think past this though with poker because IMO it is a waste of time.

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#78

Post by belter »

Someone wrote: post #56
Someone wrote: post #35

That’s called Mathematics. For example, most NP-complete problems we know of were proven to be NP-complete by showing them to be no easier than some other problems we know to be NP-complete. https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr... : “The easiest way to prove that some new problem is NP-complete is first to prove that it is in NP, and then to reduce some known NP-complete problem to it” As a se…

Reply to self: of course, the prime example is counting. If you have five breads, you can sell three, and have two breads left after that. Similarly, If you have five apples, you can sell three, and have two apples left after that. You didn’t have to learn separate addition tables for breads, apples, etc. Instead you learned that all such problems essentially are the same, and you learned how to manipulate the equiva…

I don't think your examples are examples of solving a different problem.

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#79

Post by chana_masala »

smartmic wrote: post #34

Your question immediately made me think of G. Polya's classic book (and research) from 1945 "How to solve it", which devotes a large part to the question "Here is a problem related to yours and solved before. Could you use it?" A small excerpt: "… We have to look around for closely related problems; we look at the unknown, or we look for a formerly solved problem which is linked to our present one by Generalization,…

Yes, that's what it made me think of as well. Recently an audible version of the book was released and it's actually pretty well done for a math book

Re: Ask HN: Solving problems by mapping to other problems that we know how to solve

#80

Post by sirwhinesalot »

mzl wrote: post #49
sirwhinesalot wrote: post #47

Everyone already mentioned mathematics but I'd also like to mention Operations Research as a field that's basically all about translating complex business problems into mathematical models that can be efficiently solved. In practice this almost always means translating to the formats used by (Mixed) Integer Programming (MIP) solvers, Constraint Programming (CP) solvers or SAT solvers. Satisfiability Modulo Theories (…

And similarly relevant, using a solver independent modelling language like [MiniZinc]( https://www.minizinc.org/ ) means that it is possible to write a model, and then translate it formats suitable for use with MIP, CP, and SAT solvers.

Yes MiniZinc is excellent.
Post reply on HN