Business Analytics Blog

Business Analytics Blog

Opinions expressed on this blog reflect the writer’s views and not the position of the Capgemini Group

Board of OR?

Categories : EntertainmentHome

Welcome to “Figure It Out”, a weekly email from the Operational Research (OR) team taking a light-hearted look at the numbers behind the news. The Easter break was a welcome break for us all from all the hard work we do, especially here in OR. But the hard work may not end there. Whether you were enjoying the great British weather or travelled further afield a lot of us would’ve been faced with the obstacle of entertaining children. What you may not realise is just how big a part OR play in entertaining us all. Frightening as it may sound that OR could be entertaining not only is it that it is also something that many of you will have used without realising. I am hoping that everyone is familiar with the board game Battleship and hopefully less familiar with Monte Carlo methods but Battleship in fact incorporates Monte Carlo tree search into algorithms for playing the game – well it does if you want to win. But what are Monte Carlo methods? Monte Carlo methods (or Monte Carlo experiments) are a class of computational algorithms that rely on repeated random sampling to compute their results. Each result allows the user to refine the possibility of outcomes that can lead to a successful outcome. Put simply each outcome increases the possibility of identifying the next successful outcome. The game Battleship (also known as Battleships) is a guessing game played by two people. It is known throughout the world as a pencil and paper game and predates World War I in this form. The game is played on four grids, two for each player. The grids are typically square – usually 10 × 10 – and the individual squares in the grid are identified by letter and number. On one grid the player arranges ships and records the shots by the opponent. On the other grid the player records his own shots. Before play begins, each player arranges a number of ships secretly on the grid for that player. Each ship occupies a number of consecutive squares on the grid, arranged either horizontally or vertically. The number of squares for each ship is determined by the type of the ship. The ships cannot overlap (i.e., at most one ship can occupy any given square in the grid). The types and numbers of ships allowed are the same for each player. Since you cannot see your opponent’s placements the game begins essentially as a guessing game but thanks to Monte Carlo it develops into something a lot more strategic than random guessing. So where does the Monte Carlo tree search come into this? Well very basically a Monte Carlo tree search uses the result of the outcome to give higher priority to different selections as can be seen below. To demonstrate this we will assume one ship only of size 4.



Initially the shot selection will need to be random because you have no indication to where your opponent will have placed the ship. However, once you hit his ship that’s where the algorithm comes into play. In scenario B you have made a successful hit on the ship. You now know that the ship can only be down from that point or to the right as the white dots indicate that there is no ship in those cells. So the Monte Carlo tree search is essentially allows you to identify the cells which have the highest possibility of containing the ship. In scenario C both the back and the front of the ship have been hit and so the tree search tightens further still revealing only 2 further coordinates where the rest of the ship could be. The probability of a “hit” in scenario A is quite low at just under 2%. In scenario B since the hit has been successful your probability of a hit in the next go is now 50% because you know that the remainder of the ship can only be in one of 6 cells and once the back and front have been hit then in Scenario C the probability of a success hit in the next go is actually 100%.  A good technique to employ, contrary to popular belief, is to actually place your ships close together because whilst it may be easy for your opponent to sink all of your ships once they’ve realised that you have them close together initially they will not know this and will be as random with their selection as they can. Also by having them close together if your opponent hits successfully they are also very likely to hit a totally different ship with their next move but think that it is the same ship. Once they think they have hit the same ship they will always move in one direction in order to completely sink the ship, however if you have place the ships close together then it makes it harder for them to indentify which ships it is they have actually hit in the first place. The Monte Carlo tree search will naturally give higher priority to those coordinates nearest to a successful hit in order to completely sink the ship. If the ships are closer together it will be harder to identify which ship has been hit. So when you see you child playing Battleship or indeed if you indulge in a game yourself then spare a thought for your buddy’s in OR who many years ago would’ve have used very similar techniques in real life situations.   OR is as relevant in today’s electronic games as it is in 100-year-old games.  Take one variant of Donkey Kong & Mario, for example, where DK is passing cement bags onto three conveyor belts that are moving at different speeds.  Mario’s (and your) job is to offload the bags into the van without missing a bag and losing a life.  The game needs some quick OR thinking and benefits from simple scheduling techniques, and its internal coding is likely to include elements such as mathematical programming and optimisation algorithms.  And you thought OR was just hard work …

About the author

Nigel Lewis
Nigel Lewis
Nigel leads the Capgemini Consulting’s 35 strong Business Analytics team, which delivers analytical, operational and strategic modelling solutions to clients. He has 18 years consultancy experience as well as 8 years experience in the UK gas industry. Nigel has successfully managed complex projects in both the public and private sector, including capacity modelling, simulating supply chain operations, strategic business modelling to support future policy decisions, and implementing complex demand forecasting systems. Nigel is currently focussing on the development of Capgemini’s customer analytics and analytics advisory services.

Leave a comment

Your email address will not be published. Required fields are marked *.