HeXO is NP-Hard

[00:00:03]Okay. Uh, okay. Welcome to my presentation. Today we're going to talk about why Hexo is NPR. I'm going to talk about later what exactly this means. So, first of all, uh the rules of Hexo. If you don't already know the Hexo is a game uh a two-player game edated by web code guy, which is also on this uh discord server, so you should probably know him. You can find him on YouTube.

[00:00:26]Anyways, it's a strategy game on an infinite hexag hexagonal board. Uh, in each turn, a player places two color access. So, what this means is that, of course, it's a infinite uh hex chess board and on the first turn, the first player places one stone and then after that, each player places two stones. So, for example, I've uh set up that player one is a color yellow and player two is blue. So, this is a pretty good strategy game. Whoa. It's a pretty good strategy game. And the the the objective of this game is to make six in a row. So, for example, in this position, yellow can if he makes six in a row, he wins. So of course uh player player two has to avoid this. So for example this is a position um and this this is considered a threat in my in my program I have this showing basically. So blue has to block this threat in order to not lose the game.

[00:01:36]Okay. So we will show MP hardness by simulating SAT or reducing the program to SAT SAT. Uh so uh a a such problem is basically this kind of problem. It's a string uh of all statements uh all end together. So all of these statements have to be true at the same time. And this is actually an MP complete problem. But I will explain later what this means. Just know it basically is a very hard problem that if we could solve it in polomial time basically we will solve it the majority of problems in also polomial time.

[00:02:13]So yeah, we will need to create uh some logic gate in uh in hexo. The end gate, the or gate and the not gate is difficult to create. Uh but we will create a mechanism so that if a player chooses um for example not a then yes a will automatically be uh false. Okay. So then the MP hard question will be uh for a arbitrary position is this position one for which player?

[00:02:42]Okay. So uh right. So we will trans um transmit signal by making this sort of construction in which yellow makes a double trap which is basically a threat that um the blue player has to respond with two moves. In fact, if player blue has even one uh move available, he wins because there is this uh we will basically put in our this position this uh formation.

[00:03:14]And this obviously a quadruple threat for blue. So if yellow plays perfectly uh he should in every turn make a double threat every move, every turn, sorry. Uh so is a a wire. So basically this is an input and if the input is on then yellow can make a double thread which is blocked by these two blues and yellow can continue making making the the wire gone. Um in theory yellow can also not transmit the signal but it is in like he wants to do it if he wants to win because uh if he doesn't blue just wins right away basically. So yeah, this works by creating five in a rows and if you remember six in a rows make the make player uh one win. So blue has to respond and so we'll defined cheating in this system which is basically um cheating is not supposed to happen of course but cheating is basically when yellow can create a winning opportunity even though it's not supposed to. So I hope there is no cheating in this position basically in this wire. Um but every uh every other move yellow can make is either um transmitting the signal or it just kills off the signal which is a bad thing for him. So this is another Y and I actually corrected this very recently because I didn't realize a cheating error basically. Uh so this is a horizontal wire and this is a another wire which is interesting because it actually uses four in fours in a row it makes two for arrows and this is actually useful because um it basically shifts around the parity of the wire so it will be used and this is another why I never use it uh but it just it's just good to have you know so this is the first gate we've created the end gate as following and this the functioning okay this is not very clear but I will just show you. So first of all this is the wire that the signal passes through and basically this five in a row activates only when both of these signals arrive and therefore I can transmit the signal uh onwards. So I'm going to show you an example. This is our final construction of an example basically. Uh where is I believe this is an end gate. Wait, wait. Whoa.

[00:05:40]Yes. Okay. This is an end gate. So, for example, these are inputs. So, I have Okay.

[00:05:48]So, yellow and blue has to transmit signal is in this way. So, both of these are on like this.

[00:05:57]And whoa, there is a mistake. Okay.

[00:06:00]Maybe I'll just place a yellow here.

[00:06:02]It's fine. And okay. And then so the signal is transmitted and as you can see there's a three arrow now which is only possible if uh both of the signals are on and so the the signal is keep is transmitted. Uh right so I don't think there is cheating in this.

[00:06:22]If there is I can probably fix it I guess. I don't know maybe yes maybe no but it's definitely possible. It's just an an example. If one really tries it could probably be very compact design. I don't know. Uh yeah. So also no there is an important thing that no win condition for yellow can be made because if there is a win condition then uh it it doesn't work. Everything doesn't work. This is an orgate and it's actually very similar uh to our end gate. Um so let me just load up this and find one.

[00:06:58]Yeah, this is our gate. So well how does it work? Basically there is this line this uh green line um and there are two wires which transmit the signal and if any of these two um hexes are filled in then a player can make either four or five in a rows in this green line and then the signal can can transmit. So let's let's see. So wait I have to okay yellow. Okay. So suppose the these are the the inputs because the signal is transmitted. So I put two here and then two here. Uh two here. Yes, two here. So the signal is transmitted in this way.

[00:07:41]And as you can see I put five in a row here. And now this line is already capable of doing four in a row. But actually it's a double thread because there is no blue in this line. Uh so yeah the point is that if we fill in this hack we can continue the signal basically and this works also if there is a signal here or both actually uh yeah so no is possible uh as as at as at least as far as as far as I'm aware or no wind condition is possible.

[00:08:11]Okay uh so this is the knot. Uh so as as I said before the not is not is not actually a possible gate to create because the player could just uh simply never um how do I say it's not possible because in theory a player could be advantaged if a if a wire is off for example uh but a player could just decide not to go ahead and um continue the wire like a player could just stop not not make the the signal go through and therefore a not gate could be created in every position. So we will make a not gate in another way which is basically simply two uh two wires one for a a yes and one for a no basically for the same variable and this is actually a very similar construction to another video I saw on the three cycle uh uh channel but anyway uh so basically how this works is uh a player this is a variable right and a player makes five in a row here and blue blocks offs in these two squares and the signal goes on. But if a player go do does another one of those five in a rows, it creates a threat for blue. And a threat for blue basically mean yellow has to respond.

[00:09:30]And so blue can win instantaneously. So we will look at our example, right? Uh I have okay the moves. Okay.

[00:09:39]So for example, I I decide this is the yes a. So a is on in this wire and so the trans the the signal is transmitted.

[00:09:51]But if yellow decides to make another uh so for example both yes and no at the same time as you can see blue creates a threat and if yellow threat respond it creates a double threat instantaneously and wins. Therefore only one of these two can be on at the same time.

[00:10:10]Uh right and of course no cheating is allowed or at least I hope so. So this is another wire which is not really necessary but I will create it which is a a duplication of the signal. So in complicated SATs it might be needed to duplicate the the the wire the the signal and this is a very easy thing to see if we have a three in arrow here. So this input is on these two are filled in and then we can continue to making five is narrow. I actually don't use it in our final construction uh because it's not necessary every everything is used only once. Uh okay and this is also pretty necessary is just crossing the wires crossing signals without them being uh mixed with one another. And this is actually used in my construction. So this is actually pretty simple because uh it's just symmetrical and the signal one it goes like this uh around this axis basically and this is filled in so they not do not even connect. So the final wire we will be making is more like an end gate and wire. Uh so basically this an end uh yes end gate and this kind of end but basically if they are bought on the player makes a six in a row they makes a triple threat basically yellow and this is very similar to an end gate. So yeah when both signals are turned on uh it creat a row or four in a row actually but they are two fours in a row one is free which basically makes yellow win and again I think there is no cheating or to create win condition a way to create win conditions without both uh wires being on.

[00:12:05]Okay. So SAT is now possible because we made every ingredient basically and yeah so we creating this SAT uh in in the simulation and this is a pretty simple SAT because I'm lazy and I didn't want to do a more complicated one. So right so this is the diagram we will representing. So if you can look at this uh SAT it's basically the same thing right it's a or not a b or not b c or not c and this is the are or gates and these are and gates and so this is the diagram we will be making so this is it uh abc and this is basically the same diagram of course it's not the same because the wires are diagonal but it's the same spirit Uh would you mind if uh I I actually complete the whole uh the whole diagram the whole essay?

[00:13:08]>> Yeah, that sounds like fun. Let's try it.

[00:13:10]>> Okay. Okay. So, I will just be making you look at this. What do you want to choose for A, B, and C?

[00:13:21]>> Um uh I don't know. I guess I'll say A is true and B is false and C is true.

[00:13:29][sighs] >> Okay. Okay. Okay. So A is true. You said yeah.

[00:13:35]>> Okay. Just for Okay. Yep.

[00:13:37]>> Yellow. Okay. So A is true. Whoa.

[00:13:41]>> And and so in theory, right, we if we actually had like a hexosolver or even like a like a depth 2 hexo reader, um we should be able to actually solve this.

[00:13:55]So yeah, basically what this means if uh is that a a perfect player for this game um basically it cannot be polomial or at least we we don't think it is because basically if it was polomial then P would equal MP and we will solve the million question problem question dollar question so yeah it's arbit so basically what this means is a position is arbitrarily complex okay so you said uh in the chat it says that won't satisfy the SAT expression.

[00:14:30]What do you mean by that?

[00:14:36]>> I think he's saying that >> yeah I chose were not uh sat satisfying the the expression. So, okay. A, not B, right? Not B and and not C or C, I don't remember. Not C.

[00:14:53]>> Uh, I think I said C, but not C is also fine.

[00:14:57]>> I think not C actually completes the SAT. Okay. So, uh let's go on with the wire.

[00:15:04]It may be uh may actually take a long time.

[00:15:14]because the it's it's pretty large of a construction so it may take some time.

[00:15:22]Yeah.

[00:15:33]Well, so okay, wait a minute. Um, so when you're doing that wire there, like in theory, yellow could sort of >> yellow could jump ahead, couldn't they?

[00:15:43]>> Okay. So, for example, say that this is an input just shifting the Yeah. So, suppose this was an input, right? What do you mean? Like I could do this, right?

[00:15:54]What you're saying?

[00:15:55]>> Uh, or what? Oh. Uh, >> if I do this, it's still >> I'm just imagining like yellow like plays. Um, I guess move your mouse to the up and to the right a little bit.

[00:16:08]>> Um, >> uh, I mean, where >> uh, like this >> over over three. Yeah. Yeah, that'll work. That'll do.

[00:16:15]>> Yeah, but this is a four in a row, right? And this is blocked off. So, it takes just one move for blue and I can win >> here.

[00:16:23]>> Try the um, Right. Try the try the one that you showed just a moment ago where you play like two elbows, two consecutive like corners >> like this. So basically I I just create two fors two fours but it it takes two moves to >> to block off.

[00:16:40]>> So even though it is a different method, it's still not cheating.

[00:16:45]>> I see. Okay, cool. Thank you.

[00:16:46]>> And actually it's faster. So maybe I should do do it. Okay, so this is our orgate. So C or B as I said. Uh yeah. So I will just complete it. It's an all right. Yeah.

[00:17:06]So of course perfect play from yellow.

[00:17:09]Uh right. Oh wait, there's a mistake here. Wait. Anyways, uh perfect play from yellow is expected because yellow wants to win, right? So, um, not continuing the Y is not a a rational decision, right? So, wait, what what is this?

[00:17:31]This is supposed to be a um Oh, yeah.

[00:17:35]No, wait. What?

[00:17:38]Maybe I made a mistake. It's supposed to to uh What?

[00:17:46]Oh, wait. No.

[00:17:48]>> Isn't that like the crossing over?

[00:17:51]>> Yeah. Yeah. But I I Wait, I don't I don't remember how to do it.

[00:17:57]Oh, yeah. Yeah. No. Oh, I I put this wrong. It's supposed to be yellow here, maybe.

[00:18:04]Wait. Anyways, this is supposed to make the the wire go here. No, not here.

[00:18:09]Here.

[00:18:11]So, I'm just putting some things here because the parity doesn't match.

[00:18:17]Okay, as I said, there may be some errors, but this is just a theoretical, right? So, this is another mistake I made. Uh, it's supposed to be here. No, wait. Here.

[00:18:30]Okay.

[00:18:32]Okay. Yes.

[00:18:34]So, yeah, I made some mistakes.

[00:18:42]Oh my god. Okay.

[00:18:48]Right here.

[00:18:52]Here.

[00:18:54]Okay.

[00:19:01]Oh, this is blocking off. Okay, fine.

[00:19:04]Okay, so this is an end gate. So, we need to go fill out something else. So, the not B goes up here. So, I won't fill out the whole wire. I just see where it goes. So over here and over here, right?

[00:19:19]So I just do something like this. Okay.

[00:19:27]And this is an orgate.

[00:19:39]So the wire goes here, here, here. Okay.

[00:19:42]It goes here. I will just make a couple of move here. Okay.

[00:19:48]Uh All right. The yellow supposed to make this move. Don't worry about this threat. I I forgot about it. It's a mistake. Anyways, so right this is continuing. So your example um so this goes here, right? Okay. So this is an end gate, right? This means both signals must be turned on. Uh however you said that like this is supposed to be either not C or not A but no they are not turned on. So this signal will never be turned on. So I don't think we will be able to achieve a win in this position.

[00:20:30]Okay. Uh so now a bit of theoretical um things. So yeah, we are we we proved MP completeness even though there are a couple of mistakes.

[00:20:42]Um so yeah this is not possible. Cool.

[00:20:47]Okay.

[00:20:48]Uh uh what is completeness? No sorry can we prove MP completeness? Right? Because it's a different thing from MP hardness.

[00:20:57]Uh so an MP hard problem we will show you the graph. An MP hard problem is basically a problem which is as hard as any MP problem. An MP problem is just a a problem which takes polinomial time to check for. So if I have a solution for an MP problem uh then there is a certificate that takes a polinomial time to check basically if this solution is correct. However, the MP problems could actually be we don't know but it could be actually super exponential or sorry exponential super polomial time to actually find the solution. NPR problems are problems which could be in MP or not that can basically simulate every MP problem inside of them or in this case the MP problem um I don't know how to I don't remember how to say basically we can simulate the MP problem inside the MP hard problem and this means that if we find a solution to an MP hard problem a polomial time solution to an NPR problem then we find also a polinomial time to a solution to on MP every MP problem. MP complete problems are MP hard problems. So as hard as every MP problem, but it's also inside MP. So a solution to an MP complete problem is checkable in polinomial time.

[00:22:18]However, um uh to check if a solution is a best in arbitrary position in X. So it's likely not easy to prove in polinomial time because maybe a a position is very complex.

[00:22:32]Uh wait I I see something in the chat.

[00:22:35]Would it be possible to generalize this to QBF by allowing blue to choose certain certain variables? Uh can you remember what be what is QBF?

[00:22:45]I don't know what it is.

[00:22:48]>> I guess I'll just talk. Uh so like a sad problem you have like there exists um certain variables right like there exists a b and c such that this statement is true. Um, QBF is like you're allowed to use for all, right?

[00:23:01]It's like for all A there exists B where for all C this statement is true. Um, so you're allowing >> Yeah. So what I'm wondering is like you're allowing yellow >> Yeah. You're allowing yellow to choose certain variables. I'm wondering if you could then allow black to choose certain variables as well. And then >> well I don't know actually because in this scenario or what do I call it in this scenario blue has no initiative because if it had it would choose to win the game right away. So I don't know because um the point of this simulation is that yellow has to make double threats. So blue has no choice but to respond to those threats.

[00:23:39]>> Yeah. Admittedly I'm not actually very good at hexo. I've not played hexo ever.

[00:23:43]But um yeah, I feel like if you have like two four in a rows, then you could just like allow uh Oh wait, no.

[00:23:51]>> So if you have two for two for a rows like >> so a four in a row, a three for a row is actually a double threat right away.

[00:23:59]>> Yeah.

[00:24:01]>> Yeah. Block on one side and then a second four in a row that is just a double thread.

[00:24:05]>> Oh, we could allow yellow >> like we could give yellow the ability to create double threats, right? Like yellow having the initiative might be enough here, >> right? What I don't What do you mean?

[00:24:19]Like yellow >> if yellow is yellow is able to favorably create uh like four in a row threats within one move, then maybe yellow could like selectively start new wires.

[00:24:33]>> Oh yeah. So basically the thing that like this but more more selectable variables >> right exactly I I think so >> I mean it wouldn't work for infinite variables because we would need infinite many infinite many space or place stones right if I don't know maybe there is a setup where blue actually can have the initiative without winning instantaneously. But I have no idea if this is possible.

[00:25:11]Okay. Uh so okay, we can go back, right?

[00:25:14]So hexo is likely not empty complete because to check whether a move is the best in a position is likely uh not checkable in polinomial time because it basically tells you okay now we are in this position. Is this the best possible position position we could be in? And it's likely not possible to know in polinomial time. [snorts] Okay. Uh so here are some more NPR questions. Actually it's just one in hex. So uh okay. So Z says I feel like we should try to prove P space completeness.

[00:25:51]Uh okay. So I don't know what that is but I mean oh yeah I know what that is.

[00:25:55]It's space. So it's uh memory related probably.

[00:26:05]No, it's likely possible anyways.

[00:26:08]So yeah, uh this is an RPR question which we just proved that solving is this position one for player one or player two is MP hard at least. Uh but some more questions are for example can this pattern appear?

[00:26:25]Because if I just put some pattern at the end and it can only be achieved by yellow putting both of these which is basically set SAT but for completing a position then the question can this pattern appear assuming perfect pay of course is also an NPR question.

[00:26:47]Okay. Uh so yeah I I yeah saw that uh in a few weeks oh no wait a few days actually uh someone is proving peace space completeness of go I believe or a a generalization of go uh so so yeah so I think this is my the end of my presentation I went by a little bit fast and I apologize if my um it wasn't the best for my accent or something. So, do you have any questions?

[00:27:19]>> Thank you. Um, I think that was pretty cool. I I think I followed all the ideas. Um, I mean, of course, I think you would be left with like the task of actually proving that your construction works and there's no like cheating involved, but like I imagine that you could like effectively run the the thing without any clever like oracle of hexo.

[00:27:40]Like all you need is just like a bot that can search to a depth of like two or something. And um like if you're you know if you if you have that bot then you can evaluate the circuit but not necessarily solve the the problem which is the hard part.

[00:27:58]Well yeah if well but a a bot like this construction takes a lot of moves to to evaluate. So a two depth bot wouldn't be able to actually solve this right.

[00:28:10]Oh, well well I mean but you couldate all like all like all wrong moves, right? Because there's only one move that doesn't result in you losing right away. So all of the moves are pretty much immediately forced, >> right? Yeah. Well, yeah, it's it's because once we select the variables, then it becomes SAT automatically. So yeah, it evolves naturally.

[00:28:39]Yep.

[00:28:43][snorts] >> Okay. So, no more questions. No, >> I was uh still a little confused about the discussion about the not gates >> like that's pretty important for NP hard that like you have maybe not not but something like how can we get what we want out of this?

[00:29:03]>> So, you're asking about this, right?

[00:29:07]Yes.

[00:29:08]>> Okay. So, basically uh the yellow chooses one of two um wires basically and we just say like the upper one is true. So, A is true and the down one is false A. So, A is false. So, basically what this means is that uh yellow has to choose sooner or later because he has to make a double threat. if he if he doesn't uh he loses. So he's forced to make a choice, right? And sorry and he can cannot make both wires on at the same time. Because if he did, okay, for example, say it is yellow's turn right now. No. And I make this double threat, then blue blocking makes a double threat. And if blue makes a double threat, then he automatically wins because blue can make this quadruple threat here. So what this means is that hey uh sorry yellow s is forced to make a choice basically for which variable is true or false and this is the the mpr question basically because the choice of these variables is basically entailing the this SAT problem.

[00:30:24]Did I answer your question?

[00:30:29]I will comment here briefly. I think so I think what's going on maybe >> is like this isn't actually like a true notgate but rather like a selector that you have at the beginning.

[00:30:41]>> And this is okay because like we know that our like we don't have to take general knots of like general boolean expressions but rather we can just get away with doing like all the knots in the beginning. Um because we could just like use like de Morgan's laws to um construct a more complicated knot and like we're given that like I forget the name of the like the boolean expressions where you have like the the ands on the outside and yours on the inside but that's what we have. So I think we can get away with this like selector to start.

[00:31:13]>> Correct me if I'm wrong.

[00:31:14]>> No. Yeah.

[00:31:15]>> Yeah. For the stat problem, we only have negations of variables and that gives us >> right. So I I don't know if that works as a generalized or not. It seems to me like maybe it doesn't, but that's that's okay for the proof.

[00:31:30]>> Actually, I think that in this setup where there's are there are wise in this specific case, it's actually not possible to create a a a not gate because one can just like don't not continue the wire and it's basically just a not, right? So it would be impossible to actually know whether a wire is actually off or on.

[00:31:53]It's just like an off gate is the same as no no signal transmitted. So there's no way to know that. But this the these selectors are fine because in this SAT the what um the variables are negated at the start.

[00:32:14]Right. So no more questions. So can we can end it.

[00:32:22]>> Thanks a lot. I appreciate it.

[00:32:23]>> Okay, >> I'm going to stop the recording.

[00:32:26]>> Okay, thank you too and I hope you have a good day.

[00:32:33]>> You too.