XMash Rush (CC07) - Feedback & Strategies


#45

Thanks Csipcsirip

I didn’t simulate until the end of the game.
During simulation phase (rollout) I just play one more move or not at all:

<<According to the last action played during the selection-expansion:
-for a PUSH, evaluate the current position (no additional action)
-for a MOVE, play one additional push for each player according to the following heuristics: try 5 pushes at random, keep the most promising >>
(promising = a good score with the Evaluation function for a player)

For many people, what I did was not an MCTS.
It is an UCT (Upper Confidence applies to Tree).
For me, there is enough randomness (during expansion, for additional action after a move, for new quests) to talk about MCTS (Monte Carlo TS)


#46

A MCTS using UCB is called UCT (if i remember well).

But since you are using random to predict the future (for the next quests), it is called ISMCTS. This is what i tried (unsuccessful) in LOCAM. You just do a MCTS algorithm and you randomize what you don’t know.

Anyway, thanks you for the PM.


#47

… and one week to rule them all !!!

I would suggest Halite III


or RAIC
http://russianaicup.ru/

Both of them will last longer than 4 weeks from now. CG has traditionally 10 day contests, which is what the community is used to the most. Personally i prefer the 10 days variant, although slightly different variant might be better suited even for this community, who knows?


#48

Thank you for the suggestions. I know them and am already playing Halite. But these are just too long!
So for me this CG competition is like running the 500m race. Halite is more of a 42km marathon.
I would just like to run the 2km race…


#49

Play multis, code at your own pace. There are many fun ones.
And try to ask in chat, picking the wrong strategy / data structure ends up in frustration and lot of useless code. I’m always open to discuss ideas on chat, challenges or not.


#50

Is there a specific achievement for @RockyMullet and myself for being above beber after ~30min game :smiley: ?

image

More seriously, great contest once again! Congratulations to the team who developed it and to the top players of course, for making the competition really worth watching and for the PMs.

I really struggled to simulate the push efficiently, because of the module copy.deepcopy in python which is very slow, and therefore hardly reached the 28 simulations per turn (1 push, 3BFS). I was advised on the chat to try to clone the objects instead of deepcopying them, which I will try next time with more success hopefully. :slight_smile:


#51

Why was copy.deepcopy necessary for the simulation?

You can do a full simulation without it. Just use a few for loops. Only needed one for each quest list iteration actually.

And then you can actually implement your own light-weight version which only copies the bits you need for the specific task, instead of the entire list of objects. Why did some folks use it and then complain it’s slow? I simply fail to see the benefits.

So while ignoring my horrible evaluation that clearly didn’t work, i could iterate through all push possibilities for myself and the opponent each turn.

On the move turn i could do BFS x 3 for a total of 3 quest items + another BFS for guessing the 4th item or moving towards the edge!


#52

I used it to save my game state first, and then come back to it after simulating the push and the BFS. Yes, implementing reverse push or using bits would have been faster…but I don’t complain that deepcopy is slow, as if it did not exist, my final rank would be even worse :smiley: . I blame myself for not finding a better data structure and for failing to implement some simple simulations efficiently, as the game was perfect for this!


#53

I finished my BFS article that has some tricks for optimization. You can find it here:

There is a lot of stealable code near the top of the article, including the various BFS versions and a simple maze generator.


#54

Nice article, very detailled :wink:

If I may add another tip I use myself, regarding the visited data :
You can use an array of int, and a counter on the side :

array<int, N> visited;
for (int i = 0, i < N; ++i) visited[i] = -1;
int visitedFlag = -1;

[...]

bfs() {
	visitedFlag++;

	[...]

	for (Cell &neighbor: current.neighbors) {
		if (visited[neighbor.id] != visitedFlag) {
		   // add in the queue
		}
	}
}

You then don’t have to reset the visited array/hash/map/wathever for each BFS


#56

Thanks, that is a good tip.


#57

During tree search I ignored rule about 20 moves and used whole connectivity components (for example to process all connected items) and here is my code for connectivity component:

uint64_t spread_area(uint64_t can[4], uint64_t start_area)
{
	uint64_t prev = 0;
	uint64_t ret = start_area;
	while (ret != prev) {
		prev = ret;
		ret |= (ret & can[LEFT]) >> 1;
		ret |= (ret & can[UP]) >> 7;
		ret |= (ret & can[RIGHT]) << 1;
		ret |= (ret & can[DOWN]) << 7;
	}

	return ret;
}

Coordinates are numbers from 0 to 48, if you interested in particular coordinate c, you can pass 1ULL<<c to this function as start_area. In each position I store array uint64_t can[4] : for example 49 bits of can[UP] mean can I or can’t go up for each coordinate where LEFT, UP, RIGHT, DOWN are global constants 0, 1, 2, 3. If you need area of connectivity component you should use 1 bitcount instruction (or 2 since I couldn’t find 64-bit one for gcc). You may think that can[] is hard array to calculate, but I store field in the same way and for example

can[DOWN] = (field[UP]>>7) & field[DOWN];

I guess this was fast.


#58

You can use __builtin_popcountll() for 64-bit


#59

I tried with suffix ull but this didn’t compile. I was afraid that sign conversion would slow the program.


#60

Try on godbolt.org to see whether the signed version creates any more instructions.

I’m pretty sure on most machines with 2’s complement representation there will be zero extra instructions.


#61

The gcc popcount builtins only take unsigned values (even though they don’t say ull).

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html


#62

About popcountll in signed, it just works the same and compiles OK.
https://godbolt.org/z/Q1jvII
https://tech.io/snippet/eoxDhtY
All possible functions leads to the same assembler. Even the int countCasted(long long C), where I use an union{} to reinterpret bits from signed as unsigned. There is 0 penalty on these.


#63

I don’t quite understand this code. Why would the id of the neighbors be equal to the incrementing counter?


#64

Not the id, but visited[id].
The BFS starts with visitedFlag++;, which counts the number of BFS runs performed. Then you check, if the visited value equals the current run and set it to that if not. So visited stores, in which BFS run you visited the node for the last time (instead of having a boolean array).

I just noticed the typo in the title (XMash).


#65

Oh, I see. This is for running BFS multiple times with the same underlying data set. I get it now. Thank you!