[Boards: 3 / a / aco / adv / an / asp / b / biz / c / cgl / ck / cm / co / d / diy / e / fa / fit / g / gd / gif / h / hc / his / hm / hr / i / ic / int / jp / k / lgbt / lit / m / mlp / mu / n / news / o / out / p / po / pol / qa / r / r9k / s / s4s / sci / soc / sp / t / tg / toy / trash / trv / tv / u / v / vg / vp / vr / w / wg / wsg / wsr / x / y] [Home]
Help with mathematical game?
Images are sometimes not shown due to bandwidth/network issues. Refreshing the page usually helps.

You are currently reading a thread in /sci/ - Science & Math

I want to analyze the possible outcomes and strategies of this game, however I don't know where to start. Could you direct me to the specific area of math needed, or to similar problems? Thanks in advance. The game is the following
>There are n "blocks" mounted one over another in whatever number of towers. Two players, A and B, play one turn each, one after the other one. a player can either divide one tower of blocks into two of the same number of blocks, or join two different towers of DIFFERENT SIZE. What are the winning strategies for different n ? Are there any starting set ups that allow no player to win?
>>
what is the win condition ?
>>
>>7647288
oh, i forgot. The winning condition is that you leave a player without options for a play, that is, the player can't join two towers or separate one
>>
I'd start here https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
>>
>>7647330
I suppose that you need to make him do the n-1th turn,so i dont know,its difficult because there is no defined starting state of the game,its really dependent on the starting state how you are going to progress further
>>
>>7647357
You should look at it the other way. Start from a winning state. The move prior to that must be a losing state. Keep backtracking until you reach an arbitrary starting state.
>>
>>7647352
thanks! will look into it
>>7647357
that is true, for example, for n=5 there are several different setups, (5,0) ; (4.1) (3,2) etc
>>
>>7647363
you have N sets
each has M members

Odd sets cant be broken
Equal sets cant be merged

So you need to build up a situation where all sets are equal and odd . Right ?
>>
1-1-1-1-1... is always win
3-3-3-3-3... is also
5-5-5...etc

so you need to evaluate how deep you are going to force partitions.thats a strategy for starters
>>
if N is ODD than merging to 1 set is a wincon
>>
I have a way to do it. You use random numbers for n, and the towers. You also use random numbers for each player's action.

write a simple program, to simulate this encounter. Every time an end condition is reached, log the winning and losing strategies to a file.

If there is a dominant, repeatable sequence, you will start to see patterns.

If you see one that looks about right, hardcode the strategy and run the simulation again. See if it defeats random play.

Because this is a mathematical game, it is by far easiest to see what wins at whatever n, you can see if there is a universal dominant strategy, which would be nice, or if there is a different winning combination for every n.
>>
>>7647455
this is WAY too complicated and unreliable.

>>7647283
look up Nim games and grundy theorem
>>
>>7647478

Not really. You only look at winning strategies, so that cuts it by half. And you can rank them in order of time elapsed, from shortest to longest. Ideally, the winning strat will be a repeatable sequence of one two or three steps.

It's pretty simple to derive once you've seen the payoffs.

It's great and nice to postulate everything from pure theory, but experimentation is the spirit of all science.
>>
>>7647499
Yeah, no. You're not going to get anywhere trying to extrapolate sequences of random numbers into coherent strategies, and much less trying to choose between strategies by randomly matching against each other.

It's not "pretty simple to derive", it's a wishy-washy idea that doesn't actually work. The fact that you think cutting the time by half means anything when something like you described is not even asymptotically polynomial is telling that you haven't actually tried to do anything like this ever, and are just saying it because it sounds attractive.
>>
>>7647520

You preclude the chance of arriving at the correct answer purely by accident.

I can gather that perhaps you know the underlying theory, in which case, good for you. But, if the theory were unknown, you would be struck dumb and be incapable of any solution. I have posted an incomplete method that does not require any prior theory. Running simulations of this kind is very common in sequential games, and your main beef seems to be that I have described it poorly.