SRL Archive - General

As many project of artificial intelligence, I have to implement the artificial intelligence to a robot so that he could win the game. The game is video simple to understand.. you have 4 figures (+-•x). To win the game, those pieces must be placed in a 5 per 5 board and those pieces are randomly given.

To form the "x" figure, is needed 5 pieces (or 9) if that many pieces are given, to form the 'x' figure. For the '+', 5 or 9 pieces to score. the same goes For the ° (4 or 8 pieces) and the last figure - (2 or 3 pieces). They must be placed in the board respecting the order that is given (given pieces goes from 2 to 25), and when a complete figure is made, that figure is taken from the board and we get more free space on the board.

Pieces must be placed randomly, not predefined, and the robot must know how and where to place them in order to win the game!

The robot is complete, but still can't think of a way to give artificial intelligence!! Any thoughts?

Here goes the link with every progress made so far. Everyone take a look and give some feedback please!
I know it's a foreign language, but pictures are understandable!

http://inteligenciaartificial2015.wordpress.com

Any additional information, I can provide!

From: onilika
….

Is it like tic-tac-toe but with shapes instead of lining up in a row? I don't actually understand the explanation of the game. Why do you need AI? Is the robot facing off against someone or is it just solving its own puzzle/problem?

From: Brandon
Is it like tic-tac-toe but with shapes instead of lining up in a row? I don't actually understand the explanation of the game. Why do you need AI? Is the robot facing off against someone or is it just solving its own puzzle/problem?

It is its own puzzle. i understand it. gimme a moment to make some drawings…

For the x's
so you can remove the x's by placing them in an X pattern as shown here…. the red is just 1 example of its placement, whereas the blue is the only place you can create an X made of 9 x's.
Once an X (or whatever is created, it is removed and those spaces freed up for other symbols to be placed.

likewise with the +.

and the circles…
can you also make a 4x4 (12 total) or a 5x5 (16 total) circle?

can you make a 4x1 dash also? and do these need to be horizontal or can they also be vertical?



My advice for writing an AI for it… play it yourself and develop a strategy. then just turn that into code.

Are you given all the pieces beforehand, but unable to use them until you get to them? ie ++x-+xo-xo+? If so, id start by determining what you can make.
does the board start with a few random pieces on it already?


Annyway. So you have the robot done… please tell me the AI isnt the final part of your project and its due this friday…

From: Brandon
Is it like tic-tac-toe but with shapes instead of lining up in a row? I don't actually understand the explanation of the game. Why do you need AI? Is the robot facing off against someone or is it just solving its own puzzle/problem?

It's like Turpinator mentioned! It's given a random sequence of pieces, and the robot must solve its own problem, hence the AI.

From: Turpinator

can you also make a 4x4 (12 total) or a 5x5 (16 total) circle?

Only a 2x2 and 3x3 circle! :)

From: Turpinator

can you make a 4x1 dash also? and do these need to be horizontal or can they also be vertical?

Dash is only on the horizontal and is 2x1 and 3x1 :p

From: Turpinator

My advice for writing an AI for it… play it yourself and develop a strategy. then just turn that into code.

Are you given all the pieces beforehand, but unable to use them until you get to them? ie ++x-+xo-xo+? If so, id start by determining what you can make.
does the board start with a few random pieces on it already?

Annyway. So you have the robot done… please tell me the AI isnt the final part of your project and its due this friday…

The pieces are made by us. The teacher will grab them and put them on a sequence (random). The robot has a color sensor, will read the pieces and will save them in an array.
And yes, the sequence is something like what you posted.

The robot is finished, it can read the pieces, walk along the board, grab them and put on random positions of the board (that was what the teacher asked for the first phase of the project. Must be a dummy robot that only knows to place the pieces randomly on the board.

The second and last phase is for mid January and the IA must be ready at the time.

I will post the link of the blog that we had to create so I don't need to write a 25 pages report haha

Link: http://inteligenciaartificial2015.wordpress.com

What you do is have the robot scan the board into the array like you said.

Go through the array and find the most occurrences for a single piece. Then find the minimum occurrences for another piece that is not the max piece.

This will allow you to determine which "set" you can eliminate first and foremost. You should probably also consider "weighing" each set or piece.

Dash weighs MORE than circle and X because it's the easiest to solve and only goes in a single direction for both 2x1 and 3x1.


2x2 circle is easier to solve than the simplest X. Simplest X is easier to solve than the 3x3 circle as there are less pieces to put into place if the simplest X is 3x3.

The simplest Plus is the same complexity as the simplest X.


The idea is to look for either the largest complexity or the smallest first. Smallest will allow you to eliminate quickly but only small portions of the board.. However, it is a better choice than large first, as you won't have to stall. Large complexities will allow you to eliminate a bigger portion of the board but may be slower to complete and you may have to wait until you get the right piece to solve a large one. Attempting to solve a large one prematurely may cause you to lose your chances at solving a small one.

So the choice your AI has to make is whether it has close enough pieces to solve a large one or to continue solving a small one.

Keep a copy of the current state of the board and pieces that you have. The next step would be to calculate the chances of solving a set on the next draw (whenever you get a next piece.. what's the easiest or largest to solve? Rank them in order then solve).


This approach is basic.. weighing choices.

From: Brandon


This approach is basic.. weighing choices.

noted down pretty much what you wrote to interiorize the idea.
Need to think how that approach could be written on java, the algorithms, etc.. Code will definitely be harder to implement.

I'm having great difficulty on thinking how to make the heuristics for this game. My deadline ends in a week from now, still haven't figured how to do the heuristics, still got exams and paperwork to deliver, and don't even know how to do.

If someone could help me figure how to make the heuristics, I would be appreciated :(

From: onilika
I'm having great difficulty on thinking how to make the heuristics for this game. My deadline ends in a week from now, still haven't figured how to do the heuristics, still got exams and paperwork to deliver, and don't even know how to do.

If someone could help me figure how to make the heuristics, I would be appreciated :(

Basicly like brandon said you need to work up with preferences. But my idea is different is to make not only figures preferencable but the locations for the shapes too. While aiming for highest figures possible. It is very clear to occupy corners with X, thats no brainer if you going for large X. Also no brainer is middle left or other chosen corner make as + reserve. Also no brainer is like middle clear at all costs and only put item there if it isthe final piece of the puzzle. Also make some minor axis for X and + to form like i did and a minor preferable space for small o also reserve some space for -. Basicly huge figuresin picture represents high priority places and small ones lower. But there should be some middle priority too like the x which is the center of the minor + and so on.



Just the idea.

Also try to cluster and only do one figure of same type. And avoid at all costs it ruining. For example you place x randomly. Then reserve the last 4 spots for xes unless whole board is clogged with other figures. Since X and + matchs only at middle try keep middle clear and try to always combine building x with building +. Also you can combine building huge 0 with - by keeping one end extension of - reserved in the 0.

What you would need is probably the min-max algorithm and its implementation in games. The "ai" player has to make an optimal move to counter your move each turn. There are many common algorithms fro this, but min max is by far the easiest. Topics you would want to read about are::

alpha beta pruning,
A* search,
Min max algorithm.
http://ai-depot.com/articles/minimax-explained/