Skip to main content

Indie game storeFree gamesFun gamesHorror games
Game developmentAssetsComics
SalesBundles
Jobs
TagsGame Engines

Collapsi

be the last player able to move around a collapsing grid · By Riffle Shuffle & Roll

Good rule change for first move of game

A topic by gpoquiz created 22 days ago Views: 297 Replies: 28
Viewing posts 1 to 6

Changing from moving anywhere to having 1 move at the start is great!  I don't know if this was a data backed decision, but my code calculated around a 60% ish advantage for player 1 before, and now it's much closer to 50-50.  (Which offsets the fact that I'm annoyed that I had to change my code ;) ).   Also planning on uploading my own digital collapsi, thank you for the inspiration!

That's of course with perfect play, probably not for the average humans playing the game.  

Developer

I am happy to see there is balance.  I made the change to provide focus for the opening rules.  I felt the game was too open in the beginning and gave players a sense of what exactly am I trying to do right now?  I wanted the setup and first moves to be a simple as possible.  Thank you for taking the time to run the simulations!  

(1 edit)

It's a matter of habit. I played about 1,000 games with the original rule, and the score was approximately 50:50. After the change, I initially felt that there was a greater element of chance in the game due to the generated board and limited first move, but I've gotten used to it now. In any case, before the rule change, I had a fairly high percentage of games with AI where we both picked almost the entire board, but now the game ends sooner. Where it has helped a lot is in solo mode, where I felt that with a 3x3 board I could solve almost every board, but now with the new rule, the difficulty is higher, especially in 4x4 mode.

The win ratio is still somewhere around 50:50.

Developer

I am seeing some personal preferences when it comes to how the game begins.  Another fun idea a number of people have shared is to replace the starting cards with numbers and allow the players to pick where they begin the game.  I included this in the PDF as a rule variation.  I don't replace the numbers though.  Instead, the rules state that the jacks begin the game collapsed.  

As in you personally played against your bot, or you had your bot play against itself?  If just you playing against your bot, I would encourage you to set up bot v bot play and see if there is bias in your algorithm!  Also is your minimax algorithm full depth?  Theoretically you should be able to determine who has a guaranteed win at the start of every game.

When's the digital version of collapsi going to be available?

Developer

You can play Sentinel's web implementation right here: https://sentinel65.github.io/Collapsi_AI_BASE64_en.html

It is good. =^)

I'm still working on mine.  Should be in a good state soon, just polishing.

Hi, I add link to itch.io too

https://sentinel65.itch.io/collapsi-js

Developer

Could you please credit me as the designer on the page and link to the game’s Itch page?   Linking to the youtube video would be good as well. ☺️

(2 edits)

Hi, I'll definitely add it there, but right now I'm having a big problem with the Embed options settings, where it automatically switches to full screen on my mobile phone. It only does this with the link to https://sentinel65.itch.io/collapsi-js,  the link https://sentinel65.github.io/Collapsi_AI_BASE64_en.html displays fine on my mobile phone. I have no idea what to do about it. This is my first time doing this.

Developer (1 edit)

Thank you!  I am sure you figure it out. I wish I could help you with that, but it is all beyond my capability.   Be sure to tell me when it is ready, and I will link to it in the video description. 

Oh, sorry to highjack this thread, but you're linking digital versions in the youtube description?  
https://gpoquiz.itch.io/collapsi
Just in case you hadn't seen it yet.  

(+1)

https://gpoquiz.itch.io/collapsi

Done now!

Actually sorry, I was misreading my metrics, it seems to be the opposite.  I initially though that reducing p1's options at the start meant that there are less opportunities for a guaranteed win.  But I forgot to account for the fact that p2 also has much fewer options for "escape" on their turn.  

Metrics:

  • 10,000 Games
  •  56,205,893 end states calculated.
    • .000295 ms/end state 
    • Takes first path found to victory and trims sibling branches
  • 50.2% states where p1 wins
  • 49.8% states where p2 wins
  • 7,803 guaranteed p1 wins
  • 2,197 guaranteed p2 wins

Again, this is with no maximum calculated depth aka perfect play.  Thinking 8 turns into the future with generally 4 options each turn is not something possible for most people. 

Also, I was misremembering the original metrics.  Previous bias was actual 37-63~ Anecdotally, when playing against my wife I went second a lot and it felt like I was losing more, but I figured it was a skill issue. (It probably still was)

P1 moves 1, P2 moves 4 is more fair computationally (5193-4807), but of course I'm not saying you should make balance decisions off of this.  Reducing starting options to 4 makes the start of the game less overwhelming, and also having different starting rules for p1 and p2 could overcomplicate a game that excels in its simplicity.  

If anything, my only suggesting would be adding a line like this: 

WIN
The last player able to complete a move wins the game.  For the next game, swap who goes first.

Sorry, that was a long winded post.  But just to reiterate, I'm not trying to tell the designer how to make their game, just thought the data was interesting!
Thanks so much for the game.  (Oh, and if anyone sees this and has experience in c++ or decision trees generally, it would be great if I could get my algorithm peer reviewed for correctness.)

Developer (1 edit) (+1)

I love seeing this sort of data!  Are you able to determine how many cards are remaining uncollapsed once a player wins in your simulations?  I’d like to know the range and average.  

I would like to develop a score system based on how many cards remain face up. The player earns one point for each card face up when they win. Play rounds until a player reaches x score (alternating who goes first as you suggest!)

I can definitely do that.  I'm putting the finishing touches on my digital version, but after that I can tweak my base code for whatever metrics you want.  

My initial thoughts on the scoring system:
If I'm understanding the design correctly, you want to reward  the winner of a round for winning quickly?  Or maybe just because score adds some variance that can be fun?  And of course you need the average so you can determine the number of rounds.  I like the idea, but I'm not sure first to X is the best.  Perfect players, (or even possibly adequate players) would have few cards, but new players may make mistakes that end the game much earlier. 

My guess would be that "great" players should average 2-4 cards, and new players may average 4-6 cards (vibes based statistics).

  • Low Score Threshold
    • good length for great players
    • too short for new players
  • Mid Score Threshold
    • Potentially a good compromise, but potentially not good for anyone
  • High Score Threshold
    • good length for new players
    • too long for great players

With that being said, a better system might be highest score in X rounds.  But I know very little about game design beyond my own personal experiences, I would love to hear the full thought process.  

Sorry, another long winded post.  As for your data query.  What parameters would you like?  Perfect play, or a lesser depth?  Or a more complicated set of rules to better simulate human play (Depth 1 perfect play, prioritize higher numbers, prioritize reducing opponent moves, etc.)

Oh, and please don't take any of this as trying to explain your own game to you lol.  Just thinking out loud.

Developer(+1)

You are exactly right about the scoring being swingy based on skill level.   Spot on.  Highest score after four rounds seems intuitively correct to me (each player gets to go first two times in a game.  If tied at the end of the fourth round choose who goes first at random.  BUT, I would still like to at least explore the option of having a "first to x points" win objective.  You mentioned in a previous post that the AI is able to see 8 turns into the future.  Are you able to limit that to only 1, 2, or 3 turns into the future so we could see data for a more human-like skill level?  It seems to me that most people will only be able to see 1 or 2 turns into the future because they don't know what decision the opposite player will make.  If we can get game data with that in mind, we might be able to get a more realistic number for how many points makes sense.  

If the game does end up just being played for X number of rounds, the data for how many cards are left would not be necessary, but it would still be really fun to see.  

Alternative to alternating or determining randomly: If there is an innate advantage with going first, then the person with the least points can go first, as sort of a comeback mechanic.

(1 edit) (+1)

All sims are 100,000 games.

Depth Total Duration (ms) Average Duration (ms) End States Considered Uncollapsed Cards Average Uncollapsed Cards Standard Deviation Balance (P1-P2)
0 420 0.0042 0 5.44837 1.61097 50.1-49.9
1 1005 0.01005 100,000 5.91061 1.88247 50.5-49.5
2 3173 0.03173 290,712 5.91045 1.87536 50.2-49.8
3 9481 0.09481 803,160 5.93895 1.8215 49.4-50.6
16 102,471 1.02471 360,327,245 5.7415 1.43887 78-22

I'm happy to have been proven wrong here, it seems like on average, 5.5-6 cards will be uncollapsed by the end of the game, regardless of level of depth.  The standard deviation goes down as depth increases, which is to be expected.  
Oh, and depth here = 1 person's turn, so 3 depth == If i do this, then he does this, then I do this, do i win?

Developer(+1)

Wow!  That is so cool to see.  Okay, that makes a scoring system based on cards remaining face up feasible.  Thank you so much for crunching these numbers.  Do you think it would possible to do this with the shift rule I introduced as an optional way to play?

(1 edit) (-1)

I am glad that gpoquiz's simulation results essentially confirmed what I already wrote in  this thread based on my own experience of playing about 1,000 games with AI namely that the win ratio is approximately 50:50 and that, on average, one game lasts 5-6 rounds.

It would be interesting if he tried to simulate the same number of games to see what the starting situation is for a player who goes first and, after the board is generated, has only cards with a value of 1 or 2 around them. For me, this worked out to be about 30% of the board generation. Here, the imaginary advantage of the first move turns against the player. And it's true that in the case of playing with AI, I've noticed this many times, whether on the player's side or the AI's.

As for Shift mode, I am convinced that it will not be possible to combine it with Solo mode. Solo mode must have a generated solvable board, where the algorithm has clearly defined information about the game board, including coordinates, and assembles the game board in reverse (classic solo mode 3x3 or 4x4). In combination with Shift mode, the size of the board is known at the beginning of the game, but no one knows what the game board will look like at the end of the game. But maybe I'm wrong and someone will build a generator for Shift mode that will generate at least one path for solo mode with cards moving one space in a row or column after each move.

Napkin math says that 30% is far too high for the four surrounding starting cards to be all 1's or 2's
Deck: 1,1,1,1,2,2,2,2,3,3,3,3,4,4.
(four 1, 2 in a row)
(8*7*6*5)/(14/13/12/11)
= 1680/24024 = .069 = 6.9%.
This is an upper bound, since drawing 4 for your surrounding cards in a row is the ideal circumstance.  In almost every other case you will have less than 8,7,6, or 5 1's or 2's left in the deck. 
Simulated:
100,000
p1: 5180 = .0518 = 5.2%
p2: 5168 = .05168 = 5.2%
both: 392 = .00392 = .3%

If your generation has 30% 1's or 2's in all starting positions then I would guess that your generation is wrong.  

I haven't played with the shift rule yet, but really like the concept!  I'm trying to force myself to take a small break from programming, but it will be an interesting challenge!  Adding shift will double the mathematical complexity, and so I may need to even run simulations overnight!  Oh, and then of course adding shift to my digital version when I get around to it.  

My guess is that the shift means that it's much easier to "escape", so like how p2 was favored when the first turn could move anywhere, I would guess p2 is favored in the shift variant.  And for the cards left, I would guess that there may be more cases where there are no collapsed cards left at the end of the game. (aka p2 wins)  Again, just hypotheses.  

Developer

Are you able to tell me the fewest turns it would take for a player to win a game?  

Sims show 5, but I would say that number comes with caveats.  Here is an example game.

https://pastebin.com/9ceEzqmp

In this game player 1 is guaranteed to win.  Because both players are "perfect," player 2 also knows this, and kinda "gives up."  Or in other words, plays randomly.  But the move on turn 4 is obviously a bad move for p2, because it's a guaranteed loss in one. 

So, if you mean in all cases, then yes, 5 is going to be the least turns until game ends (I couldn't construct a game that purposefully loses faster than that), but that may require a player to lose faster than what may be "normal".

Changing the heuristic so that the bot extends the game as long as it can (more opportunities for a human opponent to make a mistake) is on my to-do list, but will be a slightly more involved change, so I'm putting it off.

Fun fact:  Collapsi has 378,378,000 unique states.  (16!/(4!4!4!2!2!))  This isn't counting the fact that if you shift the board left or right, the board is technically the same due to wrapping.  (I think that's /12, so 31,531,500 but not confident.)

(7 edits) (-1)

Gentlemen, this is a game for fun, not chess, which I also enjoy very much, by the way :-) So, while the numbers are interesting, they are just theory. I've played hundreds of games with AI on my phone, and the ratio is still around 50:50. In my opinion, this number is quite significant because it keeps human players aware that you can play with AI, you can win, and of course, you can lose. But it's not about coming up with a super AI algorithm that will crush humans and give them basically no chance of winning. Believe me, that would quickly discourage any player. It's written in JS, so the power of the AI is limited, but within the possibilities, it's at least a little bit good. I've already mentioned this somewhere here, I'm not a programmer, I was introduced to this game by my older son, who also likes board games and has two little boys with whom he plays a lot. I was very interested in Mark's idea and tried playing it with my girlfriend. We found that the games are very fast, so I tried programming a JS port of this game for myself with the help of AI. The fact that it has reached this stage is another matter. I think it's playable, and for me it was essential that I could run it on my phone without having to be connected to the internet. I tried to make the graphics at least somewhat realistic, corresponding to the joker cards.

For me personally, it's an incredible experience with AI (free chatGPT) from the perspective of someone who is not a programmer. It takes a lot of time and patience, and the AI was constantly suggesting things. Now it's at a stage where I don't even have any ideas for improvements. I tried to keep the graphics simple, which I think I succeeded in doing. In the last few days, I've been replacing text with graphic pictograms wherever possible. The important thing is to have fun :-)

You can try play the game here:    Collapsi JS